1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Busca Binario]

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

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

4
00:00:07,000 --> 00:00:09,000
>> Se eu lle dei unha lista de nomes de personaxes de Disney en orde alfabética

5
00:00:09,000 --> 00:00:11,000
e pediu-lle para atopar o Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
como é que vai facer sobre iso?

7
00:00:13,000 --> 00:00:15,000
Unha forma obvia sería a de examinar a lista desde o inicio

8
00:00:15,000 --> 00:00:18,000
e comprobar cada nome para ver se é Mickey.

9
00:00:18,000 --> 00:00:22,000
Pero cando le Aladdin, Alicia, Ariel, e así por diante,

10
00:00:22,000 --> 00:00:25,000
vai logo entender que a partir da fronte da lista non foi unha boa idea.

11
00:00:25,000 --> 00:00:29,000
Ok, quizais ten que comezar a traballar cara atrás a partir do final da lista.

12
00:00:29,000 --> 00:00:33,000
Agora ler Tarzan, Stitch, Brancaneves, e así por diante.

13
00:00:33,000 --> 00:00:36,000
Aínda así, esta non parece ser a mellor maneira de ir sobre el.

14
00:00:36,000 --> 00:00:38,000
>> Ben, outra forma que pode facer sobre iso é para tentar diminuír

15
00:00:38,000 --> 00:00:41,000
a lista de nomes que ten que mirar.

16
00:00:41,000 --> 00:00:43,000
Como vostede sabe que eles están en orde alfabética,

17
00:00:43,000 --> 00:00:45,000
pode só ollar para os nomes no medio da lista

18
00:00:45,000 --> 00:00:49,000
e comproba que o Mickey Mouse é antes ou despois deste nome.

19
00:00:49,000 --> 00:00:51,000
Mirando para o último nome na segunda columna

20
00:00:51,000 --> 00:00:54,000
vostede entendería que a M para Mickey vén despois J para Jasmine,

21
00:00:54,000 --> 00:00:57,000
así que simplemente ignorar a primeira metade da lista.

22
00:00:57,000 --> 00:00:59,000
Entón probablemente ollar para arriba da última columna

23
00:00:59,000 --> 00:01:02,000
e ver que comeza con Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey vén antes de Rapunzel, parece que podemos ignorar a última columna tamén.

25
00:01:06,000 --> 00:01:08,000
Continuando a estratexia de busca, podes ver rapidamente que Mickey

26
00:01:08,000 --> 00:01:11,000
está na primeira metade do resto lista de nomes

27
00:01:11,000 --> 00:01:14,000
e, finalmente, atopar Mickey oculto entre Merlin e Minnie.

28
00:01:14,000 --> 00:01:17,000
>> O que fixo foi basicamente busca binaria.

29
00:01:17,000 --> 00:01:22,000
Como este nome indica, el executa a súa estratexia de busca en cuestión binario.

30
00:01:22,000 --> 00:01:24,000
O que significa isto?

31
00:01:24,000 --> 00:01:27,000
Ben, dada unha lista de elementos clasificados, o algoritmo de procura binaria fai unha decisión binaria -

32
00:01:27,000 --> 00:01:33,000
cara á esquerda ou á dereita, maior ou menor que, por orde alfabética, antes ou despois - en cada punto.

33
00:01:33,000 --> 00:01:35,000
Agora que temos un nome que vai xunto con este algoritmo de procura,

34
00:01:35,000 --> 00:01:38,000
Vexamos outro exemplo, pero esta vez con unha lista de números ordenados.

35
00:01:38,000 --> 00:01:43,000
Dicir que estamos ollando para o número 144 na lista de números ordenados.

36
00:01:43,000 --> 00:01:46,000
Así como antes, atopamos o número que está no medio -

37
00:01:46,000 --> 00:01:50,000
que neste caso é de 13 - 144 para ver se é maior que ou menor que 13.

38
00:01:50,000 --> 00:01:54,000
Unha vez que é claramente maior que 13, podemos ignorar todo o que é de 13 ou menos

39
00:01:54,000 --> 00:01:57,000
e concentrar só na metade restante.

40
00:01:57,000 --> 00:01:59,000
Unha vez que agora teñen un número par de elementos da esquerda,

41
00:01:59,000 --> 00:02:01,000
nós simplemente escoller un número que está preto da media.

42
00:02:01,000 --> 00:02:03,000
Neste caso, nós escoller 55.

43
00:02:03,000 --> 00:02:06,000
Nós poderiamos ter facilmente seleccionados 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Unha vez máis, 144 é maior que 55, por tanto, desprácese á dereita.

45
00:02:11,000 --> 00:02:14,000
Afortunadamente para nós, o número do medio próximo e 144,

46
00:02:14,000 --> 00:02:16,000
o que estamos a buscar.

47
00:02:16,000 --> 00:02:21,000
Polo tanto, a fin de atopar 144 usando investigación binaria, somos capaces de atopalo en só 3 pasos.

48
00:02:21,000 --> 00:02:24,000
Se tivésemos usado busca lineal aquí, tería nos levou 12 pasos.

49
00:02:24,000 --> 00:02:28,000
Por unha cuestión de feito, unha vez que este método de investigación metades do número de elementos

50
00:02:28,000 --> 00:02:31,000
ten que ollar a cada paso, vai atopar o elemento que está á procura de

51
00:02:31,000 --> 00:02:35,000
en sobre o logaritmo do número de elementos na lista.

52
00:02:35,000 --> 00:02:37,000
Agora que xa vimos dous exemplos, imos dar un ollo

53
00:02:37,000 --> 00:02:41,000
un pseudocódigo para unha función recursiva que aplica busca binaria.

54
00:02:41,000 --> 00:02:44,000
Comezando polo principio, vemos que temos que atopar unha función que recibe 4 argumentos:

55
00:02:44,000 --> 00:02:47,000
clave, matriz min, e Max.

56
00:02:47,000 --> 00:02:51,000
A clave é o número que nós estamos a buscar, de xeito 144 no exemplo anterior.

57
00:02:51,000 --> 00:02:54,000
Matriz é unha lista de números que estamos a buscar.

58
00:02:54,000 --> 00:02:57,000
Mínimo e máximo son os índices das posicións mínimas e máximas

59
00:02:57,000 --> 00:02:59,000
que actualmente estamos mirando.

60
00:02:59,000 --> 00:03:03,000
Así, cando se inicia, min será cero e max será o índice máximo da matriz.

61
00:03:03,000 --> 00:03:07,000
Como se restrinxir a busca a abaixo, imos actualizar min e max

62
00:03:07,000 --> 00:03:10,000
para ser só a franxa que aínda estamos mirando para dentro

63
00:03:10,000 --> 00:03:12,000
>> Imos saltar cara á parte interesante en primeiro lugar.

64
00:03:12,000 --> 00:03:14,000
O primeiro que facemos é atopar o punto medio,

65
00:03:14,000 --> 00:03:19,000
o índice que está a medio camiño entre o mínimo eo máximo da matriz que aínda estamos considerando.

66
00:03:19,000 --> 00:03:22,000
Entón, miramos para o valor da matriz en que a situación do punto medio

67
00:03:22,000 --> 00:03:25,000
e ver se o número que estamos a buscar é menor que a clave.

68
00:03:25,000 --> 00:03:27,000
O número no que a posición é menos

69
00:03:27,000 --> 00:03:31,000
entón iso significa que a clave é maior que todos os números á esquerda desa posición.

70
00:03:31,000 --> 00:03:33,000
Así, podemos chamar a función de busca binaria, de novo,

71
00:03:33,000 --> 00:03:36,000
pero esta vez, a actualizar o min e max parámetros de ler só a metade

72
00:03:36,000 --> 00:03:40,000
que é maior que ou igual ao valor que acabamos de ver.

73
00:03:40,000 --> 00:03:44,000
Por outra banda, a clave é menor que o número actual no punto medio da matriz,

74
00:03:44,000 --> 00:03:47,000
queremos ir á esquerda e ignorar todos os números que son maiores.

75
00:03:47,000 --> 00:03:52,000
Unha vez máis, chamamos busca binaria, pero esta vez coa gama de min e max updated

76
00:03:52,000 --> 00:03:54,000
para incluír só a metade inferior.

77
00:03:54,000 --> 00:03:57,000
Se o valor no punto medio actual na matriz non é nin

78
00:03:57,000 --> 00:04:01,000
maior que ou menor que a clave, entón ten que ser igual á chave.

79
00:04:01,000 --> 00:04:05,000
Así, podemos simplemente devolver o índice punto medio actual, e estamos a facer.

80
00:04:05,000 --> 00:04:09,000
Finalmente, esta verificación aquí é para o caso en que o número

81
00:04:09,000 --> 00:04:11,000
non é, en realidade, na matriz de números que estamos a buscar.

82
00:04:11,000 --> 00:04:14,000
Se o índice máximo do intervalo que estamos a buscar

83
00:04:14,000 --> 00:04:17,000
sempre menor que o mínimo, o que significa que nós fomos demasiado lonxe.

84
00:04:17,000 --> 00:04:20,000
Como o número non estaba na matriz de entrada, nós voltar -1

85
00:04:20,000 --> 00:04:24,000
para indicar que nada se atopou.

86
00:04:24,000 --> 00:04:26,000
>> Debe ter notado que a este algoritmo para traballar,

87
00:04:26,000 --> 00:04:28,000
a lista de números ten que ser resolto.

88
00:04:28,000 --> 00:04:31,000
Noutras palabras, só podemos atopar 144 usando busca binaria

89
00:04:31,000 --> 00:04:34,000
todos os números son ordenadas de menor a maior.

90
00:04:34,000 --> 00:04:38,000
Se non fose este o caso, non sería capaz de eliminar a metade dos números en cada etapa.

91
00:04:38,000 --> 00:04:40,000
Polo tanto, temos dúas opcións.

92
00:04:40,000 --> 00:04:43,000
Ou podemos ter unha lista non ordenada e clasificalos lo antes de empregar busca binaria,

93
00:04:43,000 --> 00:04:48,000
ou podemos estar seguro de que a lista de números é clasificada como engadir números a el.

94
00:04:48,000 --> 00:04:50,000
Así, en vez de clasificar só cando temos que buscar,

95
00:04:50,000 --> 00:04:53,000
Por que non manter a lista de clasificados en todos os tempos?

96
00:04:53,000 --> 00:04:57,000
>> Unha forma de manter unha lista de números ordenados ao mesmo tempo, permitindo que

97
00:04:57,000 --> 00:04:59,000
unha para engadir ou cambiar os números da lista

98
00:04:59,000 --> 00:05:02,000
é usando algo chamado unha árbore de busca binaria.

99
00:05:02,000 --> 00:05:05,000
Unha árbore de busca binaria é unha estrutura de datos que ten tres propiedades.

100
00:05:05,000 --> 00:05:09,000
En primeiro lugar, a subárvore esquerda de calquera nodo contén só os valores que son menos de

101
00:05:09,000 --> 00:05:11,000
ou igual ao valor do nodo.

102
00:05:11,000 --> 00:05:15,000
En segundo lugar, o dereito subárvore dun nodo contén só valores que son maiores do que

103
00:05:15,000 --> 00:05:17,000
ou igual ao valor do nodo.

104
00:05:17,000 --> 00:05:20,000
E, finalmente, as subárvores esquerda e dereita de todo nós

105
00:05:20,000 --> 00:05:23,000
tamén son árbores de busca binaria.

106
00:05:23,000 --> 00:05:26,000
Vexamos un exemplo cos mesmos números que usamos anteriormente.

107
00:05:26,000 --> 00:05:30,000
Para aqueles de vostedes que nunca vin unha árbore de ciencia da computación antes,

108
00:05:30,000 --> 00:05:34,000
deixe-me comezar por lle dicir que unha árbore de informática medra para abaixo.

109
00:05:34,000 --> 00:05:36,000
Si, ao contrario de árbores que está acostumado,

110
00:05:36,000 --> 00:05:38,000
a raíz dunha árbore de informática e na parte superior,

111
00:05:38,000 --> 00:05:41,000
e as follas están na parte inferior.

112
00:05:41,000 --> 00:05:45,000
Cada caixa pequena chámase un nó e os nós son conectados uns a outros por arestas.

113
00:05:45,000 --> 00:05:48,000
Así, a raíz desta árbore é un valor do nodo co valor de 13,

114
00:05:48,000 --> 00:05:52,000
que ten dous fillos cos valores 5 e 34.

115
00:05:52,000 --> 00:05:57,000
Unha subárvore é a árbore que está formada só de ollar a unha subseção da árbore enteira.

116
00:05:57,000 --> 00:06:03,000
>> Por exemplo, a sub-árbore esquerda do apartado 3 é a árbore creada polos nós de 0, 1 e 2.

117
00:06:03,000 --> 00:06:06,000
Entón, se volver para as propiedades dunha árbore de busca binaria,

118
00:06:06,000 --> 00:06:09,000
vemos que cada nodo da árbore está de acordo con todas as tres propiedades, é dicir,

119
00:06:09,000 --> 00:06:15,000
subárvore esquerda contén só valores que son menos que ou igual ao valor do nodo;

120
00:06:15,000 --> 00:06:16,000
subárvore dereita de todo nós

121
00:06:16,000 --> 00:06:19,000
contén só valores que son maiores do que ou igual ao valor do nodo, e

122
00:06:19,000 --> 00:06:25,000
subárvores esquerda e dereita de todos os nós tamén son árbores de busca binaria.

123
00:06:25,000 --> 00:06:28,000
Aínda que esta árbore parece diferente, esta é unha árbore de busca binaria válido

124
00:06:28,000 --> 00:06:30,000
para o mesmo conxunto de números.

125
00:06:30,000 --> 00:06:32,000
Por unha cuestión de feito, hai moitas formas posibles que pode crear

126
00:06:32,000 --> 00:06:35,000
unha árbore de busca binaria válida a partir destes números.

127
00:06:35,000 --> 00:06:38,000
Ben, imos volver para o primeiro que creou.

128
00:06:38,000 --> 00:06:40,000
Entón o que podemos facer con esas árbores?

129
00:06:40,000 --> 00:06:44,000
Ben, podemos moi simplemente atopar os valores mínimo e máximo.

130
00:06:44,000 --> 00:06:46,000
Os valores mínimos poden ser atopados por sempre vai cara á esquerda

131
00:06:46,000 --> 00:06:48,000
ata que non haxa ningún nodo para visitar.

132
00:06:48,000 --> 00:06:53,000
Por outra banda, para atopar o máximo simplemente vai para abaixo á dereita en cada momento.

133
00:06:54,000 --> 00:06:56,000
>> Atopou calquera outro número que non sexa o mínimo ou máximo

134
00:06:56,000 --> 00:06:58,000
é tan fácil.

135
00:06:58,000 --> 00:07:00,000
Dicir que estamos a buscar o número 89.

136
00:07:00,000 --> 00:07:03,000
Nós simplemente comprobar o valor de cada nodo e vaia á esquerda ou á dereita,

137
00:07:03,000 --> 00:07:06,000
dependendo de se o valor do nó é menor ou maior que

138
00:07:06,000 --> 00:07:08,000
o que estamos a buscar.

139
00:07:08,000 --> 00:07:11,000
Así, a partir da raíz de 13, vemos que 89 é maior,

140
00:07:11,000 --> 00:07:13,000
e así imos cara á dereita.

141
00:07:13,000 --> 00:07:16,000
A continuación, vemos o nó para 34, e, de novo, vaia á dereita.

142
00:07:16,000 --> 00:07:20,000
89 aínda é superior a 55, polo que seguimos indo cara á dereita.

143
00:07:20,000 --> 00:07:24,000
Nós entón chegar a un nodo co valor de 144 e vai cara á esquerda.

144
00:07:24,000 --> 00:07:26,000
Velaí que, 89 e logo alí.

145
00:07:26,000 --> 00:07:31,000
>> Outra cousa que podemos facer é imprimir todos os números a través da realización dun percorrido en inordem.

146
00:07:31,000 --> 00:07:35,000
Un percorrido en inordem significa imprimir todo na subárvore esquerda

147
00:07:35,000 --> 00:07:37,000
seguida de estampación o propio nodo

148
00:07:37,000 --> 00:07:40,000
e despois seguiu imprimindo todo na subárvore dereita.

149
00:07:40,000 --> 00:07:43,000
Por exemplo, imos tomar a nosa árbore binaria de procura favorito

150
00:07:43,000 --> 00:07:46,000
e imprimir os números en orde de clasificación.

151
00:07:46,000 --> 00:07:49,000
Comezamos a raíz do 13, pero antes de imprimir 13 temos para imprimir

152
00:07:49,000 --> 00:07:51,000
todo na subárvore esquerda.

153
00:07:51,000 --> 00:07:55,000
Entón imos para a 5. Aínda temos que ir máis fondo na árbore ata atopar o nodo máis á esquerda,

154
00:07:55,000 --> 00:07:57,000
que é igual a cero.

155
00:07:57,000 --> 00:08:00,000
Tras a impresión cero, volverse para o 1 e imprimir iso.

156
00:08:00,000 --> 00:08:03,000
Entón imos para a subárvore dereita, que é 2, e imprimir iso.

157
00:08:03,000 --> 00:08:05,000
Agora que estamos a facer que subárvore

158
00:08:05,000 --> 00:08:07,000
podemos volver-se para o 3 e imprimir lo.

159
00:08:07,000 --> 00:08:11,000
Continuando cara arriba, nós imprimimos a 5 e logo o 8.

160
00:08:11,000 --> 00:08:13,000
Agora que xa completou toda a subárvore esquerda,

161
00:08:13,000 --> 00:08:17,000
podemos imprimir a 13 e comezar a traballar na subárvore dereita.

162
00:08:17,000 --> 00:08:21,000
Nós descenda para 34, pero antes de imprimir 34 temos que imprimir a súa subárvore esquerda.

163
00:08:21,000 --> 00:08:27,000
Así, imprimir 21; entón nós comezamos a imprimir 34 e visitar a súa subárvore dereita.

164
00:08:27,000 --> 00:08:31,000
Desde 55 non subárvore esquerda, imprimir-lo e continuar a súa subárvore dereita.

165
00:08:31,000 --> 00:08:36,000
144 ten unha sub-árbore da esquerda, e polo tanto, imprimir a 89, seguíndose a 144,

166
00:08:36,000 --> 00:08:39,000
e finalmente o no máis á dereita de 233.

167
00:08:39,000 --> 00:08:44,000
Alí tes, todos os números son impresos en orde da menor á maior.

168
00:08:44,000 --> 00:08:47,000
>> Engadir algo para a árbore é relativamente indolora tamén.

169
00:08:47,000 --> 00:08:51,000
Todo o que temos que facer é estar seguro de que nós seguimos tres binarios propiedades da árbore de busca

170
00:08:51,000 --> 00:08:53,000
e insira o valor onde hai espazo.

171
00:08:53,000 --> 00:08:55,000
Imos dicir que quere inserir o valor de 7.

172
00:08:55,000 --> 00:08:58,000
Dende 7 é menor que 13, imos cara á esquerda.

173
00:08:58,000 --> 00:09:01,000
Pero é maior que 5, así que atravesan a dereita.

174
00:09:01,000 --> 00:09:04,000
Dende que é menos de 8 e 8 é un nodo folla, nós engadimos 7 para o fillo esquerdo de 8.

175
00:09:04,000 --> 00:09:09,000
Listo! Nós engadimos un número para a nosa árbore de busca binaria.

176
00:09:09,000 --> 00:09:12,000
>> Se pudermos engadir cousas, o mellor é ser capaz de eliminar as cousas tan ben.

177
00:09:12,000 --> 00:09:14,000
Desafortunadamente para nós, a exclusión é un pouco máis complicado -

178
00:09:14,000 --> 00:09:16,000
non moito, pero un pouco.

179
00:09:16,000 --> 00:09:18,000
Hai tres escenarios diferentes que temos que considerar

180
00:09:18,000 --> 00:09:21,000
ao eliminar elementos de árbores de busca binaria.

181
00:09:21,000 --> 00:09:24,000
En primeiro lugar, o caso máis sinxelo é a de que o elemento é un nodo folla.

182
00:09:24,000 --> 00:09:27,000
Neste caso, nós simplemente apaga-lo e continuar co noso negocio.

183
00:09:27,000 --> 00:09:30,000
Dicir que queremos eliminar o 7 que acaba de engadir.

184
00:09:30,000 --> 00:09:34,000
Ben, nós simplemente atopalo, eliminar-lo, e é iso.

185
00:09:35,000 --> 00:09:37,000
O seguinte caso é o nó ten só un fillo.

186
00:09:37,000 --> 00:09:40,000
Aquí podemos eliminar o nodo, pero primeiro temos que ter seguro

187
00:09:40,000 --> 00:09:42,000
para conectar a subárvore que é deixada sen pais

188
00:09:42,000 --> 00:09:44,000
para o pai do nodo que acabou eliminada.

189
00:09:44,000 --> 00:09:47,000
Dicir que queremos borrar 3 da nosa árbore.

190
00:09:47,000 --> 00:09:50,000
Tomamos o elemento fillo dese nó e anexo-lo ao pai do nodo.

191
00:09:50,000 --> 00:09:54,000
Neste caso, estamos agora a poñer o 1 ao 5.

192
00:09:54,000 --> 00:09:57,000
Isto funciona sen ningún problema, xa sabemos, de acordo coa propiedade de árbore binaria de procura,

193
00:09:57,000 --> 00:10:01,000
que todo na subárvore esquerda de 3 era inferior a 5.

194
00:10:01,000 --> 00:10:05,000
Agora que 3 do sub é de tomar coidado, podemos excluílo.

195
00:10:05,000 --> 00:10:08,000
O terceiro e último caso é o máis complexo.

196
00:10:08,000 --> 00:10:11,000
Este é o caso cando o nodo que desexa eliminar ten dous nenos.

197
00:10:11,000 --> 00:10:15,000
Co fin de facer iso, primeiro temos que atopar o nodo que ten o valor máis grande máis próximo,

198
00:10:15,000 --> 00:10:18,000
intercambiar os dous, e despois eliminar o nodo en cuestión.

199
00:10:18,000 --> 00:10:22,000
Teña en conta o nodo que ten o valor máis grande máis próximo non pode ter dous nenos en si

200
00:10:22,000 --> 00:10:26,000
dende o seu fillo esquerdo sería un candidato mellor para o maior seguinte.

201
00:10:26,000 --> 00:10:30,000
Polo tanto, a exclusión dun nodo con dous fillos equivale a cambio de 2 nós,

202
00:10:30,000 --> 00:10:33,000
e despois borrar é tratado por unha das dúas modalidades anteriormente mencionadas.

203
00:10:33,000 --> 00:10:37,000
Por exemplo, imos dicir que queremos borrar o nodo raíz de 13.

204
00:10:37,000 --> 00:10:39,000
O primeiro que facemos é o seguinte maior valor na árbore

205
00:10:39,000 --> 00:10:41,000
que, nese caso, é de 21.

206
00:10:41,000 --> 00:10:46,000
A continuación, cambiar os 2 nós, facendo unha folla 13 e 21 do nó do grupo central.

207
00:10:46,000 --> 00:10:49,000
Agora podemos simplemente eliminar 13.

208
00:10:50,000 --> 00:10:53,000
>> Como mencionado anteriormente, hai moitas formas posibles para facer unha árbore de busca binaria válido.

209
00:10:53,000 --> 00:10:56,000
Desafortunadamente para nós, algúns son peores que outros.

210
00:10:56,000 --> 00:10:59,000
Por exemplo, o que acontece cando nós construímos unha árbore de busca binaria

211
00:10:59,000 --> 00:11:01,000
a partir dunha lista ordenada de números?

212
00:11:01,000 --> 00:11:04,000
Todos os números son só engadidos á dereita en cada etapa.

213
00:11:04,000 --> 00:11:06,000
Cando queremos buscar un número,

214
00:11:06,000 --> 00:11:08,000
non temos elección, pero só de ollar para a dereita en cada etapa.

215
00:11:08,000 --> 00:11:11,000
Isto non é mellor que a procura lineal de todo.

216
00:11:11,000 --> 00:11:13,000
A pesar de non cobre-los aquí, hai outra, máis complexa,

217
00:11:13,000 --> 00:11:16,000
estruturas de datos que asegurarse de que isto non aconteza.

218
00:11:16,000 --> 00:11:18,000
Con todo, unha cousa simple que se pode facer para evitar isto é

219
00:11:18,000 --> 00:11:21,000
só para embaralhar chou os valores de entrada.

220
00:11:21,000 --> 00:11:26,000
É altamente improbable que por casualidade unha lista de números embaralhados está clasificada.

221
00:11:26,000 --> 00:11:29,000
Se este fose o caso, os casinos non permanecer na empresa por moito tempo.

222
00:11:29,000 --> 00:11:31,000
>> Alí ten.

223
00:11:31,000 --> 00:11:34,000
Xa sabe sobre a investigación binaria e árbores de busca binaria.

224
00:11:34,000 --> 00:11:36,000
Son Patrick Schmid, e este é CS50.

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

226
00:11:38,000 --> 00:11:43,000
Unha forma obvia sería a de comprobar a lista de ... [bip]

227
00:11:43,000 --> 00:11:46,000
... O número de elementos ... si

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

229
00:11:50,000 --> 00:11:55,000
Publicar ... nó de 234 ... Augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Que foi -