1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary 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 ga deg en liste over Disney karakter navn i alfabetisk rekkefølge

5
00:00:09,000 --> 00:00:11,000
og ba deg om å finne Mikke Mus,

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

7
00:00:13,000 --> 00:00:15,000
En åpenbar måte ville være å skanne listen fra begynnelsen

8
00:00:15,000 --> 00:00:18,000
og sjekk alle navn for å se om det er Mickey.

9
00:00:18,000 --> 00:00:22,000
Men som du leser Aladdin, Alice, Ariel, og så videre,

10
00:00:22,000 --> 00:00:25,000
du vil raskt innse at du starter på forsiden av listen var ikke en god idé.

11
00:00:25,000 --> 00:00:29,000
Ok, kanskje du burde begynne å jobbe bakover fra slutten av listen.

12
00:00:29,000 --> 00:00:33,000
Nå kan du lese Tarzan, Stitch, Snow White, og så videre.

13
00:00:33,000 --> 00:00:36,000
Likevel, dette ikke virke som den beste måten å gå om det.

14
00:00:36,000 --> 00:00:38,000
>> Vel, er en annen måte at du kan gå om du gjør dette for å prøve å innskrenke

15
00:00:38,000 --> 00:00:41,000
listen over navn som du må se på.

16
00:00:41,000 --> 00:00:43,000
Siden du vet at de er i alfabetisk rekkefølge,

17
00:00:43,000 --> 00:00:45,000
du kan bare se på navnene i midten av listen

18
00:00:45,000 --> 00:00:49,000
og sjekk om Mikke Mus er før eller etter dette navnet.

19
00:00:49,000 --> 00:00:51,000
Ser på etternavnet i den andre kolonnen

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

21
00:00:54,000 --> 00:00:57,000
så du vil rett og slett ignorere første halvdel av listen.

22
00:00:57,000 --> 00:00:59,000
Så du vil nok se på toppen av den siste kolonnen

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

24
00:01:02,000 --> 00:01:06,000
Mickey kommer før Rapunzel, ser ut som vi kan ignorere den siste kolonnen i tillegg.

25
00:01:06,000 --> 00:01:08,000
Fortsetter søk strategi, vil du raskt se at Mickey

26
00:01:08,000 --> 00:01:11,000
er i den første halvdel av den gjenværende navneliste

27
00:01:11,000 --> 00:01:14,000
og til slutt finne Mikke gjemmer mellom Merlin og Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Hva du har gjort var i utgangspunktet binære søk.

29
00:01:17,000 --> 00:01:22,000
Som dette navnet tilsier, utfører den sin søking strategi i en binær sak.

30
00:01:22,000 --> 00:01:24,000
Hva betyr dette?

31
00:01:24,000 --> 00:01:27,000
Vel, gitt en liste over sorterte elementene, gjør det binære søk algoritme en binær beslutning -

32
00:01:27,000 --> 00:01:33,000
venstre eller høyre, som er større enn eller mindre enn, alfabetisk før eller etter - ved hvert punkt.

33
00:01:33,000 --> 00:01:35,000
Nå som vi har et navn som går langs med dette søket algoritmen,

34
00:01:35,000 --> 00:01:38,000
la oss se på et annet eksempel, men denne gangen med en liste over sortert tall.

35
00:01:38,000 --> 00:01:43,000
Si er vi på jakt etter nummeret 144 i denne listen over sortert tall.

36
00:01:43,000 --> 00:01:46,000
Akkurat som før, finner vi tall som er i midten -

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

38
00:01:50,000 --> 00:01:54,000
Siden det er klart større enn 13, kan vi se bort fra alt som er 13 eller mindre

39
00:01:54,000 --> 00:01:57,000
og bare konsentrere seg om den andre halvparten.

40
00:01:57,000 --> 00:01:59,000
Siden vi nå har et likt antall elementer igjen,

41
00:01:59,000 --> 00:02:01,000
vi bare velge et tall som er nær midten.

42
00:02:01,000 --> 00:02:03,000
I dette tilfellet velger vi 55.

43
00:02:03,000 --> 00:02:06,000
Vi kunne ha like lett valgt 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Igjen er 144 høyere enn 55, så vi går til høyre.

45
00:02:11,000 --> 00:02:14,000
Heldigvis for oss, er neste midterste tallet 144,

46
00:02:14,000 --> 00:02:16,000
den vi leter etter.

47
00:02:16,000 --> 00:02:21,000
Så for å finne 144 med et binært søk, er vi i stand til å finne den i kun 3 trinn.

48
00:02:21,000 --> 00:02:24,000
Hvis vi ville ha brukt lineær søk her, ville det ha tatt oss 12 trinn.

49
00:02:24,000 --> 00:02:28,000
Som et faktisk, siden denne søkemetode halverer antall elementer

50
00:02:28,000 --> 00:02:31,000
det har å se på hvert trinn, vil det finne elementet den søker etter

51
00:02:31,000 --> 00:02:35,000
i om loggen av antall elementer i listen.

52
00:02:35,000 --> 00:02:37,000
Nå som vi har sett to eksempler, la oss ta en titt på

53
00:02:37,000 --> 00:02:41,000
noen pseudokode for en rekursiv funksjon som implementerer binære søk.

54
00:02:41,000 --> 00:02:44,000
Starter på toppen, ser vi at vi må finne en funksjon som tar 4 argumenter:

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

56
00:02:47,000 --> 00:02:51,000
Nøkkelen er nummeret som vi leter etter, så 144 i forrige eksempel.

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

58
00:02:54,000 --> 00:02:57,000
Min og maks er indeksene for de laveste og høyeste posisjoner

59
00:02:57,000 --> 00:02:59,000
at vi nå ser på.

60
00:02:59,000 --> 00:03:03,000
Så når vi starter, vil min være null og maks vil være den maksimale indeksverdien av tabellen.

61
00:03:03,000 --> 00:03:07,000
Som vi begrense søket ned, vil vi oppdatere min og maks

62
00:03:07,000 --> 00:03:10,000
å være nettopp det området som vi fortsatt ser i.

63
00:03:10,000 --> 00:03:12,000
>> La oss hoppe til den interessante delen først.

64
00:03:12,000 --> 00:03:14,000
Det første vi gjør er å finne midtpunktet,

65
00:03:14,000 --> 00:03:19,000
indeksen som ligger halvveis mellom min og maks av tabellen at vi fortsatt vurderer.

66
00:03:19,000 --> 00:03:22,000
Så vi ser på verdien av tabellen på det midtpunktet sted

67
00:03:22,000 --> 00:03:25,000
og se om det tallet vi leter etter er mindre enn den tasten.

68
00:03:25,000 --> 00:03:27,000
Hvis nummeret på den posisjonen er mindre,

69
00:03:27,000 --> 00:03:31,000
så det betyr at nøkkelen er større enn alle tallene til venstre for den posisjonen.

70
00:03:31,000 --> 00:03:33,000
Så vi kan kalle binært søkefunksjonen igjen,

71
00:03:33,000 --> 00:03:36,000
men denne gangen oppdatere min-parametere for å lese bare halvparten

72
00:03:36,000 --> 00:03:40,000
som er større enn eller lik verdien vi bare sett på.

73
00:03:40,000 --> 00:03:44,000
På den annen side, hvis nøkkelen er mindre enn tallet i den gjeldende midtpunktet av tabellen,

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

75
00:03:47,000 --> 00:03:52,000
Igjen, vi kaller binært søk, men denne gangen med et utvalg av min og maks oppdatert

76
00:03:52,000 --> 00:03:54,000
å inkludere bare den nedre halvdel.

77
00:03:54,000 --> 00:03:57,000
Hvis verdien ved gjeldende midtpunktet i matrisen er verken

78
00:03:57,000 --> 00:04:01,000
større enn eller mindre enn nøkkelen, så det må være lik nøkkelen.

79
00:04:01,000 --> 00:04:05,000
Dermed kan vi bare returnere gjeldende midtpunktet indeksen, og vi er ferdige.

80
00:04:05,000 --> 00:04:09,000
Endelig er denne sjekken her for saken at antall

81
00:04:09,000 --> 00:04:11,000
er faktisk ikke i rekken av tall vi søker.

82
00:04:11,000 --> 00:04:14,000
Hvis den maksimale indeksverdien i området som vi leter etter

83
00:04:14,000 --> 00:04:17,000
er stadig mindre enn den minste, betyr det at vi har gått for langt.

84
00:04:17,000 --> 00:04:20,000
Siden antallet var ikke i input array, returnerer vi -1

85
00:04:20,000 --> 00:04:24,000
å indikere at ingenting ble funnet.

86
00:04:24,000 --> 00:04:26,000
>> Du har kanskje lagt merke til at for denne algoritmen skal fungere,

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

88
00:04:28,000 --> 00:04:31,000
Med andre ord, kan vi bare finne 144 med binære søk

89
00:04:31,000 --> 00:04:34,000
hvis alle numrene er bestilt fra laveste til høyeste.

90
00:04:34,000 --> 00:04:38,000
Hvis dette ikke var tilfelle, ville vi ikke være i stand til å utelukke halvparten av tallene på hvert trinn.

91
00:04:38,000 --> 00:04:40,000
Så vi har to alternativer.

92
00:04:40,000 --> 00:04:43,000
Enten kan vi ta en usortert liste og sortere det før du bruker binære søk,

93
00:04:43,000 --> 00:04:48,000
eller vi kan sørge for at listen over numre er sortert som vi legger tallene til det.

94
00:04:48,000 --> 00:04:50,000
Derfor, i stedet for å sortere akkurat når vi må søke,

95
00:04:50,000 --> 00:04:53,000
hvorfor ikke holde listen sortert til alle tider?

96
00:04:53,000 --> 00:04:57,000
>> En måte å holde en liste med tall sorteres samtidig gi

97
00:04:57,000 --> 00:04:59,000
en å legge til eller flytte tall fra denne listen

98
00:04:59,000 --> 00:05:02,000
er ved hjelp av noe som kalles et binært søketre.

99
00:05:02,000 --> 00:05:05,000
En binært søketre er en datastruktur som har 3 egenskaper.

100
00:05:05,000 --> 00:05:09,000
Først, inneholder den venstre subtre av enhver node bare verdier som er mindre enn

101
00:05:09,000 --> 00:05:11,000
eller lik noden verdi.

102
00:05:11,000 --> 00:05:15,000
Sekund, inneholder riktig undertreet av en node bare verdier som er større enn

103
00:05:15,000 --> 00:05:17,000
eller lik noden verdi.

104
00:05:17,000 --> 00:05:20,000
Og til slutt, både venstre og høyre undertreene av alle noder

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

106
00:05:23,000 --> 00:05:26,000
La oss se på et eksempel med de samme tallene vi brukte tidligere.

107
00:05:26,000 --> 00:05:30,000
For de av dere som aldri har sett en datamaskin science treet før,

108
00:05:30,000 --> 00:05:34,000
la meg begynne med å fortelle deg at en datavitenskap treet vokser nedover.

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

110
00:05:36,000 --> 00:05:38,000
roten av en datamaskin science treet er på toppen,

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

112
00:05:41,000 --> 00:05:45,000
Hver lille boksen kalles en node, og nodene er koblet til hverandre ved kantene.

113
00:05:45,000 --> 00:05:48,000
Så roten av dette treet er en node verdi med verdien 13,

114
00:05:48,000 --> 00:05:52,000
som har 2 barn noder med verdiene 5 og 34.

115
00:05:52,000 --> 00:05:57,000
Et undertre er det treet som er dannet bare ved å se på en underdel av hele treet.

116
00:05:57,000 --> 00:06:03,000
>> For eksempel, er den venstre undertreet av node 3 treet skapt av nodene 0, 1 og 2.

117
00:06:03,000 --> 00:06:06,000
Så, hvis vi går tilbake til egenskapene til et binært søketre,

118
00:06:06,000 --> 00:06:09,000
vi ser at hver node i treet i samsvar med alle tre egenskaper, nemlig,

119
00:06:09,000 --> 00:06:15,000
venstre undertreet inneholder bare verdier som er mindre enn eller lik til noden verdi;

120
00:06:15,000 --> 00:06:16,000
rett undertreet av alle noder

121
00:06:16,000 --> 00:06:19,000
bare inneholder verdier som er større enn eller lik til noden verdi, og

122
00:06:19,000 --> 00:06:25,000
både venstre og høyre undertreene av alle noder også er binære search trær.

123
00:06:25,000 --> 00:06:28,000
Selv om dette treet ser annerledes ut, er dette en gyldig binært søketre

124
00:06:28,000 --> 00:06:30,000
for samme sett med tall.

125
00:06:30,000 --> 00:06:32,000
Som et spørsmål om faktum, det er mange mulige måter du kan lage

126
00:06:32,000 --> 00:06:35,000
gyldig binært søketre fra disse tallene.

127
00:06:35,000 --> 00:06:38,000
Vel, la oss gå tilbake til den første som vi har skapt.

128
00:06:38,000 --> 00:06:40,000
Så hva kan vi gjøre med disse trærne?

129
00:06:40,000 --> 00:06:44,000
Vel, vi kan veldig enkelt finne minimums-og maksimumsverdier.

130
00:06:44,000 --> 00:06:46,000
Minimumsverdiene kan bli funnet ved alltid å gå til venstre

131
00:06:46,000 --> 00:06:48,000
til det ikke er flere noder å besøke.

132
00:06:48,000 --> 00:06:53,000
Omvendt, for å finne den maksimale en rett og slett bare går ned til høyre på hver gang.

133
00:06:54,000 --> 00:06:56,000
>> Finne et annet nummer som ikke er minimum eller maksimum

134
00:06:56,000 --> 00:06:58,000
er like enkelt.

135
00:06:58,000 --> 00:07:00,000
Si at vi leter etter nummer 89.

136
00:07:00,000 --> 00:07:03,000
Vi bare sjekke verdien av hver node og gå til venstre eller høyre,

137
00:07:03,000 --> 00:07:06,000
avhengig av om noden verdi er mindre enn eller større enn

138
00:07:06,000 --> 00:07:08,000
den vi leter etter.

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

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

141
00:07:13,000 --> 00:07:16,000
Da ser vi noden for 34, og igjen vi går til høyre.

142
00:07:16,000 --> 00:07:20,000
89 er fortsatt større enn 55, så vi fortsetter å gå til høyre.

143
00:07:20,000 --> 00:07:24,000
Vi deretter komme opp med en node med verdien 144 og gå til venstre.

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

145
00:07:26,000 --> 00:07:31,000
>> En annen ting som vi kan gjøre er å skrive ut alle tallene ved å utføre en inorder traversering.

146
00:07:31,000 --> 00:07:35,000
En inorder traversering betyr å skrive alt ut i venstre subtre

147
00:07:35,000 --> 00:07:37,000
etterfulgt ved å skrive noden selv

148
00:07:37,000 --> 00:07:40,000
og deretter fulgt ved å skrive alt ut i riktig subtre.

149
00:07:40,000 --> 00:07:43,000
For eksempel, la oss ta vår favoritt binært søketre

150
00:07:43,000 --> 00:07:46,000
og skrive ut tallene i sortert rekkefølge.

151
00:07:46,000 --> 00:07:49,000
Vi starter ved roten av 13, men før utskrift 13 må vi skrive ut

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

153
00:07:51,000 --> 00:07:55,000
Så vi går til 5. Vi har fortsatt å gå dypere ned i treet til vi finner lengst til venstre node,

154
00:07:55,000 --> 00:07:57,000
som er null.

155
00:07:57,000 --> 00:08:00,000
Etter utskrift null, går vi tilbake til en og skrive det ut.

156
00:08:00,000 --> 00:08:03,000
Så går vi til høyre subtre, som er 2, og skrive det ut.

157
00:08:03,000 --> 00:08:05,000
Nå som vi er ferdig med det undertre,

158
00:08:05,000 --> 00:08:07,000
vi kan gå tilbake til 3 og skrive det ut.

159
00:08:07,000 --> 00:08:11,000
Fortsetter opp igjen, skriver vi 5 og deretter 8.

160
00:08:11,000 --> 00:08:13,000
Nå som vi har fullført hele venstre undertre,

161
00:08:13,000 --> 00:08:17,000
Vi kan skrive ut 13 og begynne å jobbe på høyre subtre.

162
00:08:17,000 --> 00:08:21,000
Vi hoppe ned til 34, men før utskrift 34 må vi skrive ut sin venstre subtre.

163
00:08:21,000 --> 00:08:27,000
Så vi skrive ut 21, så vi kommer til å skrive ut 34 og besøke sin rett subtre.

164
00:08:27,000 --> 00:08:31,000
Siden 55 har ingen venstre subtre, skriver vi det ut og fortsette videre til sin rett subtre.

165
00:08:31,000 --> 00:08:36,000
144 har en venstre subtre, og så vi skrive ut 89, etterfulgt av 144,

166
00:08:36,000 --> 00:08:39,000
og til slutt lengst til høyre node av 233.

167
00:08:39,000 --> 00:08:44,000
Det du har det, alle numrene er skrevet ut i rekkefølge fra laveste til høyeste.

168
00:08:44,000 --> 00:08:47,000
>> Legge noe til treet er relativt smertefri også.

169
00:08:47,000 --> 00:08:51,000
Alt vi trenger å gjøre er å sørge for at vi følger tre binære søketre egenskaper

170
00:08:51,000 --> 00:08:53,000
og deretter sette verdien der det er plass.

171
00:08:53,000 --> 00:08:55,000
La oss si vi ønsker å sette verdien av 7.

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

173
00:08:58,000 --> 00:09:01,000
Men den er større enn 5, slik at vi traversere til høyre.

174
00:09:01,000 --> 00:09:04,000
Siden det er mindre enn 8 og 8 er et blad node, legger vi 7 til venstre barn av 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Vi har lagt til et tall til vår binært søketre.

176
00:09:09,000 --> 00:09:12,000
>> Hvis vi kan legge til ting, vi bedre være i stand til å slette ting også.

177
00:09:12,000 --> 00:09:14,000
Dessverre for oss, er å slette en litt mer komplisert -

178
00:09:14,000 --> 00:09:16,000
ikke mye, men bare litt.

179
00:09:16,000 --> 00:09:18,000
Det er 3 forskjellige scenarier som vi må vurdere

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

181
00:09:21,000 --> 00:09:24,000
Først, er den enkleste tilfelle at elementet er en bladnoden.

182
00:09:24,000 --> 00:09:27,000
I dette tilfellet, vi bare slette det og gå videre med vår virksomhet.

183
00:09:27,000 --> 00:09:30,000
Si at vi ønsker å slette 7 som vi nettopp har lagt.

184
00:09:30,000 --> 00:09:34,000
Vel, vi bare finne den, ta den, og det er det.

185
00:09:35,000 --> 00:09:37,000
Den neste tilfelle er hvis noden har bare 1 barn.

186
00:09:37,000 --> 00:09:40,000
Her kan vi slette noden, men vi må først sørge for

187
00:09:40,000 --> 00:09:42,000
å koble subtre som nå igjen foreldreløse

188
00:09:42,000 --> 00:09:44,000
til den overordnede av noden vi bare slettet.

189
00:09:44,000 --> 00:09:47,000
Si at vi ønsker å slette 3 fra treet vårt.

190
00:09:47,000 --> 00:09:50,000
Vi tar barnet element av at node og fest den til den overordnede av noden.

191
00:09:50,000 --> 00:09:54,000
I dette tilfellet, er vi nå feste en til 5.

192
00:09:54,000 --> 00:09:57,000
Dette fungerer uten problem fordi vi vet, ifølge binært søketre eiendom,

193
00:09:57,000 --> 00:10:01,000
at alt i venstre subtre av 3 var mindre enn 5.

194
00:10:01,000 --> 00:10:05,000
Nå som 3 sin subtre er tatt vare på, kan vi slette det.

195
00:10:05,000 --> 00:10:08,000
Den tredje og siste tilfellet er det mest komplekse.

196
00:10:08,000 --> 00:10:11,000
Dette er tilfelle når noden vi ønsker å slette har 2 barn.

197
00:10:11,000 --> 00:10:15,000
For å gjøre dette, må vi først finne noden som har den nest største verdien,

198
00:10:15,000 --> 00:10:18,000
bytte de to, og deretter slette noden i spørsmålet.

199
00:10:18,000 --> 00:10:22,000
Legg merke til noden som har den nest største verdien kan ikke ha to barn selv

200
00:10:22,000 --> 00:10:26,000
siden dens venstre barnet ville være en bedre kandidat for den nest største.

201
00:10:26,000 --> 00:10:30,000
Derfor slette en node med to barn utgjør bytting av to noder,

202
00:10:30,000 --> 00:10:33,000
og deretter slette håndteres av en av de to nevnte regler.

203
00:10:33,000 --> 00:10:37,000
For eksempel, la oss si at vi ønsker å slette rotnoden, 13 år.

204
00:10:37,000 --> 00:10:39,000
Det første vi gjør er vi finne den neste største verdien i treet

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

206
00:10:41,000 --> 00:10:46,000
Vi deretter bytte de to noder, noe som gjør 13 a leaf og 21 den sentrale gruppen node.

207
00:10:46,000 --> 00:10:49,000
Nå kan vi bare slette 13.

208
00:10:50,000 --> 00:10:53,000
>> Som antydet tidligere, er det mange mulige måter å gjøre en gyldig binært søketre.

209
00:10:53,000 --> 00:10:56,000
Dessverre for oss, noen er verre enn andre.

210
00:10:56,000 --> 00:10:59,000
For eksempel, hva skjer når vi bygger et binært søketre

211
00:10:59,000 --> 00:11:01,000
fra en sortert liste med tall?

212
00:11:01,000 --> 00:11:04,000
Alle tall er bare lagt til rette på hvert trinn.

213
00:11:04,000 --> 00:11:06,000
Når vi ønsker å søke etter et nummer,

214
00:11:06,000 --> 00:11:08,000
Vi har ikke noe valg, men bare for å se på høyre på hvert trinn.

215
00:11:08,000 --> 00:11:11,000
Dette er ikke bedre enn lineær søkefunksjon.

216
00:11:11,000 --> 00:11:13,000
Selv om vi ikke vil dekke dem her, det finnes andre, mer komplekse,

217
00:11:13,000 --> 00:11:16,000
datastrukturer som gjør at dette ikke skjer.

218
00:11:16,000 --> 00:11:18,000
Det er imidlertid en enkel ting som kan gjøres for å unngå dette

219
00:11:18,000 --> 00:11:21,000
å bare tilfeldig shuffle beregningene.

220
00:11:21,000 --> 00:11:26,000
Det er svært usannsynlig at ved tilfeldige en stokket liste med tall er sortert.

221
00:11:26,000 --> 00:11:29,000
Hvis dette var tilfelle, ville kasinoer ikke bo i virksomheten for lenge.

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

223
00:11:31,000 --> 00:11:34,000
Du vet nå om binær søking og binære søk trær.

224
00:11:34,000 --> 00:11:36,000
Jeg er 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 åpenbar måte ville være å skanne listen fra ... [pip]

227
00:11:43,000 --> 00:11:46,000
... Antall elementer ... Jepp

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

229
00:11:50,000 --> 00:11:55,000
... Legge noden 234 ... augh.

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