1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Recerca binària]

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

3
00:00:04,000 --> 00:00:07,000
[Aquesta és CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Si et dono una llista dels noms dels personatges de Disney en ordre alfabètic

5
00:00:09,000 --> 00:00:11,000
i li va demanar que trobés Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
Com anar fent això?

7
00:00:13,000 --> 00:00:15,000
Una manera òbvia seria per escanejar la llista des del principi

8
00:00:15,000 --> 00:00:18,000
i verificar cada nom per veure si és Mickey.

9
00:00:18,000 --> 00:00:22,000
Però a mesura que llegeix Aladdin, Alice, Ariel, i així successivament,

10
00:00:22,000 --> 00:00:25,000
aviat et donaràs compte que a partir de la part davantera de la llista no era una bona idea.

11
00:00:25,000 --> 00:00:29,000
Bé, potser hauria de començar a treballar cap enrere des del final de la llista.

12
00:00:29,000 --> 00:00:33,000
Ara vostè llegir Tarzan, Stitch, Blancaneus, i així successivament.

13
00:00:33,000 --> 00:00:36,000
No obstant això, això no sembla la millor manera d'anar-hi.

14
00:00:36,000 --> 00:00:38,000
>> Bé, una altra forma en què vostè pot anar sobre fer això és intentar reduir

15
00:00:38,000 --> 00:00:41,000
la llista de noms que s'ha de mirar.

16
00:00:41,000 --> 00:00:43,000
Ja que vostè sap que ells estan en ordre alfabètic,

17
00:00:43,000 --> 00:00:45,000
vostè podria mirar als noms en la meitat de la llista

18
00:00:45,000 --> 00:00:49,000
i comprovar si Mickey Mouse és abans o després d'aquest nom.

19
00:00:49,000 --> 00:00:51,000
Mirant el cognom a la segona columna

20
00:00:51,000 --> 00:00:54,000
t'adonaries que M per Mickey ve després de J per Jasmine,

21
00:00:54,000 --> 00:00:57,000
pel que simplement em ignoren la primera meitat de la llista.

22
00:00:57,000 --> 00:00:59,000
Llavors probablement veuria a la part superior de l'última columna

23
00:00:59,000 --> 00:01:02,000
i veure que comença amb Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey ve abans de Rapunzel, sembla que podem passar per alt l'última columna també.

25
00:01:06,000 --> 00:01:08,000
Continuant amb l'estratègia de recerca, que dóna gust veure que Mickey

26
00:01:08,000 --> 00:01:11,000
és a la primera meitat de la llista restant de noms

27
00:01:11,000 --> 00:01:14,000
i, finalment, trobar Mickey amagat entre Merlí i Minnie.

28
00:01:14,000 --> 00:01:17,000
>> El que acabes de fer és buscar bàsicament binari.

29
00:01:17,000 --> 00:01:22,000
Com aquest nom indica, es porta a terme la seva estratègia de cerca en qüestió binari.

30
00:01:22,000 --> 00:01:24,000
Què vol dir això?

31
00:01:24,000 --> 00:01:27,000
Doncs bé, donada una llista d'elements ordenats, l'algorisme de recerca binària pren una decisió binària -

32
00:01:27,000 --> 00:01:33,000
esquerra o cap a la dreta, més gran que o més petit que, alfabèticament abans o després - en cada punt.

33
00:01:33,000 --> 00:01:35,000
Ara que tenim un nom que va juntament amb aquest algorisme de recerca,

34
00:01:35,000 --> 00:01:38,000
Vegem un altre exemple, però aquest cop amb una llista de nombres ordenats.

35
00:01:38,000 --> 00:01:43,000
Diguem que estem buscant el número 144 en la llista de nombres ordenats.

36
00:01:43,000 --> 00:01:46,000
Igual que abans, ens trobem amb el nombre que està al mig -

37
00:01:46,000 --> 00:01:50,000
que en aquest cas és 13-144 i veure si és més o menys que 13.

38
00:01:50,000 --> 00:01:54,000
Ja que és clarament superior a 13, es pot passar per alt tot el que és 13 o menys

39
00:01:54,000 --> 00:01:57,000
i només es concentra en la meitat restant.

40
00:01:57,000 --> 00:01:59,000
Com que ara tenim un nombre parell d'elements a l'esquerra,

41
00:01:59,000 --> 00:02:01,000
simplement tria un nombre que és a prop del centre.

42
00:02:01,000 --> 00:02:03,000
En aquest cas, vam triar 55.

43
00:02:03,000 --> 00:02:06,000
Podríem haver triat la mateixa facilitat 89.

44
00:02:06,000 --> 00:02:11,000
Bé. Un cop més, 144 és superior a 55, així que anem a la dreta.

45
00:02:11,000 --> 00:02:14,000
Afortunadament per a nosaltres, el nombre central al costat és de 144,

46
00:02:14,000 --> 00:02:16,000
la qual estem buscant.

47
00:02:16,000 --> 00:02:21,000
Així que per trobar 144 mitjançant una recerca binària, podem trobar en només 3 passos.

48
00:02:21,000 --> 00:02:24,000
Si haguéssim usat recerca lineal aquí, ens hauria pres 12 passos.

49
00:02:24,000 --> 00:02:28,000
Com a qüestió de fet, ja que aquest mètode de recerca a la meitat el nombre d'articles

50
00:02:28,000 --> 00:02:31,000
ha de mirar a cada pas, es troba l'article que està buscant

51
00:02:31,000 --> 00:02:35,000
en aproximadament el log del nombre d'elements de la llista.

52
00:02:35,000 --> 00:02:37,000
Ara que hem vist dos exemples, anem a fer una ullada a

53
00:02:37,000 --> 00:02:41,000
alguns pseudocodi per a una funció recursiva que implementa la recerca binària.

54
00:02:41,000 --> 00:02:44,000
Començant per la part superior, veiem que hem de trobar una funció que pren 4 arguments:

55
00:02:44,000 --> 00:02:47,000
clau, array, min i max.

56
00:02:47,000 --> 00:02:51,000
La clau és el nombre que estem buscant, així que 144 en l'exemple anterior.

57
00:02:51,000 --> 00:02:54,000
Matriu és la llista dels nombres que estem buscant.

58
00:02:54,000 --> 00:02:57,000
Min i max són els índexs de les posicions mínima i màxima

59
00:02:57,000 --> 00:02:59,000
que actualment estem veient.

60
00:02:59,000 --> 00:03:03,000
Així que quan vam començar, min serà zero i el màxim serà l'índex màxim de la matriu.

61
00:03:03,000 --> 00:03:07,000
En reduir la recerca, actualitzarem min i max

62
00:03:07,000 --> 00:03:10,000
a ser només el rang que encara estem mirant cap a dins

63
00:03:10,000 --> 00:03:12,000
>> Anem a passar a la part interessant en primer lloc.

64
00:03:12,000 --> 00:03:14,000
El primer que hem de fer és trobar el punt mig,

65
00:03:14,000 --> 00:03:19,000
l'índex que està a mig camí entre el mínim i màxim de la matriu que encara estem considerant.

66
00:03:19,000 --> 00:03:22,000
A continuació, ens fixem en el valor de la matriu de punt mitjà en aquest lloc

67
00:03:22,000 --> 00:03:25,000
i veure si el nombre que estem buscant és menor que la clau.

68
00:03:25,000 --> 00:03:27,000
Si el nombre en aquesta posició és menor,

69
00:03:27,000 --> 00:03:31,000
llavors vol dir que la clau és més gran que tots els nombres a l'esquerra d'aquesta posició.

70
00:03:31,000 --> 00:03:33,000
Així que podem trucar a la funció de cerca binària de nou,

71
00:03:33,000 --> 00:03:36,000
però aquesta vegada l'actualització dels valors mínim i màxim dels paràmetres de llegir només la meitat

72
00:03:36,000 --> 00:03:40,000
que és més gran que o igual al valor que acabem de veure.

73
00:03:40,000 --> 00:03:44,000
D'altra banda, si la clau és menor que el nombre actual al punt mig de la matriu,

74
00:03:44,000 --> 00:03:47,000
volem anar a l'esquerra i passar per alt tots els nombres que són majors.

75
00:03:47,000 --> 00:03:52,000
Un cop més, fem una crida binari de recerca, però aquesta vegada amb la gamma de min i max actualització

76
00:03:52,000 --> 00:03:54,000
per incloure només la meitat inferior.

77
00:03:54,000 --> 00:03:57,000
Si el valor en el punt mitjà actual en la matriu no és ni

78
00:03:57,000 --> 00:04:01,000
més gran que ni més petit que la clau, llavors ha de ser igual a la clau.

79
00:04:01,000 --> 00:04:05,000
Per tant, podem simplement tornar l'índex actual punt mig, i ja està.

80
00:04:05,000 --> 00:04:09,000
Finalment, aquesta comprovació aquí és per al cas que el nombre

81
00:04:09,000 --> 00:04:11,000
no és en realitat en el conjunt de nombres que estem buscant.

82
00:04:11,000 --> 00:04:14,000
Si l'índex màxim de la gamma que estem buscant

83
00:04:14,000 --> 00:04:17,000
és sempre menor que el mínim, això vol dir que hem anat massa lluny.

84
00:04:17,000 --> 00:04:20,000
Atès que el nombre no era a la matriu d'entrada, tornem -1

85
00:04:20,000 --> 00:04:24,000
per indicar que no es va trobar res.

86
00:04:24,000 --> 00:04:26,000
>> T'hauràs adonat que per aquest algorisme per treballar,

87
00:04:26,000 --> 00:04:28,000
la llista de nombres ha de ser ordenats.

88
00:04:28,000 --> 00:04:31,000
En altres paraules, només es pot trobar a la recerca binària 144

89
00:04:31,000 --> 00:04:34,000
si tots els nombres estan ordenats de menor a major.

90
00:04:34,000 --> 00:04:38,000
Si aquest no fos el cas, no seria capaç d'excloure mitjà dels nombres en cada pas.

91
00:04:38,000 --> 00:04:40,000
Així que tenim dues opcions.

92
00:04:40,000 --> 00:04:43,000
O es pot prendre una llista sense ordenar i classificar abans d'usar recerca binària,

93
00:04:43,000 --> 00:04:48,000
o podem assegurar-nos que la llista de nombres s'ordenen com afegir números a la mateixa.

94
00:04:48,000 --> 00:04:50,000
Així, en lloc de classificar en el moment en què hem de buscar,

95
00:04:50,000 --> 00:04:53,000
¿Per què no mantenir la llista ordenada en tot moment?

96
00:04:53,000 --> 00:04:57,000
>> Una manera de mantenir una llista de nombres ordenats alhora que permet

97
00:04:57,000 --> 00:04:59,000
un per afegir o moure números d'aquesta llista

98
00:04:59,000 --> 00:05:02,000
és l'ús d'alguna cosa que es diu un arbre de cerca binària.

99
00:05:02,000 --> 00:05:05,000
Un arbre de recerca binari és una estructura de dades que té 3 propietats.

100
00:05:05,000 --> 00:05:09,000
En primer lloc, el subarbre esquerre de qualsevol node conté només valors que són menors que

101
00:05:09,000 --> 00:05:11,000
o igual que el valor del node.

102
00:05:11,000 --> 00:05:15,000
En segon lloc, el subarbre dret d'un node només conté valors que són més grans que

103
00:05:15,000 --> 00:05:17,000
o igual que el valor del node.

104
00:05:17,000 --> 00:05:20,000
I, finalment, tant els subarbres esquerre i dret de tots els nodes

105
00:05:20,000 --> 00:05:23,000
també són arbres binaris de cerca.

106
00:05:23,000 --> 00:05:26,000
Vegem un exemple amb els mateixos números que fem servir abans.

107
00:05:26,000 --> 00:05:30,000
Per a aquells de vostès que mai han vist un arbre abans de la informàtica,

108
00:05:30,000 --> 00:05:34,000
m'ho dius a mi començar dient que un arbre de la informàtica creix cap avall.

109
00:05:34,000 --> 00:05:36,000
Sí, a diferència dels arbres que estan acostumats,

110
00:05:36,000 --> 00:05:38,000
l'arrel d'un arbre de la informàtica és a la part superior,

111
00:05:38,000 --> 00:05:41,000
i les fulles estan a la part inferior.

112
00:05:41,000 --> 00:05:45,000
Cada caixa petita s'anomena un node, i els nodes estan connectats entre si per les vores.

113
00:05:45,000 --> 00:05:48,000
Així que l'arrel d'aquest arbre és un node de valor amb el valor 13,

114
00:05:48,000 --> 00:05:52,000
que té 2 nodes fills amb els valors 5 i 34 anys.

115
00:05:52,000 --> 00:05:57,000
Un subarbre és l'arbre que es forma amb només mirar una subsecció de tot l'arbre.

116
00:05:57,000 --> 00:06:03,000
>> Per exemple, el subarbre esquerre del node 3 és l'arbre creat pels nodes 0, 1 i 2.

117
00:06:03,000 --> 00:06:06,000
Així doncs, si ens remuntem a les propietats d'un arbre de cerca binària,

118
00:06:06,000 --> 00:06:09,000
veiem que cada node de l'arbre s'ajusta a tots els 3 propietats, és a dir,

119
00:06:09,000 --> 00:06:15,000
el subarbre esquerre només conté valors que són menors o iguals que el valor del node;

120
00:06:15,000 --> 00:06:16,000
el subarbre dret de tots els nodes

121
00:06:16,000 --> 00:06:19,000
només conté valors que són majors o iguals que el valor del node, i

122
00:06:19,000 --> 00:06:25,000
subarbres esquerre i dret de tots els nodes també són arbres binaris de cerca.

123
00:06:25,000 --> 00:06:28,000
Encara que aquest arbre es veu diferent, es tracta d'un arbre binari de cerca vàlid

124
00:06:28,000 --> 00:06:30,000
per al mateix conjunt de nombres.

125
00:06:30,000 --> 00:06:32,000
Com a qüestió de fet, hi ha moltes formes possibles que es poden crear

126
00:06:32,000 --> 00:06:35,000
un arbre de recerca binari vàlid d'aquests nombres.

127
00:06:35,000 --> 00:06:38,000
Bé, tornem a la primera que hem creat.

128
00:06:38,000 --> 00:06:40,000
Llavors, què podem fer amb aquests arbres?

129
00:06:40,000 --> 00:06:44,000
Bé, podem senzillament trobar els valors mínims i màxims.

130
00:06:44,000 --> 00:06:46,000
Els valors mínims es pot trobar sempre va a l'esquerra

131
00:06:46,000 --> 00:06:48,000
fins que no hi ha més nodes per visitar.

132
00:06:48,000 --> 00:06:53,000
Per contra, per trobar el màxim simplement baixa a la dreta en cada moment.

133
00:06:54,000 --> 00:06:56,000
>> Recerca de qualsevol altre nombre que no és el mínim o el màxim

134
00:06:56,000 --> 00:06:58,000
és igual de fàcil.

135
00:06:58,000 --> 00:07:00,000
Diguem que està buscant el número 89.

136
00:07:00,000 --> 00:07:03,000
Nosaltres simplement comprovar el valor de cada node i vagi a l'esquerra oa la dreta,

137
00:07:03,000 --> 00:07:06,000
depenent de si el valor del node és menor o major que

138
00:07:06,000 --> 00:07:08,000
la qual estem buscant.

139
00:07:08,000 --> 00:07:11,000
Així, a partir de l'arrel de 13, veiem que 89 és major,

140
00:07:11,000 --> 00:07:13,000
i així ens anem a la dreta.

141
00:07:13,000 --> 00:07:16,000
Després veiem el node de 34 anys, i una altra ens anem a la dreta.

142
00:07:16,000 --> 00:07:20,000
89 és encara superior a 55, així que a seguir anant a la dreta.

143
00:07:20,000 --> 00:07:24,000
A continuació, arribar a un node amb el valor de 144 i vagi a l'esquerra.

144
00:07:24,000 --> 00:07:26,000
Però vet aquí que 89 és just allà.

145
00:07:26,000 --> 00:07:31,000
>> Una altra cosa que podem fer és imprimir tots els nombres mitjançant la realització d'un recorregut en ordre.

146
00:07:31,000 --> 00:07:35,000
Un recorregut en ordre significa per imprimir tot en el subarbre esquerre

147
00:07:35,000 --> 00:07:37,000
seguit per la impressió del propi node

148
00:07:37,000 --> 00:07:40,000
i després va seguir imprimint tot al subarbre dret.

149
00:07:40,000 --> 00:07:43,000
Per exemple, prenguem el nostre arbre binari de cerca favorit

150
00:07:43,000 --> 00:07:46,000
i imprimir els números en ordre.

151
00:07:46,000 --> 00:07:49,000
Comencem a l'arrel de 13, però abans de la impressió 13 que ha d'imprimir

152
00:07:49,000 --> 00:07:51,000
tot en el subarbre esquerre.

153
00:07:51,000 --> 00:07:55,000
Així que ens anem a 5. Encara hem d'anar més avall en l'arbre fins a trobar el node més a l'esquerra,

154
00:07:55,000 --> 00:07:57,000
que és zero.

155
00:07:57,000 --> 00:08:00,000
Després de la impressió zero, tornar a pujar a la 1 i imprimir això.

156
00:08:00,000 --> 00:08:03,000
Després anem al subarbre dret, que és 2, i imprimir això.

157
00:08:03,000 --> 00:08:05,000
Ara que hem acabat amb aquest subarbre,

158
00:08:05,000 --> 00:08:07,000
podem tornar a pujar a la 3 i imprimir-lo.

159
00:08:07,000 --> 00:08:11,000
Continuant cap amunt, imprimim el 5 i després el 8.

160
00:08:11,000 --> 00:08:13,000
Ara que hem completat tot el subarbre esquerre,

161
00:08:13,000 --> 00:08:17,000
podem imprimir el 13 i començar a treballar en el subarbre dret.

162
00:08:17,000 --> 00:08:21,000
Ens saltar fins a 34, però abans d'imprimir 34 hem de imprimir el seu subarbre esquerre.

163
00:08:21,000 --> 00:08:27,000
Així que imprimir 21, llavors hem de imprimir 34 i visiti el seu subarbre dret.

164
00:08:27,000 --> 00:08:31,000
Des de 55 no té subarbre esquerre, que l'imprimeixin i continuï amb la seva subarbre dret.

165
00:08:31,000 --> 00:08:36,000
144 té un subarbre esquerre, i així d'imprimir la 89, seguit pel 144,

166
00:08:36,000 --> 00:08:39,000
i, finalment, el node més a la dreta de 233.

167
00:08:39,000 --> 00:08:44,000
Aquí el tenen, tots els nombres s'imprimeixen en ordre de menor a major.

168
00:08:44,000 --> 00:08:47,000
>> Afegint alguna cosa que l'arbre és relativament sense dolor també.

169
00:08:47,000 --> 00:08:51,000
Tot el que hem de fer és assegurar-nos seguir 3 propietats arbre de cerca binària

170
00:08:51,000 --> 00:08:53,000
i després inserir el valor on hi ha espai.

171
00:08:53,000 --> 00:08:55,000
Diguem que volem inserir el valor de 7.

172
00:08:55,000 --> 00:08:58,000
Com 7 és menor que 13, ens anem a l'esquerra.

173
00:08:58,000 --> 00:09:01,000
Però és més gran que 5, de manera que travessen a la dreta.

174
00:09:01,000 --> 00:09:04,000
Com que és menys de 8 i 8 és un node fulla, s'afegeix 7 al fill esquerre de 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Hem afegit un nombre al nostre arbre de cerca binària.

176
00:09:09,000 --> 00:09:12,000
>> Si podem afegir coses, és millor que ser capaç d'esborrar les coses tan bé.

177
00:09:12,000 --> 00:09:14,000
Per desgràcia per a nosaltres, l'eliminació és una mica més complicat -

178
00:09:14,000 --> 00:09:16,000
No és molt, però només una mica.

179
00:09:16,000 --> 00:09:18,000
Hi ha 3 diferents escenaris que hem de considerar

180
00:09:18,000 --> 00:09:21,000
en eliminar elements dels arbres binaris de cerca.

181
00:09:21,000 --> 00:09:24,000
En primer lloc, el cas més senzill és que l'element és un node fulla.

182
00:09:24,000 --> 00:09:27,000
En aquest cas, només ha d'esborrar i seguir amb el nostre negoci.

183
00:09:27,000 --> 00:09:30,000
Diguem que vols eliminar el 7 que acaba d'afegir.

184
00:09:30,000 --> 00:09:34,000
Bé, simplement ho troba, treure, i això és tot.

185
00:09:35,000 --> 00:09:37,000
El següent cas és si el node té només 1 nen.

186
00:09:37,000 --> 00:09:40,000
Aquí es pot eliminar el node, però primer hem d'assegurar

187
00:09:40,000 --> 00:09:42,000
per connectar el subarbre que queda ara sense pares

188
00:09:42,000 --> 00:09:44,000
el pare del node que acaba d'eliminar.

189
00:09:44,000 --> 00:09:47,000
Diguem voler esborrar 3 del nostre arbre.

190
00:09:47,000 --> 00:09:50,000
Prenem l'element fill d'aquest node i adjuntar-lo al pare del node.

191
00:09:50,000 --> 00:09:54,000
En aquest cas, ara estem adjuntant la 1 a la 5.

192
00:09:54,000 --> 00:09:57,000
Això funciona sense cap problema, perquè sabem, d'acord amb la propietat d'arbre binari de recerca,

193
00:09:57,000 --> 00:10:01,000
que tot en el subarbre esquerre de 3 va ser inferior a 5.

194
00:10:01,000 --> 00:10:05,000
Ara que el 3 de subarbre es cuida, es pot eliminar.

195
00:10:05,000 --> 00:10:08,000
El tercer i últim cas és el més complex.

196
00:10:08,000 --> 00:10:11,000
Aquest és el cas quan el node que voleu suprimir té 2 nens.

197
00:10:11,000 --> 00:10:15,000
Per tal de fer això, primer ha de trobar el node que té el següent valor major,

198
00:10:15,000 --> 00:10:18,000
canviar els dos, i després eliminar el node en qüestió.

199
00:10:18,000 --> 00:10:22,000
Observeu el node que té el següent valor més gran no pot tenir 2 fills si

200
00:10:22,000 --> 00:10:26,000
ja que el seu fill de l'esquerra seria un millor candidat per l'immediatament superior.

201
00:10:26,000 --> 00:10:30,000
Per tant, l'eliminació d'un node amb 2 fills equival a 2 nodes d'intercanvi,

202
00:10:30,000 --> 00:10:33,000
i esborrar està a càrrec d'una de les dues normes esmentades.

203
00:10:33,000 --> 00:10:37,000
Per exemple, diguem que voleu eliminar el node arrel de 13.

204
00:10:37,000 --> 00:10:39,000
El primer que fem és trobar el següent valor més gran en l'arbre

205
00:10:39,000 --> 00:10:41,000
que, en aquest cas, és 21.

206
00:10:41,000 --> 00:10:46,000
A continuació, canviar els 2 nodes, de manera que una fulla 13 i 21 el node del grup central.

207
00:10:46,000 --> 00:10:49,000
Ara podem simplement esborrar 13.

208
00:10:50,000 --> 00:10:53,000
>> Com es va esmentar anteriorment, hi ha moltes maneres possibles de fer un arbre binari de recerca vàlida.

209
00:10:53,000 --> 00:10:56,000
Per desgràcia per a nosaltres, alguns són pitjors que altres.

210
00:10:56,000 --> 00:10:59,000
Per exemple, què passa quan es construeix un arbre de cerca binària

211
00:10:59,000 --> 00:11:01,000
a partir d'una llista ordenada de nombres?

212
00:11:01,000 --> 00:11:04,000
Tots els números s'acaba d'afegir a la dreta en cada pas.

213
00:11:04,000 --> 00:11:06,000
Quan volem buscar un nombre,

214
00:11:06,000 --> 00:11:08,000
no tenim més remei que mirar a la dreta en cada pas.

215
00:11:08,000 --> 00:11:11,000
Això no és millor que la recerca lineal en absolut.

216
00:11:11,000 --> 00:11:13,000
Encara que no anem a cobrir aquí, hi ha altres, més complexes,

217
00:11:13,000 --> 00:11:16,000
estructures de dades que asseguren que això no succeeixi.

218
00:11:16,000 --> 00:11:18,000
No obstant això, una cosa simple que es pot fer per evitar-ho és

219
00:11:18,000 --> 00:11:21,000
només a l'atzar a estudiar els valors d'entrada.

220
00:11:21,000 --> 00:11:26,000
És molt poc probable que per l'atzar d'una llista de nombres estudien està ordenada.

221
00:11:26,000 --> 00:11:29,000
Si aquest fos el cas, els casinos no romandre en el negoci per molt temps.

222
00:11:29,000 --> 00:11:31,000
>> Aquí el tenen.

223
00:11:31,000 --> 00:11:34,000
Ara ja sap de les cerques binàries i arbres binaris de cerca.

224
00:11:34,000 --> 00:11:36,000
Sóc Patrick Schmid, i això és CS50.

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

226
00:11:38,000 --> 00:11:43,000
Una manera òbvia seria la d'examinar la llista de ... [xiulet]

227
00:11:43,000 --> 00:11:46,000
... El nombre d'elements ... sip

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

229
00:11:50,000 --> 00:11:55,000
Node de publicar ... 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Això va ser -