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: Todo ben.

4
00:00:06,220 --> 00:00:08,140
Entón, é unha procura binaria
algoritmo podemos utilizar

5
00:00:08,140 --> 00:00:10,530
para atopar un elemento dentro dunha matriz.

6
00:00:10,530 --> 00:00:14,710
A diferenza de busca lineal, require un
condición especial responderse previamente,

7
00:00:14,710 --> 00:00:19,020
pero é moito máis eficiente que
esta condición é, de feito, cumpridos.

8
00:00:19,020 --> 00:00:20,470
>> Entón, cal é a idea aquí?

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

10
00:00:21,780 --> 00:00:25,100
Queremos reducir o tamaño da
a área de investigación para a metade de cada vez

11
00:00:25,100 --> 00:00:27,240
a fin de atopar un número de destino.

12
00:00:27,240 --> 00:00:29,520
Este é o lugar onde esta condición
entra en xogo, con todo.

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

14
00:00:32,740 --> 00:00:36,070
sen sequera ollar para
Los a matriz está clasificada.

15
00:00:36,070 --> 00:00:39,200
>> Se é unha mestura complétase,
Non podemos simplemente fóra de man

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

17
00:00:42,870 --> 00:00:45,624
Pero, se a matriz é clasificada,
podemos facer iso, porque nós

18
00:00:45,624 --> 00:00:48,040
sei que todo o
deixou de onde estamos actualmente

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

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

21
00:00:52,300 --> 00:00:55,040
debe ser maior que o valor
actualmente estamos mirando.

22
00:00:55,040 --> 00:00:58,710
>> Entón, cal é o pseudocódigo
pasos para a investigación binaria?

23
00:00:58,710 --> 00:01:02,310
Nós repetimos este proceso ata que o
matriz ou, a medida que proseguimos a través,

24
00:01:02,310 --> 00:01:07,740
matrices sub, pequenos anacos de
a matriz orixinal, é de tamaño 0.

25
00:01:07,740 --> 00:01:10,960
Calcular o punto medio
do sub matriz actual.

26
00:01:10,960 --> 00:01:14,460
>> Se o valor que está a buscar
en que elemento da matriz, pare.

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

28
00:01:15,030 --> 00:01:16,550
Isto é óptimo.

29
00:01:16,550 --> 00:01:19,610
Se non, se o destino
menos que o que está no medio,

30
00:01:19,610 --> 00:01:23,430
por iso, se o valor que estamos a buscar
para é menor que o que vemos,

31
00:01:23,430 --> 00:01:26,780
cabo este proceso de novo, pero
cambiar o punto final, en vez

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

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

34
00:01:34,110 --> 00:01:38,940
>> Sabiamos que o medio era moi alto,
ou o destino era menos que a media,

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

36
00:01:42,210 --> 00:01:44,660
un lugar para a esquerda do punto medio.

37
00:01:44,660 --> 00:01:48,120
E por iso imos definir a matriz
localización, só á esquerda

38
00:01:48,120 --> 00:01:51,145
do punto medio como o punto final.

39
00:01:51,145 --> 00:01:53,770
Por outra banda, se o destino
maior que o que está no medio,

40
00:01:53,770 --> 00:01:55,750
facemos exactamente o mesmo
proceso, pero no seu lugar,

41
00:01:55,750 --> 00:01:59,520
cambiar o punto de inicio para ser
só para a dereita do punto medio

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

43
00:02:00,680 --> 00:02:03,220
E entón, comezamos o proceso de novo.

44
00:02:03,220 --> 00:02:05,220
>> Imos ver iso, OK?

45
00:02:05,220 --> 00:02:08,620
Polo tanto, hai moita cousa a suceder e aquí,
pero aquí está unha matriz de 15 elementos.

46
00:02:08,620 --> 00:02:11,400
E nós estamos indo a ser manter o control
de moito máis cousas neste momento.

47
00:02:11,400 --> 00:02:13,870
Así, en busca lineal, fomos
só preocuparse un obxectivo.

48
00:02:13,870 --> 00:02:15,869
Pero esta vez queremos
se preocupan onde estamos

49
00:02:15,869 --> 00:02:18,480
empezando a mirar, onde
que estamos parando mirando,

50
00:02:18,480 --> 00:02:21,876
e cal é o punto medio
da matriz actual.

51
00:02:21,876 --> 00:02:23,250
Entón, imos con busca binaria.

52
00:02:23,250 --> 00:02:25,290
Estamos practicamente listo para ir, non?

53
00:02:25,290 --> 00:02:28,650
Eu só vou poñer para abaixo
debaixo aquí un conxunto de índices.

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

55
00:02:32,430 --> 00:02:34,500
Coa busca lineal, nós
coidado, na medida en que

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

57
00:02:36,800 --> 00:02:40,010
pero nós realmente non ligo para o que
elemento que está mirando.

58
00:02:40,010 --> 00:02:41,014
En busca binaria, o que facemos.

59
00:02:41,014 --> 00:02:42,930
E así estes son só
alí como un pequeno guía.

60
00:02:42,930 --> 00:02:44,910
>> Así, podemos comezar, non?

61
00:02:44,910 --> 00:02:46,240
Ben, non exactamente.

62
00:02:46,240 --> 00:02:48,160
Lembre que eu dixen
preto de busca binaria?

63
00:02:48,160 --> 00:02:50,955
Non podemos facelo nun
matriz sen clasificar ou máis,

64
00:02:50,955 --> 00:02:55,820
que non son garantir que o
certos elementos ou valores non son

65
00:02:55,820 --> 00:02:57,650
sendo accidentalmente
descartados cando nós só

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

67
00:02:59,920 --> 00:03:02,574
>> Entón, paso un investigación binaria
é que ten que ter unha matriz clasificada.

68
00:03:02,574 --> 00:03:05,240
E pode utilizar calquera dos selección
algoritmos que falamos

69
00:03:05,240 --> 00:03:06,700
para chegar a esa posición.

70
00:03:06,700 --> 00:03:10,370
Entón, agora, estamos nunha posición onde
podemos realizar a procura binaria.

71
00:03:10,370 --> 00:03:12,560
>> Entón, imos repetir o proceso
paso a paso e manter

72
00:03:12,560 --> 00:03:14,830
ao tanto do que está a suceder a medida que avanzamos.

73
00:03:14,830 --> 00:03:17,980
Así, o primeiro que temos que facer é calcular
o punto medio da gama actual.

74
00:03:17,980 --> 00:03:20,620
Ben, imos dicir que estamos, en primeiro lugar
todo, ollando para o valor 19.

75
00:03:20,620 --> 00:03:22,290
Estamos intentando atopar o número 19.

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

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

78
00:03:28,880 --> 00:03:31,430
E por iso imos chamar os inicio e fin.

79
00:03:31,430 --> 00:03:35,387
>> Entón nós calculamos o punto medio por
adición de 0, máis 14 dividido por 2;

80
00:03:35,387 --> 00:03:36,720
punto medio moi sinxelo.

81
00:03:36,720 --> 00:03:40,190
E podemos dicir que
o punto medio é agora 7.

82
00:03:40,190 --> 00:03:43,370
Así, é de 15 o que estamos a buscar?

83
00:03:43,370 --> 00:03:43,940
Non, non é.

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

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

86
00:03:49,400 --> 00:03:52,470
>> Entón, o que podemos facer é
cambiar o punto de inicio

87
00:03:52,470 --> 00:03:57,280
ser só dereito da
punto medio, e repita o proceso de novo.

88
00:03:57,280 --> 00:04:01,690
E cando facemos iso, nós agora din que a
novo punto de partida é a localización matriz 8.

89
00:04:01,690 --> 00:04:07,220
O que fixemos é eficaz
ignorado todo á 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
en vez de ter que buscar
máis de 15 elementos na nosa matriz,

92
00:04:13,510 --> 00:04:15,610
só temos que buscar máis de 7.

93
00:04:15,610 --> 00:04:17,706
Entón 8 é o punto de partida.

94
00:04:17,706 --> 00:04:19,600
14 aínda é o punto final.

95
00:04:19,600 --> 00:04:21,430
>> E agora, nós imos sobre iso de novo.

96
00:04:21,430 --> 00:04:22,810
Nós calculamos o punto medio.

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

98
00:04:27,130 --> 00:04:28,660
Isto é o que estamos a buscar?

99
00:04:28,660 --> 00:04:30,110
Non, non é.

100
00:04:30,110 --> 00:04:32,930
Estamos á procura de un valor que é
menos que o que acaba de atopar.

101
00:04:32,930 --> 00:04:34,721
Entón, nós estamos indo a repetir
o proceso de novo.

102
00:04:34,721 --> 00:04:38,280
Nós imos cambiar o punto final para
ser só para a dereita do punto medio.

103
00:04:38,280 --> 00:04:41,800
Así, o punto final pasa a ser 10.

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

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

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

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

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

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

110
00:05:02,900 --> 00:05:05,074
E neste caso, mira, o
obxectivo está no medio.

111
00:05:05,074 --> 00:05:06,740
Atopamos o que estamos buscando.

112
00:05:06,740 --> 00:05:07,780
Podemos parar.

113
00:05:07,780 --> 00:05:10,561
Nós Feito con éxito
unha investigación binaria.

114
00:05:10,561 --> 00:05:11,060
Todo ben.

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

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 traballo se
o obxectivo non está na matriz?

118
00:05:19,060 --> 00:05:20,810
Ben, imos volvelo
de novo, e esta vez,

119
00:05:20,810 --> 00:05:23,380
imos ollar para o elemento
16, que visualmente vemos

120
00:05:23,380 --> 00:05:25,620
non existe en calquera lugar na matriz.

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

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

123
00:05:28,590 --> 00:05:32,490
Estes son os índices da primeira e
últimos elementos da matriz completa.

124
00:05:32,490 --> 00:05:36,057
E nós imos pasar polo proceso que acabamos
pasou por unha vez, intentando atopar 16,

125
00:05:36,057 --> 00:05:39,140
aínda visualmente, xa podemos
dicir que non vai estar alí.

126
00:05:39,140 --> 00:05:43,450
Nós só queremos que seguro este algoritmo
será, de feito, seguen a traballar de algunha maneira

127
00:05:43,450 --> 00:05:46,310
e non só deixar-nos
preso nun loop infinito.

128
00:05:46,310 --> 00:05:48,190
>> Entón, cal é o primeiro paso?

129
00:05:48,190 --> 00:05:50,230
Calcular o punto medio
da matriz actual.

130
00:05:50,230 --> 00:05:52,790
Cal é o punto medio
da matriz actual?

131
00:05:52,790 --> 00:05:54,410
Ben, é 7, non?

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

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

134
00:05:59,280 --> 00:05:59,780
Non.

135
00:05:59,780 --> 00:06:02,930
É moi preto, pero nós estamos mirando
para un valor algo maior que iso.

136
00:06:02,930 --> 00:06:06,310
>> Entón, nós sabemos que vai
estar en ningunha parte da esquerda de 15.

137
00:06:06,310 --> 00:06:08,540
O obxectivo é maior que
o que está no punto medio.

138
00:06:08,540 --> 00:06:12,450
E, así, establecer o punto de partida para
ser só dereito de medio.

139
00:06:12,450 --> 00:06:16,130
O punto medio é actualmente 7, así
digamos que o punto de partida é 8.

140
00:06:16,130 --> 00:06:18,130
E o que temos efectivamente
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, repetimos o
procesar unha vez máis.

143
00:06:23,750 --> 00:06:24,910
Calcular o punto medio.

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

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

146
00:06:31,060 --> 00:06:31,870
Desgraciadamente non.

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

148
00:06:34,930 --> 00:06:37,850
E así, neste caso, imos
para cambiar o punto final para ser só

149
00:06:37,850 --> 00:06:40,035
á esquerda do punto medio do curso.

150
00:06:40,035 --> 00:06:43,440
O punto medio de corrente é de 11, e
así que imos definir o punto final

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

152
00:06:46,980 --> 00:06:48,660
>> De novo, nós pasar polo proceso de novo.

153
00:06:48,660 --> 00:06:49,640
Calcular o punto medio.

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

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

156
00:06:54,750 --> 00:06:55,500
Desgraciadamente non.

157
00:06:55,500 --> 00:06:58,050
Aínda estamos a buscar
un número menor que iso.

158
00:06:58,050 --> 00:07:02,060
Entón, nós imos cambiar o punto final a estas alturas
ser só para a dereita do punto medio.

159
00:07:02,060 --> 00:07:05,532
O punto medio é actualmente 9,
de xeito que o punto final será 8.

160
00:07:05,532 --> 00:07:07,920
E agora, estamos só buscando
a matriz dun único elemento.

161
00:07:07,920 --> 00:07:10,250
>> Cal é o punto medio desta matriz?

162
00:07:10,250 --> 00:07:13,459
Ben, comeza ás 8, el
remata en 8, o punto medio é de 8.

163
00:07:13,459 --> 00:07:14,750
É iso o que estamos a buscar?

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

165
00:07:16,339 --> 00:07:17,380
Non, nós estamos mirando para 16.

166
00:07:17,380 --> 00:07:20,160
Polo tanto, se está na matriz,
debe existir algún lugar

167
00:07:20,160 --> 00:07:21,935
á esquerda de onde estamos hoxe.

168
00:07:21,935 --> 00:07:23,060
Entón, o que imos facer?

169
00:07:23,060 --> 00:07:26,610
Ben, imos definir o punto final para ser só
á esquerda do punto medio do curso.

170
00:07:26,610 --> 00:07:29,055
Entón, nós imos cambiar o punto final a 7.

171
00:07:29,055 --> 00:07:32,120
Ve o que
pasou aquí, aínda?

172
00:07:32,120 --> 00:07:33,370
Olle aquí enriba agora.

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

174
00:07:35,970 --> 00:07:39,620
Efectivamente, as dúas extremidades
da nosa matriz cruzar,

175
00:07:39,620 --> 00:07:42,252
e é o punto de partida
Agora, tras o punto final.

176
00:07:42,252 --> 00:07:43,960
Ben, iso non fai
fai calquera sentido, non?

177
00:07:43,960 --> 00:07:47,960
Entón, agora, o que podemos dicir é que
ten un sub matriz de tamaño 0.

178
00:07:47,960 --> 00:07:50,110
E xa que estamos chegara a
Neste punto, podemos agora

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

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

181
00:07:56,280 --> 00:07:58,340
E así el non está alí.

182
00:07:58,340 --> 00:08:01,340
Agora, teña en conta que este é lixeiramente
diferente do que o punto de inicio e final

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

184
00:08:02,900 --> 00:08:05,030
Se tivésemos sido buscando
para 17, tería

185
00:08:05,030 --> 00:08:08,870
foi na matriz, eo punto de inicio
e punto final desta última iteración

186
00:08:08,870 --> 00:08:11,820
antes deses puntos cruzados,
que encontraría 17 alí.

187
00:08:11,820 --> 00:08:15,510
É só cando cruzan o que pudermos
garantir que o elemento non fai

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

189
00:08:17,180 --> 00:08:20,260
>> Entón, imos ter unha chea menos
etapas que busca lineal.

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

191
00:08:23,250 --> 00:08:27,770
repetidamente ao medio para atopar o destino,
ben porque o elemento obxecto

192
00:08:27,770 --> 00:08:33,110
vai estar nalgún lugar no último
división, ou que non existe en todo.

193
00:08:33,110 --> 00:08:37,830
Entón, no peor dos casos, hai que
dividir os array-- sabe?

194
00:08:37,830 --> 00:08:40,510
Rexistro de n veces; nós
Ten que cortar o problema

195
00:08:40,510 --> 00:08:42,610
en metade dun certo número de veces.

196
00:08:42,610 --> 00:08:45,160
Ese número de veces que se log n.

197
00:08:45,160 --> 00:08:46,510
>> Cal é o mellor escenario?

198
00:08:46,510 --> 00:08:48,899
Ben, a primeira vez que
calcular o punto medio,

199
00:08:48,899 --> 00:08:50,190
atopamos o que estamos buscando.

200
00:08:50,190 --> 00:08:52,150
En toda a anterior
exemplos de busca binaria

201
00:08:52,150 --> 00:08:55,489
nós só ir máis, se tivésemos
está a buscar o elemento 15,

202
00:08:55,489 --> 00:08:57,030
que encontraría inmediatamente.

203
00:08:57,030 --> 00:08:58,321
Isto foi no inicio.

204
00:08:58,321 --> 00:09:01,200
Ese foi o punto medio de
o primeiro intento dunha escisión

205
00:09:01,200 --> 00:09:03,950
dunha división na procura binaria.

206
00:09:03,950 --> 00:09:06,350
>> E así, no peor
caso, busca binaria execútase

207
00:09:06,350 --> 00:09:11,580
no rexistro n, o cal é substancialmente mellor
que busca lineal, no peor dos casos.

208
00:09:11,580 --> 00:09:16,210
No mellor dos casos, binario
busca execútase en omega de 1.

209
00:09:16,210 --> 00:09:18,990
Así, busca binaria é moi
mellor que a procura lineal,

210
00:09:18,990 --> 00:09:23,270
pero tes que xestionar o proceso de
clasificando súa matriz antes de se

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

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

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

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