1
00:00:00,000 --> 00:00:03,346
>> [Música tocando]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Tudo bem.

4
00:00:06,220 --> 00:00:08,140
Então, é uma busca binária
algoritmo podemos usar

5
00:00:08,140 --> 00:00:10,530
para encontrar um elemento dentro de uma matriz.

6
00:00:10,530 --> 00:00:14,710
Ao contrário de busca linear, requer um
condição especial ser atendidas previamente,

7
00:00:14,710 --> 00:00:19,020
mas é muito mais eficiente se
essa condição é, de facto, cumpridos.

8
00:00:19,020 --> 00:00:20,470
>> Então, qual é a idéia aqui?

9
00:00:20,470 --> 00:00:21,780
é dividir e conquistar.

10
00:00:21,780 --> 00:00:25,100
Queremos reduzir o tamanho da
a área de pesquisa para metade de cada vez

11
00:00:25,100 --> 00:00:27,240
a fim de encontrar um número de destino.

12
00:00:27,240 --> 00:00:29,520
Este é o lugar onde essa condição
entra em jogo, no entanto.

13
00:00:29,520 --> 00:00:32,740
Nós só pode alavancar o poder de
eliminando metade dos elementos

14
00:00:32,740 --> 00:00:36,070
sem sequer olhar para
-los se a matriz está classificada.

15
00:00:36,070 --> 00:00:39,200
>> Se for uma mistura completa-se,
Não podemos simplesmente fora de mão

16
00:00:39,200 --> 00:00:42,870
descartar metade dos elementos, porque
não sabemos o que estamos descartando.

17
00:00:42,870 --> 00:00:45,624
Mas, se a matriz é classificada,
nós podemos fazer isso, porque nós

18
00:00:45,624 --> 00:00:48,040
sei que tudo ao
deixou de onde estamos atualmente

19
00:00:48,040 --> 00:00:50,500
deve ser inferior a
valor que estamos atualmente.

20
00:00:50,500 --> 00:00:52,300
E tudo para o
certo de onde estamos

21
00:00:52,300 --> 00:00:55,040
deve ser maior do que o valor
atualmente estamos olhando.

22
00:00:55,040 --> 00:00:58,710
>> Então, qual é o pseudocódigo
passos para a pesquisa binária?

23
00:00:58,710 --> 00:01:02,310
Nós repetimos este processo até que o
matriz ou, à medida que prosseguimos através,

24
00:01:02,310 --> 00:01:07,740
matrizes sub, pequenos pedaços de
a matriz original, é de tamanho 0.

25
00:01:07,740 --> 00:01:10,960
Calcular o ponto médio
do sub matriz atual.

26
00:01:10,960 --> 00:01:14,460
>> Se o valor que você está procurando
em que elemento da matriz, pare.

27
00:01:14,460 --> 00:01:15,030
Vc achou.

28
00:01:15,030 --> 00:01:16,550
Isso é ótimo.

29
00:01:16,550 --> 00:01:19,610
Caso contrário, se o destino for
menos do que o que está no meio,

30
00:01:19,610 --> 00:01:23,430
por isso, se o valor que estamos procurando
para é menor do que o que vemos,

31
00:01:23,430 --> 00:01:26,780
repetir esse processo novamente, mas
alterar o ponto final, em vez

32
00:01:26,780 --> 00:01:29,300
de ser o original
completar gama completa,

33
00:01:29,300 --> 00:01:34,110
para ser apenas para a esquerda
de onde nós apenas olhou.

34
00:01:34,110 --> 00:01:38,940
>> Sabíamos que o meio era muito alto,
ou o alvo era menos do que a média,

35
00:01:38,940 --> 00:01:42,210
e por isso deve existir, se ela
existe de todo na matriz,

36
00:01:42,210 --> 00:01:44,660
um lugar para a esquerda do ponto médio.

37
00:01:44,660 --> 00:01:48,120
E por isso vamos definir a matriz
localização, apenas à esquerda

38
00:01:48,120 --> 00:01:51,145
do ponto médio como o novo ponto final.

39
00:01:51,145 --> 00:01:53,770
Por outro lado, se o destino for
maior do que o que está no meio,

40
00:01:53,770 --> 00:01:55,750
fazemos exatamente o mesmo
processo, mas em vez disso,

41
00:01:55,750 --> 00:01:59,520
alterar o ponto de início para ser
apenas para a direita do ponto médio

42
00:01:59,520 --> 00:02:00,680
nós apenas calculado.

43
00:02:00,680 --> 00:02:03,220
E então, começamos o processo novamente.

44
00:02:03,220 --> 00:02:05,220
>> Vamos visualizar isso, OK?

45
00:02:05,220 --> 00:02:08,620
Portanto, há muita coisa acontecendo e aqui,
mas aqui está uma matriz de 15 elementos.

46
00:02:08,620 --> 00:02:11,400
E nós estamos indo para ser manter o controle
de muito mais coisas neste momento.

47
00:02:11,400 --> 00:02:13,870
Assim, em busca linear, fomos
apenas se preocupar com um alvo.

48
00:02:13,870 --> 00:02:15,869
Mas desta vez queremos
se preocupam com onde estamos

49
00:02:15,869 --> 00:02:18,480
começando a olhar, onde
que estamos parando olhando,

50
00:02:18,480 --> 00:02:21,876
e qual é o ponto médio
da matriz atual.

51
00:02:21,876 --> 00:02:23,250
Então, vamos lá com busca binária.

52
00:02:23,250 --> 00:02:25,290
Estamos praticamente pronto para ir, certo?

53
00:02:25,290 --> 00:02:28,650
Eu só vou colocar para baixo
abaixo aqui um conjunto de índices.

54
00:02:28,650 --> 00:02:32,430
Esta é, basicamente, apenas o elemento
da matriz que estamos falando.

55
00:02:32,430 --> 00:02:34,500
Com a busca linear, nós
cuidado, na medida em que

56
00:02:34,500 --> 00:02:36,800
precisa saber quantas
elementos que estamos iterando,

57
00:02:36,800 --> 00:02:40,010
mas nós realmente não ligo para o que
elemento que está olhando.

58
00:02:40,010 --> 00:02:41,014
Em busca binária, o que fazemos.

59
00:02:41,014 --> 00:02:42,930
E assim esses são apenas
lá como um pequeno guia.

60
00:02:42,930 --> 00:02:44,910
>> Assim, podemos começar, certo?

61
00:02:44,910 --> 00:02:46,240
Bem, não exatamente.

62
00:02:46,240 --> 00:02:48,160
Lembre-se que eu disse
cerca de busca binária?

63
00:02:48,160 --> 00:02:50,955
Não podemos fazê-lo em um
matriz não triados ou mais,

64
00:02:50,955 --> 00:02:55,820
que não são garantindo que o
certos elementos ou valores não são

65
00:02:55,820 --> 00:02:57,650
sendo acidentalmente
descartados quando nós apenas

66
00:02:57,650 --> 00:02:59,920
decidir ignorar metade da matriz.

67
00:02:59,920 --> 00:03:02,574
>> Então, passo um com pesquisa binária
é que você deve ter uma matriz classificada.

68
00:03:02,574 --> 00:03:05,240
E você pode usar qualquer um dos triagem
algoritmos que falamos

69
00:03:05,240 --> 00:03:06,700
para chegar a essa posição.

70
00:03:06,700 --> 00:03:10,370
Então, agora, estamos em uma posição onde
podemos executar a busca binária.

71
00:03:10,370 --> 00:03:12,560
>> Então, vamos repetir o processo
passo a passo e manter

72
00:03:12,560 --> 00:03:14,830
a par do que está acontecendo à medida que avançamos.

73
00:03:14,830 --> 00:03:17,980
Assim, o primeiro que precisamos fazer é calcular
o ponto médio da gama corrente.

74
00:03:17,980 --> 00:03:20,620
Bem, vamos dizer que estamos, em primeiro lugar
tudo, olhando para o valor 19.

75
00:03:20,620 --> 00:03:22,290
Nós estamos tentando encontrar o número 19.

76
00:03:22,290 --> 00:03:25,380
O primeiro elemento do presente
matriz está localizada no índice zero,

77
00:03:25,380 --> 00:03:28,880
e o último elemento da presente
matriz está localizada no índice 14.

78
00:03:28,880 --> 00:03:31,430
E por isso vamos chamar aqueles início e fim.

79
00:03:31,430 --> 00:03:35,387
>> Então nós calculamos o ponto médio por
adição de 0, mais 14 dividido por 2;

80
00:03:35,387 --> 00:03:36,720
ponto médio bastante simples.

81
00:03:36,720 --> 00:03:40,190
E podemos dizer que
o ponto médio é agora 7.

82
00:03:40,190 --> 00:03:43,370
Assim, é de 15 o que estamos procurando?

83
00:03:43,370 --> 00:03:43,940
Não é não.

84
00:03:43,940 --> 00:03:45,270
Estamos à procura de 19.

85
00:03:45,270 --> 00:03:49,400
Mas sabemos que 19 é maior
do que o que nós no meio.

86
00:03:49,400 --> 00:03:52,470
>> Então, o que nós podemos fazer é
alterar o ponto de início

87
00:03:52,470 --> 00:03:57,280
ser apenas para a direita da
ponto médio, e repita o processo novamente.

88
00:03:57,280 --> 00:04:01,690
E quando fazemos isso, nós agora dizem que a
novo ponto de partida é a localização matriz 8.

89
00:04:01,690 --> 00:04:07,220
O que temos feito é eficaz
ignorado tudo para a esquerda de 15.

90
00:04:07,220 --> 00:04:09,570
Nós eliminamos metade
do problema, e agora,

91
00:04:09,570 --> 00:04:13,510
em vez de ter que procurar
mais de 15 elementos em nossa matriz,

92
00:04:13,510 --> 00:04:15,610
só temos que procurar mais de 7.

93
00:04:15,610 --> 00:04:17,706
Então 8 é o novo ponto de partida.

94
00:04:17,706 --> 00:04:19,600
14 ainda é o ponto final.

95
00:04:19,600 --> 00:04:21,430
>> E agora, nós vamos sobre isso novamente.

96
00:04:21,430 --> 00:04:22,810
Nós calculamos o novo ponto médio.

97
00:04:22,810 --> 00:04:27,130
8 mais 14 é 22, dividido por 2 é de 11.

98
00:04:27,130 --> 00:04:28,660
É isso que estamos procurando?

99
00:04:28,660 --> 00:04:30,110
Não é não.

100
00:04:30,110 --> 00:04:32,930
Estamos à procura de um valor que é
menos do que o que acabou de encontrar.

101
00:04:32,930 --> 00:04:34,721
Então, nós estamos indo para repetir
o processo novamente.

102
00:04:34,721 --> 00:04:38,280
Nós vamos mudar o ponto final para
ser apenas para a esquerda do ponto médio.

103
00:04:38,280 --> 00:04:41,800
Assim, o novo ponto final torna-se 10.

104
00:04:41,800 --> 00:04:44,780
E agora, que é a única parte do
a matriz temos que classificar completamente.

105
00:04:44,780 --> 00:04:48,460
Portanto, temos agora eliminado
12 dos 15 elementos.

106
00:04:48,460 --> 00:04:51,550
Sabemos que, se 19
existe na matriz, ele

107
00:04:51,550 --> 00:04:57,210
deve existir algum lugar entre o elemento
número 8 e elemento de número 10.

108
00:04:57,210 --> 00:04:59,400
>> Então nós calculamos o novo ponto central novamente.

109
00:04:59,400 --> 00:05:02,900
8 acrescido de 10 é 18, dividido por 2 é 9.

110
00:05:02,900 --> 00:05:05,074
E, neste caso, olha, o
alvo está no meio.

111
00:05:05,074 --> 00:05:06,740
Encontramos exatamente o que estamos procurando.

112
00:05:06,740 --> 00:05:07,780
Nós podemos parar.

113
00:05:07,780 --> 00:05:10,561
Nós concluído com êxito
uma pesquisa binária.

114
00:05:10,561 --> 00:05:11,060
Tudo certo.

115
00:05:11,060 --> 00:05:13,930
Então, nós sabemos que este algoritmo
funciona se o alvo é

116
00:05:13,930 --> 00:05:16,070
algures no interior da matriz.

117
00:05:16,070 --> 00:05:19,060
Será que este algoritmo de trabalho se
o alvo não está na matriz?

118
00:05:19,060 --> 00:05:20,810
Bem, vamos iniciá-lo
novamente, e desta vez,

119
00:05:20,810 --> 00:05:23,380
vamos olhar para o elemento
16, que visualmente podemos ver

120
00:05:23,380 --> 00:05:25,620
não existe em qualquer lugar na matriz.

121
00:05:25,620 --> 00:05:27,110
>> O ponto de partida é novamente 0.

122
00:05:27,110 --> 00:05:28,590
O ponto final é novamente 14.

123
00:05:28,590 --> 00:05:32,490
Esses são os índices da primeira e
últimos elementos da matriz completa.

124
00:05:32,490 --> 00:05:36,057
E nós vamos passar pelo processo que acabamos
passou por mais uma vez, tentando encontrar 16,

125
00:05:36,057 --> 00:05:39,140
embora visualmente, já podemos
dizer que não vai estar lá.

126
00:05:39,140 --> 00:05:43,450
Nós apenas queremos ter certeza este algoritmo
será, de fato, continuam a trabalhar de alguma forma

127
00:05:43,450 --> 00:05:46,310
e não apenas deixar-nos
preso em um loop infinito.

128
00:05:46,310 --> 00:05:48,190
>> Então, qual é o primeiro passo?

129
00:05:48,190 --> 00:05:50,230
Calcular o ponto médio
da matriz atual.

130
00:05:50,230 --> 00:05:52,790
Qual é o ponto médio
da matriz atual?

131
00:05:52,790 --> 00:05:54,410
Bem, é 7, certo?

132
00:05:54,410 --> 00:05:57,560
14 mais 0 dividido por 2 a 7.

133
00:05:57,560 --> 00:05:59,280
15 é o que estamos procurando?

134
00:05:59,280 --> 00:05:59,780
Não.

135
00:05:59,780 --> 00:06:02,930
É muito perto, mas nós estamos olhando
para um valor um pouco maior do que isso.

136
00:06:02,930 --> 00:06:06,310
>> Então, nós sabemos que ele vai
estar em lugar nenhum à esquerda de 15.

137
00:06:06,310 --> 00:06:08,540
O alvo é maior do que
o que está no ponto médio.

138
00:06:08,540 --> 00:06:12,450
E, assim, definir o novo ponto de partida para
ser apenas para a direita de meio.

139
00:06:12,450 --> 00:06:16,130
O ponto médio é actualmente 7, assim
digamos que o novo ponto de partida é 8.

140
00:06:16,130 --> 00:06:18,130
E o que nós temos efetivamente
feito de novo é ignorado

141
00:06:18,130 --> 00:06:21,150
toda a metade esquerda da matriz.

142
00:06:21,150 --> 00:06:23,750
>> Agora, nós repetimos o
processar mais uma vez.

143
00:06:23,750 --> 00:06:24,910
Calcular o novo ponto médio.

144
00:06:24,910 --> 00:06:29,350
8 mais 14 é 22, dividido por 2 é de 11.

145
00:06:29,350 --> 00:06:31,060
23 é o que estamos procurando?

146
00:06:31,060 --> 00:06:31,870
Infelizmente não.

147
00:06:31,870 --> 00:06:34,930
Estamos à procura de um valor
que é inferior a 23.

148
00:06:34,930 --> 00:06:37,850
E assim, neste caso, nós vamos
para mudar o ponto final para ser apenas

149
00:06:37,850 --> 00:06:40,035
para a esquerda do ponto médio do curso.

150
00:06:40,035 --> 00:06:43,440
O ponto médio de corrente é de 11, e
por isso vamos definir o novo ponto final

151
00:06:43,440 --> 00:06:46,980
para a próxima vez que vamos
por este processo a 10.

152
00:06:46,980 --> 00:06:48,660
>> Novamente, nós passar pelo processo novamente.

153
00:06:48,660 --> 00:06:49,640
Calcular o ponto médio.

154
00:06:49,640 --> 00:06:53,100
8 mais 10 dividido por 2 é 9.

155
00:06:53,100 --> 00:06:54,750
19 é o que estamos procurando?

156
00:06:54,750 --> 00:06:55,500
Infelizmente não.

157
00:06:55,500 --> 00:06:58,050
Nós ainda estamos procurando
um número menor do que isso.

158
00:06:58,050 --> 00:07:02,060
Então, nós vamos mudar o ponto final neste momento
ser apenas para a esquerda do ponto médio.

159
00:07:02,060 --> 00:07:05,532
O ponto médio é actualmente 9,
de modo que o ponto final será 8.

160
00:07:05,532 --> 00:07:07,920
E agora, estamos apenas à procura
a matriz de um único elemento.

161
00:07:07,920 --> 00:07:10,250
>> Qual é o ponto médio dessa matriz?

162
00:07:10,250 --> 00:07:13,459
Bem, começa às 8, ele
termina em 8, o ponto médio é de 8.

163
00:07:13,459 --> 00:07:14,750
É isso o que estamos procurando?

164
00:07:14,750 --> 00:07:16,339
Estamos à procura de 17?

165
00:07:16,339 --> 00:07:17,380
Não, nós estamos olhando para 16.

166
00:07:17,380 --> 00:07:20,160
Portanto, se ela existe na matriz,
ele deve existir algum lugar

167
00:07:20,160 --> 00:07:21,935
para a esquerda de onde estamos atualmente.

168
00:07:21,935 --> 00:07:23,060
Então, o que vamos fazer?

169
00:07:23,060 --> 00:07:26,610
Bem, vamos definir o ponto final para ser apenas
para a esquerda do ponto médio do curso.

170
00:07:26,610 --> 00:07:29,055
Então, nós vamos mudar o ponto final a 7.

171
00:07:29,055 --> 00:07:32,120
Você vê o que apenas
aconteceu aqui, embora?

172
00:07:32,120 --> 00:07:33,370
Olhe aqui em cima agora.

173
00:07:33,370 --> 00:07:35,970
>> Iniciar agora é maior que final.

174
00:07:35,970 --> 00:07:39,620
Efetivamente, as duas extremidades
da nossa matriz ter cruzado,

175
00:07:39,620 --> 00:07:42,252
e é o ponto de partida
Agora, após o ponto final.

176
00:07:42,252 --> 00:07:43,960
Bem, isso não faz
faz qualquer sentido, certo?

177
00:07:43,960 --> 00:07:47,960
Então, agora, o que podemos dizer é que
tem um sub matriz de tamanho 0.

178
00:07:47,960 --> 00:07:50,110
E uma vez que estamos chegado a
Neste ponto, podemos agora

179
00:07:50,110 --> 00:07:53,940
garantir que elemento 16
não existe na matriz,

180
00:07:53,940 --> 00:07:56,280
porque o ponto de partida
e ponto final cruzaram.

181
00:07:56,280 --> 00:07:58,340
E assim ele não está lá.

182
00:07:58,340 --> 00:08:01,340
Agora, observe que este é ligeiramente
diferente do que o ponto inicial e final

183
00:08:01,340 --> 00:08:02,900
apontar sendo o mesmo.

184
00:08:02,900 --> 00:08:05,030
Se tivéssemos sido à procura
para 17, teria

185
00:08:05,030 --> 00:08:08,870
sido na matriz, e o ponto de início
e ponto final dessa última iteração

186
00:08:08,870 --> 00:08:11,820
antes desses pontos cruzados,
que teria encontrado 17 lá.

187
00:08:11,820 --> 00:08:15,510
É só quando eles cruzam o que pudermos
garantir que o elemento não faz

188
00:08:15,510 --> 00:08:17,180
existem na matriz.

189
00:08:17,180 --> 00:08:20,260
>> Então, vamos ter um monte menos
etapas do que busca linear.

190
00:08:20,260 --> 00:08:23,250
No pior caso, tivemos
para dividir uma lista de n elementos

191
00:08:23,250 --> 00:08:27,770
repetidamente ao meio para encontrar o alvo,
quer porque o elemento alvo

192
00:08:27,770 --> 00:08:33,110
vai estar em algum lugar no último
divisão, ou ele não existe em tudo.

193
00:08:33,110 --> 00:08:37,830
Então, na pior das hipóteses, temos que
dividir os array-- você sabe?

194
00:08:37,830 --> 00:08:40,510
Log de n vezes; nós
tem que cortar o problema

195
00:08:40,510 --> 00:08:42,610
em metade de um certo número de vezes.

196
00:08:42,610 --> 00:08:45,160
Esse número de vezes que é log n.

197
00:08:45,160 --> 00:08:46,510
>> Qual é o melhor cenário?

198
00:08:46,510 --> 00:08:48,899
Bem, a primeira vez que
calcular o ponto médio,

199
00:08:48,899 --> 00:08:50,190
encontramos o que estamos procurando.

200
00:08:50,190 --> 00:08:52,150
Em toda a anterior
exemplos de busca binária

201
00:08:52,150 --> 00:08:55,489
nós apenas ido mais, se tivéssemos
está procurando o elemento 15,

202
00:08:55,489 --> 00:08:57,030
que teria encontrado que imediatamente.

203
00:08:57,030 --> 00:08:58,321
Isso foi no início.

204
00:08:58,321 --> 00:09:01,200
Esse foi o ponto médio de
a primeira tentativa de uma cisão

205
00:09:01,200 --> 00:09:03,950
de uma divisão na busca binária.

206
00:09:03,950 --> 00:09:06,350
>> E assim, no pior
caso, busca binária é executado

207
00:09:06,350 --> 00:09:11,580
no registo n, o qual é substancialmente melhor
que busca linear, no pior dos casos.

208
00:09:11,580 --> 00:09:16,210
No melhor dos casos, binário
busca é executado em omega de 1.

209
00:09:16,210 --> 00:09:18,990
Assim, busca binária é muito
melhor do que a busca linear,

210
00:09:18,990 --> 00:09:23,270
mas você tem que lidar com o processo de
classificando sua matriz antes de se poder

211
00:09:23,270 --> 00:09:26,140
alavancar o poder de busca binária.

212
00:09:26,140 --> 00:09:27,130
>> Eu sou Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Este é CS 50.

214
00:09:29,470 --> 00:09:31,070