1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Pesquisa Binário]

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 lhe dei uma lista de nomes de personagens da Disney em ordem alfabética

5
00:00:09,000 --> 00:00:11,000
e pediu-lhe para encontrar o Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
como é que você vai fazer sobre isso?

7
00:00:13,000 --> 00:00:15,000
Uma maneira óbvia seria a de examinar a lista desde o início

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

9
00:00:18,000 --> 00:00:22,000
Mas quando você lê Aladdin, Alice, Ariel, e assim por diante,

10
00:00:22,000 --> 00:00:25,000
você vai logo perceber que a partir da frente da lista não foi uma boa idéia.

11
00:00:25,000 --> 00:00:29,000
Ok, talvez você deve começar a trabalhar para trás a partir do final da lista.

12
00:00:29,000 --> 00:00:33,000
Agora você ler Tarzan, Stitch, Branca de Neve, e assim por diante.

13
00:00:33,000 --> 00:00:36,000
Ainda assim, esta não parece ser a melhor maneira de ir sobre ele.

14
00:00:36,000 --> 00:00:38,000
>> Bem, outra maneira que você pode fazer sobre isso é para tentar diminuir

15
00:00:38,000 --> 00:00:41,000
a lista de nomes que você tem que olhar.

16
00:00:41,000 --> 00:00:43,000
Como você sabe que eles estão em ordem alfabética,

17
00:00:43,000 --> 00:00:45,000
você pode apenas olhar para os nomes no meio da lista

18
00:00:45,000 --> 00:00:49,000
e verifique se o Mickey Mouse é antes ou depois deste nome.

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

20
00:00:51,000 --> 00:00:54,000
você perceberia que a M para Mickey vem depois J para Jasmine,

21
00:00:54,000 --> 00:00:57,000
assim que você simplesmente ignorar a primeira metade da lista.

22
00:00:57,000 --> 00:00:59,000
Então você provavelmente olhar para o topo da última coluna

23
00:00:59,000 --> 00:01:02,000
e ver que ele começa com Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey vem antes de Rapunzel, parece que podemos ignorar a última coluna também.

25
00:01:06,000 --> 00:01:08,000
Continuando a estratégia de busca, você verá rapidamente que Mickey

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

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

28
00:01:14,000 --> 00:01:17,000
>> O que você fez foi basicamente busca binária.

29
00:01:17,000 --> 00:01:22,000
Como este nome indica, ele executa sua estratégia de busca em questão binário.

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

31
00:01:24,000 --> 00:01:27,000
Bem, dada uma lista de itens classificados, o algoritmo de busca binária faz uma decisão binária -

32
00:01:27,000 --> 00:01:33,000
para a esquerda ou para a direita, maior ou menor do que, por ordem alfabética, antes ou depois - em cada ponto.

33
00:01:33,000 --> 00:01:35,000
Agora que temos um nome que vai junto com este algoritmo de busca,

34
00:01:35,000 --> 00:01:38,000
Vejamos outro exemplo, mas desta vez com uma lista de números ordenados.

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

36
00:01:43,000 --> 00:01:46,000
Assim como antes, encontramos o número que está no meio -

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

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

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

40
00:01:57,000 --> 00:01:59,000
Uma vez que agora têm um número par de itens à esquerda,

41
00:01:59,000 --> 00:02:01,000
nós simplesmente escolher um número que está perto da média.

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

43
00:02:03,000 --> 00:02:06,000
Nós poderíamos ter facilmente escolhidos 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Mais uma vez, 144 é maior que 55, portanto, vá para a direita.

45
00:02:11,000 --> 00:02:14,000
Felizmente para nós, o número do meio próximo é 144,

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

47
00:02:16,000 --> 00:02:21,000
Portanto, a fim de encontrar 144 usando pesquisa binária, somos capazes de encontrá-lo em apenas 3 passos.

48
00:02:21,000 --> 00:02:24,000
Se tivéssemos usado busca linear aqui, teria nos levado 12 passos.

49
00:02:24,000 --> 00:02:28,000
Por uma questão de facto, uma vez que este método de pesquisa metades do número de itens

50
00:02:28,000 --> 00:02:31,000
tem que olhar a cada passo, ele vai encontrar o item que está à procura de

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

52
00:02:35,000 --> 00:02:37,000
Agora que nós vimos dois exemplos, vamos dar uma olhada

53
00:02:37,000 --> 00:02:41,000
um pseudocódigo para uma função recursiva que implementa busca binária.

54
00:02:41,000 --> 00:02:44,000
Começando pelo topo, vemos que temos de encontrar uma função que recebe 4 argumentos:

55
00:02:44,000 --> 00:02:47,000
chave, matriz min, e max.

56
00:02:47,000 --> 00:02:51,000
A chave é o número que nós estamos procurando, de forma 144 no exemplo anterior.

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

58
00:02:54,000 --> 00:02:57,000
Mínimo e máximo são os índices das posições mínimas e máximas

59
00:02:57,000 --> 00:02:59,000
que atualmente estamos olhando.

60
00:02:59,000 --> 00:03:03,000
Assim, quando se iniciar, min será zero e max será o índice máximo da matriz.

61
00:03:03,000 --> 00:03:07,000
Como se restringir a pesquisa para baixo, vamos atualizar min e max

62
00:03:07,000 --> 00:03:10,000
para ser apenas a faixa que ainda estamos olhando para dentro

63
00:03:10,000 --> 00:03:12,000
>> Vamos pular para a parte interessante em primeiro lugar.

64
00:03:12,000 --> 00:03:14,000
A primeira coisa que fazemos é encontrar o ponto médio,

65
00:03:14,000 --> 00:03:19,000
o índice que está a meio caminho entre o mínimo eo máximo da matriz que ainda estamos considerando.

66
00:03:19,000 --> 00:03:22,000
Então, olhamos para o valor da matriz em que a localização do ponto médio

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

68
00:03:25,000 --> 00:03:27,000
Se o número em que a posição é menos,

69
00:03:27,000 --> 00:03:31,000
então isso significa que a chave é maior do que todos os números à esquerda dessa posição.

70
00:03:31,000 --> 00:03:33,000
Assim, podemos chamar a função de busca binária, novamente,

71
00:03:33,000 --> 00:03:36,000
mas desta vez, atualizando o min e max parâmetros de ler apenas a metade

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

73
00:03:40,000 --> 00:03:44,000
Por outro lado, se a chave é menor do que o número actual no ponto médio da matriz,

74
00:03:44,000 --> 00:03:47,000
queremos ir para a esquerda e ignorar todos os números que são maiores.

75
00:03:47,000 --> 00:03:52,000
Mais uma vez, chamamos de busca binária, mas desta vez com a gama de min e max updated

76
00:03:52,000 --> 00:03:54,000
para incluir apenas a metade inferior.

77
00:03:54,000 --> 00:03:57,000
Se o valor no ponto médio actual na matriz não é nem

78
00:03:57,000 --> 00:04:01,000
maior do que ou menor do que a chave, então ele tem de ser igual à chave.

79
00:04:01,000 --> 00:04:05,000
Assim, podemos simplesmente retornar o índice ponto médio atual, e estamos a fazer.

80
00:04:05,000 --> 00:04:09,000
Finalmente, esta verificação aqui é para o caso em que o número

81
00:04:09,000 --> 00:04:11,000
não é, na verdade, na matriz de números que estamos procurando.

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

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

84
00:04:17,000 --> 00:04:20,000
Como o número não estava na matriz de entrada, nós retornar -1

85
00:04:20,000 --> 00:04:24,000
para indicar que nada foi encontrado.

86
00:04:24,000 --> 00:04:26,000
>> Você deve ter notado que para este algoritmo para trabalhar,

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

88
00:04:28,000 --> 00:04:31,000
Em outras palavras, só podemos encontrar 144 usando busca binária

89
00:04:31,000 --> 00:04:34,000
se todos os números são ordenados do menor para o maior.

90
00:04:34,000 --> 00:04:38,000
Se não fosse este o caso, não seria capaz de excluir metade dos números em cada etapa.

91
00:04:38,000 --> 00:04:40,000
Portanto, temos duas opções.

92
00:04:40,000 --> 00:04:43,000
Ou podemos ter uma lista não ordenada e classificá-lo antes de usar busca binária,

93
00:04:43,000 --> 00:04:48,000
ou podemos ter certeza de que a lista de números é classificada como adicionar números a ele.

94
00:04:48,000 --> 00:04:50,000
Assim, em vez de classificar apenas quando temos que procurar,

95
00:04:50,000 --> 00:04:53,000
Por que não manter a lista de classificados em todos os tempos?

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

97
00:04:57,000 --> 00:04:59,000
uma para adicionar ou mudar os números da lista

98
00:04:59,000 --> 00:05:02,000
é usando algo chamado uma árvore de busca binária.

99
00:05:02,000 --> 00:05:05,000
Uma árvore de busca binária é uma estrutura de dados que tem três propriedades.

100
00:05:05,000 --> 00:05:09,000
Primeiro, a subárvore esquerda de qualquer nó contém apenas os valores que são menos de

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

102
00:05:11,000 --> 00:05:15,000
Em segundo lugar, o direito subárvore de um nó contém apenas valores que são maiores do que

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

104
00:05:17,000 --> 00:05:20,000
E, finalmente, tanto as subárvores esquerda e direita de todos os nós

105
00:05:20,000 --> 00:05:23,000
também são árvores de busca binária.

106
00:05:23,000 --> 00:05:26,000
Vejamos um exemplo com os mesmos números que usamos anteriormente.

107
00:05:26,000 --> 00:05:30,000
Para aqueles de vocês que nunca vi uma árvore de ciência da computação antes,

108
00:05:30,000 --> 00:05:34,000
deixe-me começar por lhe dizer que uma árvore de informática cresce para baixo.

109
00:05:34,000 --> 00:05:36,000
Sim, ao contrário de árvores que está acostumado,

110
00:05:36,000 --> 00:05:38,000
a raiz de uma árvore de informática é na parte superior,

111
00:05:38,000 --> 00:05:41,000
e as folhas estão na parte inferior.

112
00:05:41,000 --> 00:05:45,000
Cada caixa pequena é chamado um nó e os nós são conectados uns aos outros por arestas.

113
00:05:45,000 --> 00:05:48,000
Assim, a raiz dessa árvore é um valor do nó com o valor de 13,

114
00:05:48,000 --> 00:05:52,000
que tem dois nós filhos com os valores 5 e 34.

115
00:05:52,000 --> 00:05:57,000
Uma subárvore é a árvore que é formada só de olhar para uma subseção da árvore inteira.

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

117
00:06:03,000 --> 00:06:06,000
Então, se voltar para as propriedades de uma árvore de busca binária,

118
00:06:06,000 --> 00:06:09,000
vemos que cada nó da árvore está em conformidade com todas as três propriedades, ou seja,

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

120
00:06:15,000 --> 00:06:16,000
subárvore direita de todos os nós

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

122
00:06:19,000 --> 00:06:25,000
subárvores esquerda e direita de todos os nós também são árvores de busca binária.

123
00:06:25,000 --> 00:06:28,000
Embora esta árvore parece diferente, esta é uma árvore de busca binária válido

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

125
00:06:30,000 --> 00:06:32,000
Por uma questão de fato, há muitas formas possíveis que você pode criar

126
00:06:32,000 --> 00:06:35,000
uma árvore de busca binária válida a partir desses números.

127
00:06:35,000 --> 00:06:38,000
Bem, vamos voltar para o primeiro que criou.

128
00:06:38,000 --> 00:06:40,000
Então o que podemos fazer com essas árvores?

129
00:06:40,000 --> 00:06:44,000
Bem, podemos muito simplesmente encontrar os valores mínimo e máximo.

130
00:06:44,000 --> 00:06:46,000
Os valores mínimos podem ser encontrados por sempre vai para a esquerda

131
00:06:46,000 --> 00:06:48,000
até que não haja mais nenhum nó para visitar.

132
00:06:48,000 --> 00:06:53,000
Por outro lado, para encontrar o máximo simplesmente vai para baixo para a direita em cada momento.

133
00:06:54,000 --> 00:06:56,000
>> Encontrando qualquer outro número que não seja o mínimo ou máximo

134
00:06:56,000 --> 00:06:58,000
é tão fácil.

135
00:06:58,000 --> 00:07:00,000
Dizer que estamos procurando o número 89.

136
00:07:00,000 --> 00:07:03,000
Nós simplesmente verificar o valor de cada nó e vá para a esquerda ou direita,

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

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

139
00:07:08,000 --> 00:07:11,000
Assim, a partir da raiz de 13, vemos que 89 é maior,

140
00:07:11,000 --> 00:07:13,000
e assim vamos para a direita.

141
00:07:13,000 --> 00:07:16,000
Em seguida, vemos o nó para 34, e, novamente, vá para a direita.

142
00:07:16,000 --> 00:07:20,000
89 ainda é superior a 55, por isso continuamos indo para a direita.

143
00:07:20,000 --> 00:07:24,000
Nós então chegar a um nó com o valor de 144 e vá para a esquerda.

144
00:07:24,000 --> 00:07:26,000
Eis que, 89 é logo ali.

145
00:07:26,000 --> 00:07:31,000
>> Outra coisa que podemos fazer é imprimir todos os números através da realização de um percurso em inordem.

146
00:07:31,000 --> 00:07:35,000
Um percurso em inordem significa imprimir tudo na subárvore esquerda

147
00:07:35,000 --> 00:07:37,000
seguida de estampagem o próprio nó

148
00:07:37,000 --> 00:07:40,000
e depois seguiu imprimindo tudo na subárvore direita.

149
00:07:40,000 --> 00:07:43,000
Por exemplo, vamos tomar nossa árvore binária de busca favorito

150
00:07:43,000 --> 00:07:46,000
e imprimir os números em ordem de classificação.

151
00:07:46,000 --> 00:07:49,000
Começamos a raiz de 13, mas antes de imprimir 13 temos para imprimir

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

153
00:07:51,000 --> 00:07:55,000
Então vamos para a 5. Nós ainda temos que ir mais fundo na árvore até encontrar o nó mais à esquerda,

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

155
00:07:57,000 --> 00:08:00,000
Após a impressão zero, voltar-se para o 1 e imprimir isso.

156
00:08:00,000 --> 00:08:03,000
Então vamos para a subárvore direita, que é 2, e imprimir isso.

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

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

159
00:08:07,000 --> 00:08:11,000
Continuando para cima, nós imprimimos a 5 e depois o 8.

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

161
00:08:13,000 --> 00:08:17,000
nós podemos imprimir a 13 e começar a trabalhar na subárvore direita.

162
00:08:17,000 --> 00:08:21,000
Nós desça para 34, mas antes de imprimir 34 temos de imprimir sua subárvore esquerda.

163
00:08:21,000 --> 00:08:27,000
Assim, imprimir 21; então nós começamos a imprimir 34 e visitar a sua subárvore direita.

164
00:08:27,000 --> 00:08:31,000
Desde 55 não tem subárvore esquerda, imprimi-lo e continuar a sua subárvore direita.

165
00:08:31,000 --> 00:08:36,000
144 tem uma sub-árvore da esquerda, e portanto, imprimir a 89, seguindo-se a 144,

166
00:08:36,000 --> 00:08:39,000
e finalmente o nó mais à direita de 233.

167
00:08:39,000 --> 00:08:44,000
Lá você tem, todos os números são impressos em ordem da menor para a maior.

168
00:08:44,000 --> 00:08:47,000
>> Acrescentar algo para a árvore é relativamente indolor também.

169
00:08:47,000 --> 00:08:51,000
Tudo o que temos a fazer é ter certeza de que nós seguimos três binários propriedades da árvore de busca

170
00:08:51,000 --> 00:08:53,000
e insira o valor onde há espaço.

171
00:08:53,000 --> 00:08:55,000
Vamos dizer que deseja inserir o valor de 7.

172
00:08:55,000 --> 00:08:58,000
Desde 7 é menor que 13, vamos para a esquerda.

173
00:08:58,000 --> 00:09:01,000
Mas é maior do que 5, de modo que atravessam para a direita.

174
00:09:01,000 --> 00:09:04,000
Desde que é menos de 8 e 8 é um nó folha, nós adicionamos 7 para o filho esquerdo de 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Nós adicionamos um número para nossa árvore de busca binária.

176
00:09:09,000 --> 00:09:12,000
>> Se pudermos acrescentar coisas, é melhor ser capaz de apagar as coisas tão bem.

177
00:09:12,000 --> 00:09:14,000
Infelizmente para nós, a exclusão é um pouco mais complicado -

178
00:09:14,000 --> 00:09:16,000
não muito, mas um pouco.

179
00:09:16,000 --> 00:09:18,000
Há três cenários diferentes que temos de considerar

180
00:09:18,000 --> 00:09:21,000
ao excluir elementos de árvores de busca binária.

181
00:09:21,000 --> 00:09:24,000
Em primeiro lugar, o caso mais fácil é a de que o elemento é um nó de folha.

182
00:09:24,000 --> 00:09:27,000
Neste caso, nós simplesmente excluí-lo e continuar com o nosso negócio.

183
00:09:27,000 --> 00:09:30,000
Dizer que queremos excluir o 7 que acabou de adicionar.

184
00:09:30,000 --> 00:09:34,000
Bem, nós simplesmente encontrá-lo, removê-lo, e é isso.

185
00:09:35,000 --> 00:09:37,000
O próximo caso é se o nó tem apenas um filho.

186
00:09:37,000 --> 00:09:40,000
Aqui podemos excluir o nó, mas primeiro temos que ter certeza

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

188
00:09:42,000 --> 00:09:44,000
para o pai do nó que acabou excluída.

189
00:09:44,000 --> 00:09:47,000
Dizer que queremos apagar 3 da nossa árvore.

190
00:09:47,000 --> 00:09:50,000
Tomamos o elemento filho desse nó e anexá-lo ao pai do nó.

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

192
00:09:54,000 --> 00:09:57,000
Isso funciona sem nenhum problema, pois sabemos, de acordo com a propriedade de árvore binária de busca,

193
00:09:57,000 --> 00:10:01,000
que tudo 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 cuidado, podemos excluí-lo.

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

196
00:10:08,000 --> 00:10:11,000
Este é o caso quando o nó que pretende eliminar tem duas crianças.

197
00:10:11,000 --> 00:10:15,000
A fim de fazer isso, primeiro temos que encontrar o nó que tem o valor maior mais próximo,

198
00:10:15,000 --> 00:10:18,000
trocar os dois, e depois excluir o nó em questão.

199
00:10:18,000 --> 00:10:22,000
Observe o nó que tem o valor maior mais próximo não pode ter duas crianças em si

200
00:10:22,000 --> 00:10:26,000
desde o seu filho esquerdo seria um candidato melhor para o maior seguinte.

201
00:10:26,000 --> 00:10:30,000
Portanto, a exclusão de um nó com dois filhos equivale a troca de 2 nós,

202
00:10:30,000 --> 00:10:33,000
e depois apagar é tratado por uma das duas regras acima mencionadas.

203
00:10:33,000 --> 00:10:37,000
Por exemplo, vamos dizer que queremos excluir o nó raiz de 13.

204
00:10:37,000 --> 00:10:39,000
A primeira coisa que fazemos é encontrar o próximo maior valor na árvore

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

206
00:10:41,000 --> 00:10:46,000
Em seguida, trocar os 2 nós, fazendo uma folha 13 e 21 do nó do grupo central.

207
00:10:46,000 --> 00:10:49,000
Agora podemos simplesmente apagar 13.

208
00:10:50,000 --> 00:10:53,000
>> Como mencionado anteriormente, existem muitas formas possíveis para fazer uma árvore de busca binária válido.

209
00:10:53,000 --> 00:10:56,000
Infelizmente para nós, alguns são piores que outros.

210
00:10:56,000 --> 00:10:59,000
Por exemplo, o que acontece quando nós construímos uma árvore de busca binária

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

212
00:11:01,000 --> 00:11:04,000
Todos os números são apenas adicionados à direita em cada etapa.

213
00:11:04,000 --> 00:11:06,000
Quando queremos procurar um número,

214
00:11:06,000 --> 00:11:08,000
não temos escolha, mas só de olhar para a direita em cada etapa.

215
00:11:08,000 --> 00:11:11,000
Isto não é melhor do que a busca linear de todo.

216
00:11:11,000 --> 00:11:13,000
Apesar de não cobri-los aqui, há outra, mais complexa,

217
00:11:13,000 --> 00:11:16,000
estruturas de dados que se certificar de que isso não aconteça.

218
00:11:16,000 --> 00:11:18,000
No entanto, uma coisa simples que pode ser feito para evitar isso é

219
00:11:18,000 --> 00:11:21,000
apenas para embaralhar aleatoriamente os valores de entrada.

220
00:11:21,000 --> 00:11:26,000
É altamente improvável que por acaso uma lista de números embaralhados está classificada.

221
00:11:26,000 --> 00:11:29,000
Se este fosse o caso, os casinos não permanecer na empresa por muito tempo.

222
00:11:29,000 --> 00:11:31,000
>> Lá você tem.

223
00:11:31,000 --> 00:11:34,000
Você já sabe sobre a pesquisa binária e árvores de busca binária.

224
00:11:34,000 --> 00:11:36,000
Sou 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
Uma maneira óbvia seria a de verificar a lista de ... [bip]

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

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

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

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