1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binær Search]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Dette er CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Hvis jeg gav dig en liste over Disney character navne i alfabetisk rækkefølge

5
00:00:09,000 --> 00:00:11,000
og bedt dig om at finde Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
hvordan ville du gå om at gøre dette?

7
00:00:13,000 --> 00:00:15,000
En indlysende måde ville være at scanne listen fra begyndelsen

8
00:00:15,000 --> 00:00:18,000
og kontrollere hver navn for at se, om det er Mickey.

9
00:00:18,000 --> 00:00:22,000
Men når du læser Aladdin, Alice, Ariel, og så videre,

10
00:00:22,000 --> 00:00:25,000
vil du hurtigt indse, at starte på forsiden af ​​listen ikke var en god idé.

11
00:00:25,000 --> 00:00:29,000
Okay, måske skulle du begynde at arbejde baglæns fra slutningen af ​​listen.

12
00:00:29,000 --> 00:00:33,000
Nu kan du læse Tarzan, Stitch, Snehvide, og så videre.

13
00:00:33,000 --> 00:00:36,000
Alligevel synes dette ikke som den bedste måde at gå om det.

14
00:00:36,000 --> 00:00:38,000
>> Nå, en anden måde, at du kunne gå om at gøre dette på er at forsøge at indsnævre

15
00:00:38,000 --> 00:00:41,000
listen over de navne, som du er nødt til at se på.

16
00:00:41,000 --> 00:00:43,000
Da du ved, at de er i alfabetisk rækkefølge,

17
00:00:43,000 --> 00:00:45,000
du bare kunne se på navnene i midten af ​​listen

18
00:00:45,000 --> 00:00:49,000
og kontrollere, om Mickey Mouse er før eller efter dette navn.

19
00:00:49,000 --> 00:00:51,000
Ser man på det sidste navn i anden kolonne

20
00:00:51,000 --> 00:00:54,000
du ville indse, at M for Mickey kommer efter J for Jasmine,

21
00:00:54,000 --> 00:00:57,000
så du ville bare ignorere den første halvdel af listen.

22
00:00:57,000 --> 00:00:59,000
Så skal du nok se på toppen af ​​den sidste kolonne

23
00:00:59,000 --> 00:01:02,000
og se, at det begynder med Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey kommer før Rapunzel, ser ud til vi kan ignorere den sidste kolonne så godt.

25
00:01:06,000 --> 00:01:08,000
Fortsat søgestrategien, vil du hurtigt se, at Mickey

26
00:01:08,000 --> 00:01:11,000
er i den første halvdel af den resterende navnelisten

27
00:01:11,000 --> 00:01:14,000
og endelig finde Mickey gemmer sig mellem Merlin og Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Hvad du lige gjorde var dybest set binær søgning.

29
00:01:17,000 --> 00:01:22,000
Da dette navnet antyder, det udfører sin søgning strategi i en binær sag.

30
00:01:22,000 --> 00:01:24,000
Hvad betyder dette?

31
00:01:24,000 --> 00:01:27,000
Nå, få en liste med sorterede elementer, det binære søgealgoritme gør en binær afgørelse -

32
00:01:27,000 --> 00:01:33,000
venstre eller højre, over eller under, alfabetisk før eller efter - i hvert punkt.

33
00:01:33,000 --> 00:01:35,000
Nu hvor vi har et navn, der går langs med denne søgealgoritme,

34
00:01:35,000 --> 00:01:38,000
lad os se på et andet eksempel, men denne gang med en liste over sorteret numre.

35
00:01:38,000 --> 00:01:43,000
Siger, at vi er på udkig efter det nummer 144 i denne liste over sorteret numre.

36
00:01:43,000 --> 00:01:46,000
Ligesom før, finder vi det tal, der er i midten -

37
00:01:46,000 --> 00:01:50,000
som i dette tilfælde er 13 - og se om 144 er større end eller mindre end 13.

38
00:01:50,000 --> 00:01:54,000
Da det er klart større end 13, kan vi ignorere alt, der er 13 eller derunder

39
00:01:54,000 --> 00:01:57,000
og bare koncentrere sig om den resterende halvdel.

40
00:01:57,000 --> 00:01:59,000
Da vi nu har et lige antal elementer tilbage,

41
00:01:59,000 --> 00:02:01,000
vi simpelthen vælge et nummer, der er tæt på midten.

42
00:02:01,000 --> 00:02:03,000
I dette tilfælde vælger vi 55.

43
00:02:03,000 --> 00:02:06,000
Vi kunne have lige så let valgt 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Igen, 144 er større end 55, så vi går til højre.

45
00:02:11,000 --> 00:02:14,000
Heldigvis for os, er det næste midterste tal 144,

46
00:02:14,000 --> 00:02:16,000
den vi leder efter.

47
00:02:16,000 --> 00:02:21,000
Så for at finde 144 ved hjælp af en binær søgning, vi er i stand til at finde det i kun 3 trin.

48
00:02:21,000 --> 00:02:24,000
Hvis vi ville have brugt lineær søgning her, ville det have taget os 12 trin.

49
00:02:24,000 --> 00:02:28,000
Som en kendsgerning, denne søgemetode siden halverer antallet af elementer

50
00:02:28,000 --> 00:02:31,000
det skal se på ved hvert trin, vil det finde det element, som søger efter

51
00:02:31,000 --> 00:02:35,000
i omkring loggen af ​​antallet af elementer på listen.

52
00:02:35,000 --> 00:02:37,000
Nu, hvor vi har set 2 eksempler, lad os tage et kig på

53
00:02:37,000 --> 00:02:41,000
nogle pseudokoden for en rekursiv funktion som implementerer binær søgning.

54
00:02:41,000 --> 00:02:44,000
Start foroven, kan vi se, at vi er nødt til at finde en funktion, der tager 4 argumenter:

55
00:02:44,000 --> 00:02:47,000
nøgle, array, min og max.

56
00:02:47,000 --> 00:02:51,000
Det centrale er det nummer, vi leder efter, så 144 i det foregående eksempel.

57
00:02:51,000 --> 00:02:54,000
Array er listen over numre, som vi søger.

58
00:02:54,000 --> 00:02:57,000
Min og max er indekser minimum og maksimum positioner

59
00:02:57,000 --> 00:02:59,000
at vi i øjeblikket kigger på.

60
00:02:59,000 --> 00:03:03,000
Så når vi starter, vil min være nul og maks. vil være den maksimale indeks af array.

61
00:03:03,000 --> 00:03:07,000
Som vi indsnævre søgningen ned, vil vi opdatere min og max

62
00:03:07,000 --> 00:03:10,000
at være lige det område, at vi stadig er på udkig i.

63
00:03:10,000 --> 00:03:12,000
>> Lad os springe til den interessante del først.

64
00:03:12,000 --> 00:03:14,000
Det første, vi gør, er at finde midtpunktet,

65
00:03:14,000 --> 00:03:19,000
det indeks, der ligger halvvejs mellem min og max af arrayet, at vi stadig overvejer.

66
00:03:19,000 --> 00:03:22,000
Så ser vi på værdien af ​​array ved at midtpunktet placering

67
00:03:22,000 --> 00:03:25,000
og se, om det nummer, vi leder efter, er mindre end den nøgle.

68
00:03:25,000 --> 00:03:27,000
Hvis antallet i denne position er mindre,

69
00:03:27,000 --> 00:03:31,000
så betyder det, at nøglen er større end alle numre til venstre for denne position.

70
00:03:31,000 --> 00:03:33,000
Så vi kan kalde binær søgefunktion igen,

71
00:03:33,000 --> 00:03:36,000
men denne gang opdatere min og max parametre for at læse bare det halve

72
00:03:36,000 --> 00:03:40,000
der er større end eller lig med den værdi, vi kiggede bare på.

73
00:03:40,000 --> 00:03:44,000
På den anden side, hvis nøglen er lavere end antallet i den aktuelle midtpunktet af arrayet

74
00:03:44,000 --> 00:03:47,000
vi ønsker at gå til venstre og ignorere alle tal, der er større.

75
00:03:47,000 --> 00:03:52,000
Igen, vi kalder binær søgning, men denne gang med den række af min og max opdateret

76
00:03:52,000 --> 00:03:54,000
omfatte blot den nederste halvdel.

77
00:03:54,000 --> 00:03:57,000
Hvis værdien på det aktuelle midtpunkt i arrayet er hverken

78
00:03:57,000 --> 00:04:01,000
større end eller mindre end tasten, så må det være lig med nøglen.

79
00:04:01,000 --> 00:04:05,000
Således kan vi blot returnere den aktuelle midtpunkt indeks, og vi er færdige.

80
00:04:05,000 --> 00:04:09,000
Endelig er denne kontrol her er for det tilfælde, at antallet

81
00:04:09,000 --> 00:04:11,000
er faktisk ikke i den vifte af numre, vi søger.

82
00:04:11,000 --> 00:04:14,000
Hvis den maksimale indeks for det område, vi er på udkig efter

83
00:04:14,000 --> 00:04:17,000
er stadig mindre end det minimum, der betyder, at vi har gået for langt.

84
00:04:17,000 --> 00:04:20,000
Da nummeret ikke var i inputarrayet, vender vi tilbage -1

85
00:04:20,000 --> 00:04:24,000
at indikere, at intet blev fundet.

86
00:04:24,000 --> 00:04:26,000
>> Du har måske bemærket, at for denne algoritme til at arbejde,

87
00:04:26,000 --> 00:04:28,000
listen over numre skal sorteres.

88
00:04:28,000 --> 00:04:31,000
Med andre ord kan vi kun finde 144 ved hjælp af binær søgning

89
00:04:31,000 --> 00:04:34,000
hvis alle tallene bestilles fra laveste til højeste.

90
00:04:34,000 --> 00:04:38,000
Hvis dette ikke var tilfældet, ville vi ikke være i stand til at udelukke halvdelen af ​​numrene på hvert trin.

91
00:04:38,000 --> 00:04:40,000
Så vi har 2 muligheder.

92
00:04:40,000 --> 00:04:43,000
Enten kan vi tage en usorteret liste og sortere det, før du bruger binær søgning,

93
00:04:43,000 --> 00:04:48,000
eller vi kan sørge for, at listen over numre sorteres som vi tilføje numre til det.

94
00:04:48,000 --> 00:04:50,000
I stedet for at sortere lige når vi er nødt til at søge,

95
00:04:50,000 --> 00:04:53,000
hvorfor ikke holde listen sorteres på alle tidspunkter?

96
00:04:53,000 --> 00:04:57,000
>> En måde at holde en liste over numre sorteres samtidig tillader

97
00:04:57,000 --> 00:04:59,000
en til at tilføje eller flytte numre fra denne liste

98
00:04:59,000 --> 00:05:02,000
er ved hjælp af noget, der hedder et binært søgetræ.

99
00:05:02,000 --> 00:05:05,000
En binær søgning træ er en datastruktur, der har 3 egenskaber.

100
00:05:05,000 --> 00:05:09,000
Først den venstre undertræ et emne indeholder kun værdier, der er mindre end

101
00:05:09,000 --> 00:05:11,000
eller lig med knudepunktet værdi.

102
00:05:11,000 --> 00:05:15,000
Dels ret undertræ af et knudepunkt kun indeholder værdier, der er større end

103
00:05:15,000 --> 00:05:17,000
eller lig med knudepunktet værdi.

104
00:05:17,000 --> 00:05:20,000
Og endelig både venstre og højre undertræer af alle knuder

105
00:05:20,000 --> 00:05:23,000
er også binære søgetræer.

106
00:05:23,000 --> 00:05:26,000
Lad os se på et eksempel med de samme numre, vi brugte tidligere.

107
00:05:26,000 --> 00:05:30,000
For dem af jer, der aldrig har set en computer science træ før,

108
00:05:30,000 --> 00:05:34,000
lad mig starte med at fortælle dig, at en computer science træet vokser nedad.

109
00:05:34,000 --> 00:05:36,000
Ja, i modsætning til træer du er vant til,

110
00:05:36,000 --> 00:05:38,000
roden af ​​en computer science træ er øverst,

111
00:05:38,000 --> 00:05:41,000
og bladene er i bunden.

112
00:05:41,000 --> 00:05:45,000
Hver lille boks kaldes en knude, og knuderne er forbundet med hinanden ved kanterne.

113
00:05:45,000 --> 00:05:48,000
Så roden af ​​dette træ er et knudepunkt værdi med værdien 13,

114
00:05:48,000 --> 00:05:52,000
der har 2 børn noder med værdierne 5 og 34 år.

115
00:05:52,000 --> 00:05:57,000
Et undertræ er træet, der dannes blot ved at kigge på en underafdeling af hele træet.

116
00:05:57,000 --> 00:06:03,000
>> For eksempel er den venstre undertræ af knudepunktet 3 træet skabt af knudepunkterne 0, 1 og 2.

117
00:06:03,000 --> 00:06:06,000
Så hvis vi går tilbage til egenskaberne af en binær søgning træ,

118
00:06:06,000 --> 00:06:09,000
vi se, at hver node i træet i overensstemmelse med alle 3 ejendomme, nemlig,

119
00:06:09,000 --> 00:06:15,000
den venstre undertræ kun indeholder værdier, der er mindre end eller lig med knudepunktet værdi;

120
00:06:15,000 --> 00:06:16,000
ret undertræ over alle emner

121
00:06:16,000 --> 00:06:19,000
kun indeholder værdier, der er større end eller lig med knudepunktet værdi, og

122
00:06:19,000 --> 00:06:25,000
både venstre og højre undertræer af alle knuder også er binære søgetræer.

123
00:06:25,000 --> 00:06:28,000
Selv om dette træ ser anderledes ud, dette er en gyldig binær søgning tree

124
00:06:28,000 --> 00:06:30,000
for det samme sæt af numre.

125
00:06:30,000 --> 00:06:32,000
Som en kendsgerning, er der mange mulige måder, du kan oprette

126
00:06:32,000 --> 00:06:35,000
en gyldig binær søgning træ fra disse numre.

127
00:06:35,000 --> 00:06:38,000
Nå, lad os gå tilbage til den første, vi har oprettet.

128
00:06:38,000 --> 00:06:40,000
Så hvad kan vi gøre med disse træer?

129
00:06:40,000 --> 00:06:44,000
Nå, kan vi ganske enkelt finde minimum og maksimum værdier.

130
00:06:44,000 --> 00:06:46,000
Minimumsværdierne findes ved altid at gå mod venstre

131
00:06:46,000 --> 00:06:48,000
indtil der ikke er flere knuder at besøge.

132
00:06:48,000 --> 00:06:53,000
Omvendt at finde den maksimalt en simpelthen bare går ned til højre på hver gang.

133
00:06:54,000 --> 00:06:56,000
>> Finde et andet nummer, der ikke er minimum eller maksimum

134
00:06:56,000 --> 00:06:58,000
er lige så nemt.

135
00:06:58,000 --> 00:07:00,000
Siger, at vi leder efter nummeret 89.

136
00:07:00,000 --> 00:07:03,000
Vi har simpelthen kontrollere værdien af ​​hver node og gå til venstre eller højre,

137
00:07:03,000 --> 00:07:06,000
afhængigt af om knudens værdi er mindre end eller større end

138
00:07:06,000 --> 00:07:08,000
den vi leder efter.

139
00:07:08,000 --> 00:07:11,000
Så starter ved roden af ​​13, ser vi, at 89 er større,

140
00:07:11,000 --> 00:07:13,000
og så går vi til højre.

141
00:07:13,000 --> 00:07:16,000
Så vi ser node for 34, og vi igen gå til højre.

142
00:07:16,000 --> 00:07:20,000
89 er stadig større end 55, så fortsætter vi gå til højre.

143
00:07:20,000 --> 00:07:24,000
Vi derefter komme med en node med værdien af ​​144 og gå til venstre.

144
00:07:24,000 --> 00:07:26,000
Lo og beskue, 89 er lige der.

145
00:07:26,000 --> 00:07:31,000
>> En anden ting, vi kan gøre, er at udskrive alle numre ved at udføre en inorder traversal.

146
00:07:31,000 --> 00:07:35,000
En inorder traversal betyder at udskrive alt ud i venstre undertræ

147
00:07:35,000 --> 00:07:37,000
efterfulgt af trykning knudepunktet selv

148
00:07:37,000 --> 00:07:40,000
og derefter efterfulgt af trykning alt ud i højre undertræ.

149
00:07:40,000 --> 00:07:43,000
For eksempel, lad os tage vores foretrukne binær søgning træ

150
00:07:43,000 --> 00:07:46,000
og udskrive tallene i sorteret orden.

151
00:07:46,000 --> 00:07:49,000
Vi starter ved roden af ​​13, men inden udskrivning 13 vi er nødt til at udskrive

152
00:07:49,000 --> 00:07:51,000
alt i venstre undertræ.

153
00:07:51,000 --> 00:07:55,000
Så vi går til 5. Vi har stadig nødt til at gå dybere ned i træet, indtil vi finder den længst til venstre knudepunkt,

154
00:07:55,000 --> 00:07:57,000
hvilket er nul.

155
00:07:57,000 --> 00:08:00,000
Efter udskrivning nul, går vi tilbage op til 1, og udskrive denne ud.

156
00:08:00,000 --> 00:08:03,000
Så går vi til højre undertræ, der er 2, og udskrive det ud.

157
00:08:03,000 --> 00:08:05,000
Nu, hvor vi er færdig med at undertræ,

158
00:08:05,000 --> 00:08:07,000
vi kan gå tilbage op til 3, og printe det ud.

159
00:08:07,000 --> 00:08:11,000
Fortsætter op igen, vi udskriver 5 og derefter 8.

160
00:08:11,000 --> 00:08:13,000
Nu, hvor vi har afsluttet hele venstre undertræ,

161
00:08:13,000 --> 00:08:17,000
vi kan printe ud de 13 og begynde at arbejde på højre undertræ.

162
00:08:17,000 --> 00:08:21,000
Vi hopper ned til 34, men inden udskrivning 34 vi er nødt til at udskrive sin venstre undertræ.

163
00:08:21,000 --> 00:08:27,000
Så vi udskrive 21, så vi kommer til at printe ud 34 og besøge sin ret undertræ.

164
00:08:27,000 --> 00:08:31,000
Siden 55 har ikke nogen venstre undertræ, vi printe den ud og fortsætte til sin ret undertræ.

165
00:08:31,000 --> 00:08:36,000
144 har en venstre undertræ, og så vi udskrive 89, efterfulgt af 144,

166
00:08:36,000 --> 00:08:39,000
og endelig den yderste højre knudepunkt 233.

167
00:08:39,000 --> 00:08:44,000
Der har du det, alle de tal udskrives i rækkefølge fra laveste til højeste.

168
00:08:44,000 --> 00:08:47,000
>> Tilføjelse noget til træet er relativt smertefri så godt.

169
00:08:47,000 --> 00:08:51,000
Alt, hvad vi skal gøre, er at sikre, at vi følger 3 binære søgetræ egenskaber

170
00:08:51,000 --> 00:08:53,000
og derefter indsætte den værdi, hvor der er plads.

171
00:08:53,000 --> 00:08:55,000
Lad os sige, at vi ønsker at indsætte værdien af ​​7.

172
00:08:55,000 --> 00:08:58,000
Siden 7 er mindre end 13, vi går til venstre.

173
00:08:58,000 --> 00:09:01,000
Men det er større end 5, så vi krydser til højre.

174
00:09:01,000 --> 00:09:04,000
Da det er mindre end 8 og 8 er et blad node, tilføjer vi 7 til venstre barn af 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Vi har tilføjet en række til vores binær søgning træ.

176
00:09:09,000 --> 00:09:12,000
>> Hvis vi kan tilføje ting, vi bedre kunne slette tingene så godt.

177
00:09:12,000 --> 00:09:14,000
Desværre for os, sletning er en lille smule mere kompliceret -

178
00:09:14,000 --> 00:09:16,000
ikke meget, men bare en lille smule.

179
00:09:16,000 --> 00:09:18,000
Der er 3 forskellige scenarier, som vi er nødt til at overveje

180
00:09:18,000 --> 00:09:21,000
når du sletter elementer fra binære søgetræer.

181
00:09:21,000 --> 00:09:24,000
For det første er den letteste sagen er, at elementet er et blad node.

182
00:09:24,000 --> 00:09:27,000
I dette tilfælde, skal du blot sletter vi det og gå videre med vores forretning.

183
00:09:27,000 --> 00:09:30,000
Sige at vi vil slette de 7, som vi lige har tilføjet.

184
00:09:30,000 --> 00:09:34,000
Tja, vi simpelthen finde det, fjerne det, og det er det.

185
00:09:35,000 --> 00:09:37,000
Den næste sag er, hvis knudepunkt har kun 1 barn.

186
00:09:37,000 --> 00:09:40,000
Her kan vi slette den knude, men vi først nødt til at sørge

187
00:09:40,000 --> 00:09:42,000
at forbinde undertræ der er nu overladt forældreløse

188
00:09:42,000 --> 00:09:44,000
til den forælder af den node vi netop slettet.

189
00:09:44,000 --> 00:09:47,000
Sige at vi vil slette 3 fra vores træ.

190
00:09:47,000 --> 00:09:50,000
Vi tager barnet element i denne knude, og fastgør den til den forælder, for node.

191
00:09:50,000 --> 00:09:54,000
I dette tilfælde vil vi nu fastgørelse af 1 til 5.

192
00:09:54,000 --> 00:09:57,000
Dette fungerer uden problemer, fordi vi ved, ifølge den binære søgetræ egenskaben,

193
00:09:57,000 --> 00:10:01,000
at alt i den venstre undertræ af 3 var mindre end 5.

194
00:10:01,000 --> 00:10:05,000
Nu, 3 's undertræ er taget sig af, kan vi slette det.

195
00:10:05,000 --> 00:10:08,000
Den tredje og sidste sag er den mest komplekse.

196
00:10:08,000 --> 00:10:11,000
Dette er tilfældet, når knuden vi ønsker at slette har 2 børn.

197
00:10:11,000 --> 00:10:15,000
For at kunne gøre dette, skal vi først nødt til at finde den knude, der har den næststørste værdi,

198
00:10:15,000 --> 00:10:18,000
bytte de to, og derefter slette den node i spørgsmålet.

199
00:10:18,000 --> 00:10:22,000
Bemærk den knude, der har den næststørste værdi kan ikke have 2 børn selv

200
00:10:22,000 --> 00:10:26,000
siden den venstre barn ville være en bedre kandidat til den næststørste.

201
00:10:26,000 --> 00:10:30,000
Derfor sletter en node med 2 børn svarer til swapping af 2 knuder,

202
00:10:30,000 --> 00:10:33,000
og derefter slette varetages af 1 af de 2 førnævnte regler.

203
00:10:33,000 --> 00:10:37,000
For eksempel sige, lad os vi ønsker at slette roden node, 13.

204
00:10:37,000 --> 00:10:39,000
Det første vi gør, er at vi finder den næststørste værdi i træet

205
00:10:39,000 --> 00:10:41,000
som i dette tilfælde er 21.

206
00:10:41,000 --> 00:10:46,000
Vi så bytte de 2 knuder, hvilket gør 13 et blad og 21 den centrale gruppe node.

207
00:10:46,000 --> 00:10:49,000
Nu kan vi blot slette 13.

208
00:10:50,000 --> 00:10:53,000
>> Som omtalt tidligere, er der mange muligheder for at gøre en gyldig binær søgning træ.

209
00:10:53,000 --> 00:10:56,000
Desværre for os, nogle er værre end andre.

210
00:10:56,000 --> 00:10:59,000
For eksempel sker det, når vi bygger et binært søgetræ

211
00:10:59,000 --> 00:11:01,000
fra en sorteret liste over numre?

212
00:11:01,000 --> 00:11:04,000
Alle numre er lige tilføjet til højre på hvert trin.

213
00:11:04,000 --> 00:11:06,000
Når vi ønsker at søge efter et nummer,

214
00:11:06,000 --> 00:11:08,000
vi har ikke noget valg, men kun for at se på højre ved hvert trin.

215
00:11:08,000 --> 00:11:11,000
Dette er ikke bedre end lineær søgning på alle.

216
00:11:11,000 --> 00:11:13,000
Selv om vi ikke vil dække dem her, der er andre, mere komplekse,

217
00:11:13,000 --> 00:11:16,000
datastrukturer, der gør sikker på, at dette ikke sker.

218
00:11:16,000 --> 00:11:18,000
Men en enkelt ting, der kan gøres for at undgå dette er

219
00:11:18,000 --> 00:11:21,000
til bare tilfældigt shuffle inputværdierne.

220
00:11:21,000 --> 00:11:26,000
Det er højst usandsynligt, at ved tilfældig chance en blandet liste af tal er sorteret.

221
00:11:26,000 --> 00:11:29,000
Hvis dette var tilfældet, ville kasinoer ikke bo i business for længe.

222
00:11:29,000 --> 00:11:31,000
>> Der har du det.

223
00:11:31,000 --> 00:11:34,000
Nu ved du om binær søgning og binær søgning træer.

224
00:11:34,000 --> 00:11:36,000
Jeg Patrick Schmid, og dette er CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
En oplagt måde ville være at scanne listen fra ... [bip]

227
00:11:43,000 --> 00:11:46,000
... Antallet af elementer ... yep

228
00:11:46,000 --> 00:11:50,000
[Griner]

229
00:11:50,000 --> 00:11:55,000
... Sende knudepunkt 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Det var -