1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binär sökning]

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

3
00:00:04,000 --> 00:00:07,000
[Detta är CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Om jag gav dig en lista med Disney tecken namn i alfabetisk ordning

5
00:00:09,000 --> 00:00:11,000
och bad dig att hitta Musse Pigg,

6
00:00:11,000 --> 00:00:13,000
hur skulle du gå om att göra detta?

7
00:00:13,000 --> 00:00:15,000
Ett självklart sätt skulle vara att skanna listan från början

8
00:00:15,000 --> 00:00:18,000
och kontrollera varje namn för att se om det är Mickey.

9
00:00:18,000 --> 00:00:22,000
Men när du läser Aladdin, Alice, Ariel, och så vidare,

10
00:00:22,000 --> 00:00:25,000
du kommer snabbt att inse att starta längst fram i listan inte var en bra idé.

11
00:00:25,000 --> 00:00:29,000
Okej, kanske du borde börja arbeta bakåt från slutet av listan.

12
00:00:29,000 --> 00:00:33,000
Nu kan du läsa Tarzan, Stitch, Snövit, och så vidare.

13
00:00:33,000 --> 00:00:36,000
Ändå verkar det inte som det bästa sättet att gå till väga.

14
00:00:36,000 --> 00:00:38,000
>> Tja, är ett annat sätt att du kan gå om att göra detta för att försöka begränsa

15
00:00:38,000 --> 00:00:41,000
listan med namn som du måste titta på.

16
00:00:41,000 --> 00:00:43,000
Eftersom du vet att de är i alfabetisk ordning,

17
00:00:43,000 --> 00:00:45,000
du kan bara titta på namnen i mitten av listan

18
00:00:45,000 --> 00:00:49,000
och kontrollera om Musse Pigg är före eller efter detta namn.

19
00:00:49,000 --> 00:00:51,000
Man tittar på efternamn i den andra kolumnen

20
00:00:51,000 --> 00:00:54,000
du skulle inse att M för Mickey kommer efter J för Jasmine,

21
00:00:54,000 --> 00:00:57,000
så du skulle helt enkelt ignorera den första halvan av listan.

22
00:00:57,000 --> 00:00:59,000
Då skulle du förmodligen titta på toppen av den sista kolumnen

23
00:00:59,000 --> 00:01:02,000
och se att det börjar med Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey kommer före Rapunzel, ser ut som vi kan ignorera den sista kolumnen också.

25
00:01:06,000 --> 00:01:08,000
Fortsatt sökstrategi, ser du snabbt att Mickey

26
00:01:08,000 --> 00:01:11,000
är i den första hälften av den återstående listan med namn

27
00:01:11,000 --> 00:01:14,000
och slutligen hitta Mickey gömmer mellan Merlin och Mimmi.

28
00:01:14,000 --> 00:01:17,000
>> Vad du gjorde var i princip binär sökning.

29
00:01:17,000 --> 00:01:22,000
Eftersom detta namn antyder, utför den sin sökning strategi i en binär fråga.

30
00:01:22,000 --> 00:01:24,000
Vad betyder det här?

31
00:01:24,000 --> 00:01:27,000
Tja, få en lista över sorterade poster, gör den binära sökalgoritmen en binär beslut -

32
00:01:27,000 --> 00:01:33,000
vänster eller höger, större än eller mindre än, alfabetiskt före eller efter - vid varje punkt.

33
00:01:33,000 --> 00:01:35,000
Nu när vi har ett namn som går längs med denna sökalgoritm,

34
00:01:35,000 --> 00:01:38,000
låt oss titta på ett annat exempel, men den här gången med en lista över sorterade nummer.

35
00:01:38,000 --> 00:01:43,000
Säg att vi letar efter numret 144 i listan över sorterade nummer.

36
00:01:43,000 --> 00:01:46,000
Precis som tidigare, finner vi det nummer som är i mitten -

37
00:01:46,000 --> 00:01:50,000
som i detta fall är 13 - och se om 144 är större än eller mindre än 13.

38
00:01:50,000 --> 00:01:54,000
Eftersom det är klart större än 13, kan vi ignorera allt som är 13 eller mindre

39
00:01:54,000 --> 00:01:57,000
och bara koncentrera sig på den återstående hälften.

40
00:01:57,000 --> 00:01:59,000
Eftersom vi nu har ett jämnt antal artiklar kvar,

41
00:01:59,000 --> 00:02:01,000
Vi väljer helt enkelt ett nummer som ligger nära mitten.

42
00:02:01,000 --> 00:02:03,000
I det här fallet väljer vi 55.

43
00:02:03,000 --> 00:02:06,000
Vi kunde ha lika lätt valt 89.

44
00:02:06,000 --> 00:02:11,000
Okej. Återigen är 144 större än 55, så vi går till höger.

45
00:02:11,000 --> 00:02:14,000
Lyckligtvis för oss, är nästa mellersta nummer 144,

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

47
00:02:16,000 --> 00:02:21,000
Så för att hitta 144 med hjälp av en binär sökning, vi kan hitta den i bara 3 steg.

48
00:02:21,000 --> 00:02:24,000
Om vi ​​skulle ha använt linjär sökning här skulle det ha tagit oss 12 steg.

49
00:02:24,000 --> 00:02:28,000
I själva verket, eftersom denna sökmetod halverar antalet objekt

50
00:02:28,000 --> 00:02:31,000
det har att titta på vid varje steg, kommer det att hitta objektet den söker efter

51
00:02:31,000 --> 00:02:35,000
ungefär i logaritmen av antalet objekt i listan.

52
00:02:35,000 --> 00:02:37,000
Nu när vi har sett 2 exempel, låt oss ta en titt på

53
00:02:37,000 --> 00:02:41,000
vissa pseudokod för en rekursiv funktion som implementerar binär sökning.

54
00:02:41,000 --> 00:02:44,000
Börjar på toppen ser vi att vi måste hitta en funktion som tar 4 argument:

55
00:02:44,000 --> 00:02:47,000
nyckel, array, min och max.

56
00:02:47,000 --> 00:02:51,000
Nyckeln är det nummer som vi söker, så 144 i föregående exempel.

57
00:02:51,000 --> 00:02:54,000
Array är en lista över nummer som vi söker.

58
00:02:54,000 --> 00:02:57,000
Min och max är index för de lägsta och högsta positioner

59
00:02:57,000 --> 00:02:59,000
att vi för närvarande tittar på.

60
00:02:59,000 --> 00:03:03,000
Så när vi börjar, kommer min vara noll och max blir den maximala indexet i arrayen.

61
00:03:03,000 --> 00:03:07,000
När vi begränsa sökningen ner kommer vi att uppdatera min och max

62
00:03:07,000 --> 00:03:10,000
bara vara det område som vi fortfarande ser i.

63
00:03:10,000 --> 00:03:12,000
>> Låt oss hoppa till den intressanta delen först.

64
00:03:12,000 --> 00:03:14,000
Det första vi gör är att hitta mittpunkten,

65
00:03:14,000 --> 00:03:19,000
det index som är halvvägs mellan min och max för den array som vi fortfarande överväger.

66
00:03:19,000 --> 00:03:22,000
Sedan tittar vi på värdet av uppsättningen på den mittpunkt plats

67
00:03:22,000 --> 00:03:25,000
och se om det antal som vi söker är mindre än den nyckeln.

68
00:03:25,000 --> 00:03:27,000
Om antalet på den positionen är mindre,

69
00:03:27,000 --> 00:03:31,000
då betyder det nyckeln är större än alla siffror till vänster om den positionen.

70
00:03:31,000 --> 00:03:33,000
Så vi kan kalla binär sökfunktionen igen,

71
00:03:33,000 --> 00:03:36,000
men denna gång uppdatera min och parametrar max för att läsa bara halv

72
00:03:36,000 --> 00:03:40,000
som är större än eller lika med det värde vi bara tittat på.

73
00:03:40,000 --> 00:03:44,000
Å andra sidan, om nyckeln är mindre än antalet vid den aktuella mittpunkten av arrayen,

74
00:03:44,000 --> 00:03:47,000
vi vill gå åt vänster och ignorera alla nummer som är större.

75
00:03:47,000 --> 00:03:52,000
Återigen, vi kallar binär sökning men denna gång med olika min och max uppdaterad

76
00:03:52,000 --> 00:03:54,000
att inkludera bara den nedre halvan.

77
00:03:54,000 --> 00:03:57,000
Om värdet vid den aktuella mittpunkten i arrayen är varken

78
00:03:57,000 --> 00:04:01,000
större än eller mindre än nyckeln, då måste det vara lika med nyckeln.

79
00:04:01,000 --> 00:04:05,000
Således kan vi återvända enkelt den aktuella mittpunkten index och vi är klara.

80
00:04:05,000 --> 00:04:09,000
Slutligen är denna kontroll här fallet att antalet

81
00:04:09,000 --> 00:04:11,000
är faktiskt inte i matris med tal som vi söker.

82
00:04:11,000 --> 00:04:14,000
Om den maximala index intervallet som vi söker

83
00:04:14,000 --> 00:04:17,000
är någonsin mindre än den minsta, innebär att vi har gått för långt.

84
00:04:17,000 --> 00:04:20,000
Eftersom antalet inte var i inputuppställningen, återvänder vi -1

85
00:04:20,000 --> 00:04:24,000
för att indikera att ingenting hittades.

86
00:04:24,000 --> 00:04:26,000
>> Du kanske har märkt att detta algoritm ska fungera,

87
00:04:26,000 --> 00:04:28,000
listan över nummer måste sorteras.

88
00:04:28,000 --> 00:04:31,000
Med andra ord kan vi bara hitta 144 med binär sökning

89
00:04:31,000 --> 00:04:34,000
om alla talen är ordnade från lägsta till högsta.

90
00:04:34,000 --> 00:04:38,000
Om detta inte vore fallet, skulle vi inte kunna utesluta hälften av siffrorna i varje steg.

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

92
00:04:40,000 --> 00:04:43,000
Antingen kan vi ta en osorterad lista och sortera den innan du använder binär sökning,

93
00:04:43,000 --> 00:04:48,000
eller så kan vi se till att listan över nummer sorteras som vi lägga till siffror till det.

94
00:04:48,000 --> 00:04:50,000
I stället för att sortera just när vi måste söka,

95
00:04:50,000 --> 00:04:53,000
varför inte hålla listan sorteras hela tiden?

96
00:04:53,000 --> 00:04:57,000
>> Ett sätt att hålla en lista med tal sorteras samtidigt tillåter

97
00:04:57,000 --> 00:04:59,000
en för att lägga till eller flytta nummer från den här listan

98
00:04:59,000 --> 00:05:02,000
är att använda något som kallas en binär sökträd.

99
00:05:02,000 --> 00:05:05,000
En binär sökträdet är en datastruktur som har 3 egenskaper.

100
00:05:05,000 --> 00:05:09,000
Det första innehåller den vänstra underträd någon nod endast värden som är mindre än

101
00:05:09,000 --> 00:05:11,000
eller lika med nodens värde.

102
00:05:11,000 --> 00:05:15,000
Det andra, innehåller rätt underträdet av en nod endast värden som är större än

103
00:05:15,000 --> 00:05:17,000
eller lika med nodens värde.

104
00:05:17,000 --> 00:05:20,000
Och slutligen både vänster och höger underträd av alla noder

105
00:05:20,000 --> 00:05:23,000
är också binära sökträd.

106
00:05:23,000 --> 00:05:26,000
Låt oss titta på ett exempel med samma nummer som vi använt tidigare.

107
00:05:26,000 --> 00:05:30,000
För dig som aldrig har sett en datavetenskap träd innan,

108
00:05:30,000 --> 00:05:34,000
Låt mig börja med att berätta att en datavetenskap träd växer nedåt.

109
00:05:34,000 --> 00:05:36,000
Ja, till skillnad från träd du är van vid,

110
00:05:36,000 --> 00:05:38,000
roten av en datavetenskap träd är överst,

111
00:05:38,000 --> 00:05:41,000
och bladen är i botten.

112
00:05:41,000 --> 00:05:45,000
Varje liten ruta kallas en nod, och noderna är förbundna med varandra genom kanterna.

113
00:05:45,000 --> 00:05:48,000
Så roten till detta träd är en nod värde med värdet 13,

114
00:05:48,000 --> 00:05:52,000
som har 2 barn noder med värdena 5 och 34.

115
00:05:52,000 --> 00:05:57,000
En underträd är trädet som bildas genom att bara titta på en underavdelning av hela trädet.

116
00:05:57,000 --> 00:06:03,000
>> Till exempel, är den vänstra underträd av noden 3 trädet skapas av noderna 0, 1, och 2.

117
00:06:03,000 --> 00:06:06,000
Så, om vi går tillbaka till egenskaperna hos en binärt sökträd,

118
00:06:06,000 --> 00:06:09,000
Vi ser att varje nod i trädet uppfyller alla 3 egenskaper, nämligen,

119
00:06:09,000 --> 00:06:15,000
vänster underträd innehåller endast värden som är mindre än eller lika med nodens värde;

120
00:06:15,000 --> 00:06:16,000
högra underträdet av alla noder

121
00:06:16,000 --> 00:06:19,000
endast innehåller värden som är större än eller lika med nodens värde, och

122
00:06:19,000 --> 00:06:25,000
både vänster och höger underträd av alla noder är också binära sökträd.

123
00:06:25,000 --> 00:06:28,000
Även detta träd ser annorlunda, är detta en giltig binärt sökträd

124
00:06:28,000 --> 00:06:30,000
för samma uppsättning siffror.

125
00:06:30,000 --> 00:06:32,000
I själva verket finns det många olika sätt som du kan skapa

126
00:06:32,000 --> 00:06:35,000
en giltig binärt sökträd från dessa siffror.

127
00:06:35,000 --> 00:06:38,000
Nåväl, låt oss gå tillbaka till den första vi skapade.

128
00:06:38,000 --> 00:06:40,000
Så vad kan vi göra med dessa träd?

129
00:06:40,000 --> 00:06:44,000
Tja, vi kan mycket enkelt hitta de lägsta och högsta värdena.

130
00:06:44,000 --> 00:06:46,000
De minimivärden kan hittas genom att alltid gå till vänster

131
00:06:46,000 --> 00:06:48,000
tills det inte finns fler noder att besöka.

132
00:06:48,000 --> 00:06:53,000
Omvänt, för att hitta den maximala ett helt enkelt går ner till höger vid varje tidpunkt.

133
00:06:54,000 --> 00:06:56,000
>> Hitta något annat nummer som inte är det minsta eller högsta

134
00:06:56,000 --> 00:06:58,000
är lika enkelt.

135
00:06:58,000 --> 00:07:00,000
Säg att vi letar efter numret 89.

136
00:07:00,000 --> 00:07:03,000
Vi kontrollerar bara värdet av varje nod och gå till vänster eller höger,

137
00:07:03,000 --> 00:07:06,000
beroende på om nodens värde är mindre än eller större än

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

139
00:07:08,000 --> 00:07:11,000
Så börjar vid roten av 13 ser vi att 89 är större,

140
00:07:11,000 --> 00:07:13,000
och så går vi till höger.

141
00:07:13,000 --> 00:07:16,000
Sedan ser vi nod för 34, och igen vi gå till höger.

142
00:07:16,000 --> 00:07:20,000
89 är fortfarande större än 55, så vi fortsätter att gå till höger.

143
00:07:20,000 --> 00:07:24,000
Vi kommer sedan upp med en nod med värdet av 144 och gå till vänster.

144
00:07:24,000 --> 00:07:26,000
Hör och häpna, 89 är rätt där.

145
00:07:26,000 --> 00:07:31,000
>> En annan sak som vi kan göra är att skriva ut alla nummer genom att utföra en inorder förflyttning.

146
00:07:31,000 --> 00:07:35,000
En inorder förflyttning innebär att skriva ut allt i den vänstra underträd

147
00:07:35,000 --> 00:07:37,000
följd av tryckning själva noden

148
00:07:37,000 --> 00:07:40,000
och sedan följt av tryckning allt ut i rätt underträd.

149
00:07:40,000 --> 00:07:43,000
Till exempel, låt oss ta vår favorit träd binär sökning

150
00:07:43,000 --> 00:07:46,000
och skriva ut numren i sorterad ordning.

151
00:07:46,000 --> 00:07:49,000
Vi börjar vid roten av 13, men innan du skriver ut 13 måste vi skriva ut

152
00:07:49,000 --> 00:07:51,000
allt i vänstra underträd.

153
00:07:51,000 --> 00:07:55,000
Så vi går till 5. Vi måste fortfarande gå djupare ner i trädet tills vi hittar längst till vänster nod,

154
00:07:55,000 --> 00:07:57,000
vilket är noll.

155
00:07:57,000 --> 00:08:00,000
Efter utskrift noll, går vi tillbaka upp till 1 och skriva ut det.

156
00:08:00,000 --> 00:08:03,000
Sen går vi åt höger underträd som är 2, och skriva ut det.

157
00:08:03,000 --> 00:08:05,000
Nu när vi är klara med det underträd,

158
00:08:05,000 --> 00:08:07,000
vi kan gå tillbaka till 3 och skriva ut den.

159
00:08:07,000 --> 00:08:11,000
Fortsätter tillbaka upp, ut vi 5 och sedan 8.

160
00:08:11,000 --> 00:08:13,000
Nu när vi har avslutat hela vänster underträd,

161
00:08:13,000 --> 00:08:17,000
Vi kan skriva ut 13 och börja arbeta på rätt underträd.

162
00:08:17,000 --> 00:08:21,000
Vi hoppa ner till 34, men innan du skriver ut 34 måste vi skriva ut sin vänstra underträd.

163
00:08:21,000 --> 00:08:27,000
Så vi skriver ut 21, då får vi skriva ut 34 och besöka sin rätt underträd.

164
00:08:27,000 --> 00:08:31,000
Sedan 55 har ingen vänstra underträd, skriva vi det och fortsätter till dess högra delträd.

165
00:08:31,000 --> 00:08:36,000
144 har en vänster underträd, så vi skriver ut 89, följt av 144,

166
00:08:36,000 --> 00:08:39,000
och slutligen längst till höger nod 233.

167
00:08:39,000 --> 00:08:44,000
Där har du det, alla nummer skrivs ut i ordning från lägsta till högsta.

168
00:08:44,000 --> 00:08:47,000
>> Lägga något till trädet är relativt smärtfritt också.

169
00:08:47,000 --> 00:08:51,000
Allt vi behöver göra är att se till att vi följer 3 binära egenskaper sökträd

170
00:08:51,000 --> 00:08:53,000
och sätt sedan in värdet där det finns utrymme.

171
00:08:53,000 --> 00:08:55,000
Låt oss säga att vi vill infoga värdet 7.

172
00:08:55,000 --> 00:08:58,000
Sedan 7 är mindre än 13, går vi till vänster.

173
00:08:58,000 --> 00:09:01,000
Men det är större än 5, så vi korsar till höger.

174
00:09:01,000 --> 00:09:04,000
Eftersom det är mindre än 8 och 8 är en lövnod lägger vi 7 till vänster barn 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Vi har lagt ett nummer till vår binära sökträd.

176
00:09:09,000 --> 00:09:12,000
>> Om vi ​​kan lägga saker, att vi bättre kan ta bort saker också.

177
00:09:12,000 --> 00:09:14,000
Tyvärr för oss, är att ta bort lite mer komplicerat -

178
00:09:14,000 --> 00:09:16,000
inte mycket, men bara lite.

179
00:09:16,000 --> 00:09:18,000
Det finns 3 olika scenarion som vi måste överväga

180
00:09:18,000 --> 00:09:21,000
när du tar bort element från binära sökträd.

181
00:09:21,000 --> 00:09:24,000
Först, är det enklaste fallet att elementet är en lövnod.

182
00:09:24,000 --> 00:09:27,000
I det här fallet, ta bort vi bara den och gå vidare med vår verksamhet.

183
00:09:27,000 --> 00:09:30,000
Säg att vi vill ta bort 7 som vi just lagt.

184
00:09:30,000 --> 00:09:34,000
Tja, vi helt enkelt hitta den, ta bort den, och det är det.

185
00:09:35,000 --> 00:09:37,000
Nästa fallet är om noden har endast 1 barn.

186
00:09:37,000 --> 00:09:40,000
Här kan vi ta bort noden, men vi måste först se till att

187
00:09:40,000 --> 00:09:42,000
att ansluta underträd som nu lämnas föräldralösa

188
00:09:42,000 --> 00:09:44,000
till överordnade noden vi bort bara.

189
00:09:44,000 --> 00:09:47,000
Säg att vi vill ta bort 3 från vår träd.

190
00:09:47,000 --> 00:09:50,000
Vi tar barnet del av denna nod och bifoga det till den förälder av noden.

191
00:09:50,000 --> 00:09:54,000
I det här fallet, vi fästa nu 1 till 5.

192
00:09:54,000 --> 00:09:57,000
Detta fungerar utan problem eftersom vi vet, enligt binära sökträdet egendom,

193
00:09:57,000 --> 00:10:01,000
att allt i vänstra delträd av 3 var mindre än 5.

194
00:10:01,000 --> 00:10:05,000
Nu när 3: s underträd tas om hand, kan vi ta bort den.

195
00:10:05,000 --> 00:10:08,000
Den tredje och sista fallet är den mest komplicerade.

196
00:10:08,000 --> 00:10:11,000
Detta är fallet när noden vi vill ta bort har 2 barn.

197
00:10:11,000 --> 00:10:15,000
För att göra detta måste vi först hitta noden som har den största värdet,

198
00:10:15,000 --> 00:10:18,000
byta två, och sedan ta bort noden i fråga.

199
00:10:18,000 --> 00:10:22,000
Lägg märke till nod som har den största värdet inte kan ha 2 barn själv

200
00:10:22,000 --> 00:10:26,000
eftersom dess vänstra barn skulle vara en bättre kandidat för den näst största.

201
00:10:26,000 --> 00:10:30,000
Därför, ta bort en nod med 2 barn uppgår till byta av 2 noder,

202
00:10:30,000 --> 00:10:33,000
och sedan ta bort sköts av 1 av de 2 ovan nämnda reglerna.

203
00:10:33,000 --> 00:10:37,000
Till exempel, låt oss säga att vi vill ta bort rotnoden, 13.

204
00:10:37,000 --> 00:10:39,000
Det första vi gör är att vi hittar den näst största värdet i trädet

205
00:10:39,000 --> 00:10:41,000
som i detta fall, är 21.

206
00:10:41,000 --> 00:10:46,000
Vi byter sedan 2 noder, vilket 13 ett blad och 21 den centrala gruppen nod.

207
00:10:46,000 --> 00:10:49,000
Nu kan vi helt enkelt ta bort 13.

208
00:10:50,000 --> 00:10:53,000
>> Som nämndes tidigare, det finns många möjliga sätt att göra en giltig träd binär sökning.

209
00:10:53,000 --> 00:10:56,000
Tyvärr för oss, vissa är värre än andra.

210
00:10:56,000 --> 00:10:59,000
Till exempel, vad händer när vi bygger ett binärt sökträd

211
00:10:59,000 --> 00:11:01,000
från en sorterad lista med nummer?

212
00:11:01,000 --> 00:11:04,000
Alla siffror är bara till höger vid varje steg.

213
00:11:04,000 --> 00:11:06,000
När vi vill söka efter ett nummer,

214
00:11:06,000 --> 00:11:08,000
Vi har inget annat val än bara titta på rätt vid varje steg.

215
00:11:08,000 --> 00:11:11,000
Detta är inte bättre än linjär sökning alls.

216
00:11:11,000 --> 00:11:13,000
Även om vi inte kommer att täcka dem här, det finns andra, mer komplexa,

217
00:11:13,000 --> 00:11:16,000
datastrukturer som ser till att detta inte sker.

218
00:11:16,000 --> 00:11:18,000
Men en enkel sak som kan göras för att undvika detta

219
00:11:18,000 --> 00:11:21,000
att bara slumpmässigt blanda de ingående värdena.

220
00:11:21,000 --> 00:11:26,000
Det är högst osannolikt att genom slumpen en blandad lista med nummer sorteras.

221
00:11:26,000 --> 00:11:29,000
Om så vore fallet, skulle kasinon inte stanna i affärer för länge.

222
00:11:29,000 --> 00:11:31,000
>> Där har ni det.

223
00:11:31,000 --> 00:11:34,000
Du vet nu om binär sökning och binära träd sökning.

224
00:11:34,000 --> 00:11:36,000
Jag Patrick Schmid, och detta är CS50.

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

226
00:11:38,000 --> 00:11:43,000
Ett självklart sätt skulle vara att skanna listan från ... [pip]

227
00:11:43,000 --> 00:11:46,000
... Antalet objekt ... Japp

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

229
00:11:50,000 --> 00:11:55,000
... Post nod 234 ... augh.

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