1
00:00:00,000 --> 00:00:03,346
>> [REPRODUCCIÓN DE MÚSICA]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: De acuerdo.

4
00:00:06,220 --> 00:00:08,140
Así que la búsqueda binaria es un
algoritmo podemos utilizar

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

6
00:00:10,530 --> 00:00:14,710
A diferencia de búsqueda lineal, se requiere un
condición especial se reunió con anterioridad,

7
00:00:14,710 --> 00:00:19,020
pero es mucho más eficiente si
esa condición es, de hecho, se ha reunido.

8
00:00:19,020 --> 00:00:20,470
>> ¿Cuál es la idea aquí?

9
00:00:20,470 --> 00:00:21,780
es divide y vencerás.

10
00:00:21,780 --> 00:00:25,100
Queremos reducir el tamaño de
el área de búsqueda a la mitad cada vez

11
00:00:25,100 --> 00:00:27,240
con el fin de encontrar un número de destino.

12
00:00:27,240 --> 00:00:29,520
Aquí es donde esa condición
entra en juego, sin embargo.

13
00:00:29,520 --> 00:00:32,740
Sólo podemos aprovechar el poder de
eliminando medio de los elementos

14
00:00:32,740 --> 00:00:36,070
sin siquiera mirar
si la matriz se ordenan.

15
00:00:36,070 --> 00:00:39,200
>> Si se trata de una mezcla completa hasta,
No podemos salir de la mano

16
00:00:39,200 --> 00:00:42,870
descartar medio de los elementos, porque
no sabemos lo que estamos desechando.

17
00:00:42,870 --> 00:00:45,624
Pero si la matriz está ordenada,
podemos hacer eso, porque nosotros

18
00:00:45,624 --> 00:00:48,040
saber que todo a la
izquierdo de donde actualmente estamos

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

20
00:00:50,500 --> 00:00:52,300
Y todo a la
derecha de donde estamos

21
00:00:52,300 --> 00:00:55,040
debe ser mayor que el valor
actualmente estamos viendo.

22
00:00:55,040 --> 00:00:58,710
>> ¿Cuál es el pseudocódigo
pasos para la búsqueda binaria?

23
00:00:58,710 --> 00:01:02,310
Repetimos este proceso hasta que el
matriz o, a medida que avancemos a través,

24
00:01:02,310 --> 00:01:07,740
matrices sub, pequeñas piezas de
la matriz original, es de tamaño 0.

25
00:01:07,740 --> 00:01:10,960
Calcular el punto medio
de la matriz sub actual.

26
00:01:10,960 --> 00:01:14,460
>> Si el valor que estás buscando es
en ese elemento de la matriz, para.

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

28
00:01:15,030 --> 00:01:16,550
Eso es genial.

29
00:01:16,550 --> 00:01:19,610
De lo contrario, si el objetivo es
menos de lo que está en el medio,

30
00:01:19,610 --> 00:01:23,430
por lo que si el valor que estamos buscando
para es menor que lo que vemos,

31
00:01:23,430 --> 00:01:26,780
repetir este proceso otra vez, pero
cambiar el punto final, en vez

32
00:01:26,780 --> 00:01:29,300
de ser el original
completar arsenal completo,

33
00:01:29,300 --> 00:01:34,110
para ser justo a la izquierda
de donde nos miramos.

34
00:01:34,110 --> 00:01:38,940
>> Sabíamos que el medio era demasiado alto,
o el objetivo era menos de la mitad,

35
00:01:38,940 --> 00:01:42,210
y por lo que debe existir, si
existe en absoluto en el array,

36
00:01:42,210 --> 00:01:44,660
en algún lugar a la izquierda del punto medio.

37
00:01:44,660 --> 00:01:48,120
Y así vamos a establecer la matriz
ubicación justo a la izquierda

38
00:01:48,120 --> 00:01:51,145
del punto medio como el nuevo punto final.

39
00:01:51,145 --> 00:01:53,770
A la inversa, si el objetivo es
mayor que lo que está en el medio,

40
00:01:53,770 --> 00:01:55,750
hacemos lo mismo exacta
proceso, pero en lugar de eso

41
00:01:55,750 --> 00:01:59,520
cambiar el punto de inicio para ser
justo a la derecha del punto medio

42
00:01:59,520 --> 00:02:00,680
simplemente calculamos.

43
00:02:00,680 --> 00:02:03,220
Y entonces, comenzamos el proceso de nuevo.

44
00:02:03,220 --> 00:02:05,220
>> Vamos a visualizar esto, ¿de acuerdo?

45
00:02:05,220 --> 00:02:08,620
Así que hay mucho que hacer y aquí,
pero aquí es una matriz de los 15 elementos.

46
00:02:08,620 --> 00:02:11,400
Y vamos a hacer el seguimiento
de muchas más cosas en esta ocasión.

47
00:02:11,400 --> 00:02:13,870
Así que en búsqueda lineal, estábamos
simplemente preocuparse por un objetivo.

48
00:02:13,870 --> 00:02:15,869
Pero esta vez queremos
preocuparse por dónde estamos

49
00:02:15,869 --> 00:02:18,480
empezando a mirar, donde
nos detenemos en busca,

50
00:02:18,480 --> 00:02:21,876
y lo que es el punto medio
de la matriz actual.

51
00:02:21,876 --> 00:02:23,250
Así que aquí vamos con búsqueda binaria.

52
00:02:23,250 --> 00:02:25,290
Estamos bastante bueno para ir, ¿verdad?

53
00:02:25,290 --> 00:02:28,650
Yo sólo voy a poner abajo
a continuación aquí un conjunto de índices.

54
00:02:28,650 --> 00:02:32,430
Esto es básicamente lo que el elemento
de la matriz de que estamos hablando.

55
00:02:32,430 --> 00:02:34,500
Con la búsqueda lineal, se
cuidado, ya que nos

56
00:02:34,500 --> 00:02:36,800
necesita saber cuántos
elementos que estamos interactuando sobre,

57
00:02:36,800 --> 00:02:40,010
pero en realidad no importa lo que
elemento que actualmente estamos viendo.

58
00:02:40,010 --> 00:02:41,014
En búsqueda binaria, lo que hacemos.

59
00:02:41,014 --> 00:02:42,930
Y así, esos son sólo
allí como una pequeña guía.

60
00:02:42,930 --> 00:02:44,910
>> Así que podemos empezar, ¿no?

61
00:02:44,910 --> 00:02:46,240
Bueno, no del todo.

62
00:02:46,240 --> 00:02:48,160
Recuerde lo que dije
sobre búsqueda binaria?

63
00:02:48,160 --> 00:02:50,955
No podemos hacerlo en una
array sin ordenar o de lo contrario,

64
00:02:50,955 --> 00:02:55,820
no estamos garantizando que el
ciertos elementos o valores no son

65
00:02:55,820 --> 00:02:57,650
siendo accidentalmente
desechado cuando sólo

66
00:02:57,650 --> 00:02:59,920
decidir ignorar medio de la matriz.

67
00:02:59,920 --> 00:03:02,574
>> Así que paso una con búsqueda binaria
es que debe tener un conjunto ordenado.

68
00:03:02,574 --> 00:03:05,240
Y usted puede utilizar cualquiera de la clasificación
algoritmos que hemos hablado

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

70
00:03:06,700 --> 00:03:10,370
Así que ahora, estamos en una posición en la
podemos realizar la búsqueda binaria.

71
00:03:10,370 --> 00:03:12,560
>> Así que vamos a repetir el proceso
paso a paso y tener

72
00:03:12,560 --> 00:03:14,830
la pista de lo que está sucediendo a medida que avanzamos.

73
00:03:14,830 --> 00:03:17,980
Así que lo primero que hay que hacer es calcular
el punto medio de la matriz actual.

74
00:03:17,980 --> 00:03:20,620
Bueno, vamos a decir que somos, en primer
todo, buscando el valor 19.

75
00:03:20,620 --> 00:03:22,290
Estamos tratando de encontrar el número 19.

76
00:03:22,290 --> 00:03:25,380
El primer elemento de esta
matriz se encuentra en el índice cero,

77
00:03:25,380 --> 00:03:28,880
y el último elemento de esta
matriz se encuentra en el índice 14.

78
00:03:28,880 --> 00:03:31,430
Y así vamos a llamar a los de inicio y fin.

79
00:03:31,430 --> 00:03:35,387
>> Así se calcula el punto medio por
la adición de 0, más 14 dividido por 2;

80
00:03:35,387 --> 00:03:36,720
punto medio bastante sencillo.

81
00:03:36,720 --> 00:03:40,190
Y podemos decir que
el punto medio es ahora 7.

82
00:03:40,190 --> 00:03:43,370
Así que es 15 lo que estamos buscando?

83
00:03:43,370 --> 00:03:43,940
No, no es.

84
00:03:43,940 --> 00:03:45,270
Estamos buscando a 19.

85
00:03:45,270 --> 00:03:49,400
Pero sabemos que 19 es mayor
de lo que encontramos en el centro.

86
00:03:49,400 --> 00:03:52,470
>> Así que lo que podemos hacer es
cambiar el punto de inicio

87
00:03:52,470 --> 00:03:57,280
para ser justo a la derecha de la
punto medio, y repetir el proceso de nuevo.

88
00:03:57,280 --> 00:04:01,690
Y cuando lo hacemos, decimos ahora la
nuevo punto de partida es la ubicación matriz 8.

89
00:04:01,690 --> 00:04:07,220
Lo que hemos hecho es efectiva
todo lo ignorado a la izquierda de 15.

90
00:04:07,220 --> 00:04:09,570
Hemos eliminado media
del problema, y ​​ahora,

91
00:04:09,570 --> 00:04:13,510
en lugar de tener que buscar
más de 15 elementos en nuestra serie,

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

93
00:04:15,610 --> 00:04:17,706
Así que 8 es el nuevo punto de inicio.

94
00:04:17,706 --> 00:04:19,600
14 sigue siendo el punto final.

95
00:04:19,600 --> 00:04:21,430
>> Y ahora, vamos sobre esto de nuevo.

96
00:04:21,430 --> 00:04:22,810
Calculamos el nuevo punto medio.

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

98
00:04:27,130 --> 00:04:28,660
¿Es esto lo que estamos buscando?

99
00:04:28,660 --> 00:04:30,110
No, no es.

100
00:04:30,110 --> 00:04:32,930
Estamos buscando a un valor que es
menos de lo que acabamos de encontrar.

101
00:04:32,930 --> 00:04:34,721
Así que vamos a repetir
el proceso de nuevo.

102
00:04:34,721 --> 00:04:38,280
Vamos a cambiar el punto final a
ser justo a la izquierda del punto medio.

103
00:04:38,280 --> 00:04:41,800
Así que el nuevo punto final se convierte en 10.

104
00:04:41,800 --> 00:04:44,780
Y ahora, esa es la única parte de
la matriz que tenemos que clasificar.

105
00:04:44,780 --> 00:04:48,460
Así que ahora hemos eliminado
12 de los 15 elementos.

106
00:04:48,460 --> 00:04:51,550
Sabemos que si 19
existe en la matriz,

107
00:04:51,550 --> 00:04:57,210
debe existir en algún lugar entre el elemento
número 8 y el elemento número 10.

108
00:04:57,210 --> 00:04:59,400
>> Así se calcula el nuevo punto medio nuevo.

109
00:04:59,400 --> 00:05:02,900
8 más 10 es 18, dividido por 2 es 9.

110
00:05:02,900 --> 00:05:05,074
Y en este caso, mira, la
objetivo está en el centro.

111
00:05:05,074 --> 00:05:06,740
Nos encontramos exactamente lo que estamos buscando.

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

113
00:05:07,780 --> 00:05:10,561
Hemos completado con éxito
una búsqueda binaria.

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

115
00:05:11,060 --> 00:05:13,930
Así que sabemos que este algoritmo
funciona si el objetivo es

116
00:05:13,930 --> 00:05:16,070
en algún lugar dentro de la matriz.

117
00:05:16,070 --> 00:05:19,060
¿Funciona esto algoritmo si
el objetivo no está en la matriz?

118
00:05:19,060 --> 00:05:20,810
Bueno, vamos a empezar que
de nuevo, y esta vez,

119
00:05:20,810 --> 00:05:23,380
vamos a ver para el elemento
16, que visualmente se puede ver

120
00:05:23,380 --> 00:05:25,620
no existe en cualquier parte de la matriz.

121
00:05:25,620 --> 00:05:27,110
>> El punto de inicio es de nuevo 0.

122
00:05:27,110 --> 00:05:28,590
El punto final es de nuevo 14.

123
00:05:28,590 --> 00:05:32,490
Esos son los índices de la primera y
últimos elementos de la matriz completa.

124
00:05:32,490 --> 00:05:36,057
Y vamos a ir a través del proceso que acabamos de
fue a través de nuevo, tratando de encontrar 16,

125
00:05:36,057 --> 00:05:39,140
a pesar de que visualmente, ya podemos
dicen que no va a estar allí.

126
00:05:39,140 --> 00:05:43,450
Sólo queremos asegurarnos de que este algoritmo
será, de hecho, siguen trabajando de alguna manera

127
00:05:43,450 --> 00:05:46,310
y no sólo nos dejan
atrapado en un bucle infinito.

128
00:05:46,310 --> 00:05:48,190
>> ¿Cuál es el primer paso?

129
00:05:48,190 --> 00:05:50,230
Calcular el punto medio
de la matriz actual.

130
00:05:50,230 --> 00:05:52,790
¿Cuál es el punto medio
de la matriz actual?

131
00:05:52,790 --> 00:05:54,410
Bueno, es 7, ¿no?

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

133
00:05:57,560 --> 00:05:59,280
Es de 15 lo que estamos buscando?

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

135
00:05:59,780 --> 00:06:02,930
Está bastante cerca, pero estamos buscando
por un valor un poco más grande que eso.

136
00:06:02,930 --> 00:06:06,310
>> Así que sabemos que se va a
estar en ninguna parte a la izquierda de 15.

137
00:06:06,310 --> 00:06:08,540
El objetivo es mayor que
lo que está en el punto medio.

138
00:06:08,540 --> 00:06:12,450
Y así nos pusimos en el nuevo punto de partida para
ser justo a la derecha del centro.

139
00:06:12,450 --> 00:06:16,130
El punto medio es actualmente 7, por lo que
digamos que el nuevo punto de inicio es 8.

140
00:06:16,130 --> 00:06:18,130
Y lo que hemos efectivamente
hecho nuevo es ignorado

141
00:06:18,130 --> 00:06:21,150
toda la mitad izquierda de la matriz.

142
00:06:21,150 --> 00:06:23,750
>> Ahora, repetimos el
procesar una vez más.

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

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

145
00:06:29,350 --> 00:06:31,060
Es de 23 lo que estamos buscando?

146
00:06:31,060 --> 00:06:31,870
Lamentablemente no.

147
00:06:31,870 --> 00:06:34,930
Estamos buscando a un valor
que es menor que 23.

148
00:06:34,930 --> 00:06:37,850
Y así, en este caso, vamos
para cambiar el punto final para ser justo

149
00:06:37,850 --> 00:06:40,035
a la izquierda del punto medio actual.

150
00:06:40,035 --> 00:06:43,440
El punto medio actual es 11, y
así que vamos a establecer el nuevo punto final

151
00:06:43,440 --> 00:06:46,980
para la próxima vez que vayamos
a través de este proceso a 10.

152
00:06:46,980 --> 00:06:48,660
>> Una vez más, pasamos por el proceso de nuevo.

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

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

155
00:06:53,100 --> 00:06:54,750
Es de 19 lo que estamos buscando?

156
00:06:54,750 --> 00:06:55,500
Lamentablemente no.

157
00:06:55,500 --> 00:06:58,050
Todavía estamos buscando
un número menor que eso.

158
00:06:58,050 --> 00:07:02,060
Así que vamos a cambiar el punto final de este tiempo
para ser justo a la izquierda del punto medio.

159
00:07:02,060 --> 00:07:05,532
El punto medio es actualmente 9,
por lo que el punto final será de 8.

160
00:07:05,532 --> 00:07:07,920
Y ahora, sólo estamos buscando
en un solo elemento de la matriz.

161
00:07:07,920 --> 00:07:10,250
>> ¿Cuál es el punto medio de este conjunto?

162
00:07:10,250 --> 00:07:13,459
Bueno, empieza a las 8, que
termina a las 8, el punto medio es 8.

163
00:07:13,459 --> 00:07:14,750
¿Eso es lo que estamos buscando?

164
00:07:14,750 --> 00:07:16,339
¿Estamos buscando 17?

165
00:07:16,339 --> 00:07:17,380
No, estamos en busca de 16.

166
00:07:17,380 --> 00:07:20,160
Así que si existe en la matriz,
debe existir en alguna parte

167
00:07:20,160 --> 00:07:21,935
a la izquierda de donde actualmente somos.

168
00:07:21,935 --> 00:07:23,060
¿Entonces, que vamos a hacer?

169
00:07:23,060 --> 00:07:26,610
Bueno, vamos a establecer el punto final a ser sólo
a la izquierda del punto medio actual.

170
00:07:26,610 --> 00:07:29,055
Así que vamos a cambiar el punto final a 7.

171
00:07:29,055 --> 00:07:32,120
¿Ves lo que acaba de
que pasó aquí, sin embargo?

172
00:07:32,120 --> 00:07:33,370
Busque aquí ahora.

173
00:07:33,370 --> 00:07:35,970
>> Start es ahora mayor que fin.

174
00:07:35,970 --> 00:07:39,620
Efectivamente, los dos extremos
de nuestra gama han cruzado,

175
00:07:39,620 --> 00:07:42,252
y el punto de inicio es
ahora después de que el punto final.

176
00:07:42,252 --> 00:07:43,960
Bueno, eso no lo hace
tiene sentido, ¿verdad?

177
00:07:43,960 --> 00:07:47,960
Así que ahora, lo que podemos decir es que
tener una matriz de tamaño sub 0.

178
00:07:47,960 --> 00:07:50,110
Y una vez que estamos llegado a
este punto, podemos ahora

179
00:07:50,110 --> 00:07:53,940
garantizar que el elemento 16
no existe en la matriz,

180
00:07:53,940 --> 00:07:56,280
debido a que el punto de partida
y el punto final han cruzado.

181
00:07:56,280 --> 00:07:58,340
Y por lo que no está ahí.

182
00:07:58,340 --> 00:08:01,340
Ahora, observe que esto es ligeramente
diferente a la del punto de inicio y fin

183
00:08:01,340 --> 00:08:02,900
punto que se encuentre el mismo.

184
00:08:02,900 --> 00:08:05,030
Si hubiéramos estado buscando
para el 17, tendría

185
00:08:05,030 --> 00:08:08,870
estado de la matriz, y el punto de inicio
y el punto final de la última iteración

186
00:08:08,870 --> 00:08:11,820
antes de que esos puntos cruzados,
habríamos encontrado 17 allí.

187
00:08:11,820 --> 00:08:15,510
Es sólo cuando cruzan que podemos
garantiza que el elemento no

188
00:08:15,510 --> 00:08:17,180
existir en la matriz.

189
00:08:17,180 --> 00:08:20,260
>> Así que vamos a echar mucho menos
pasos que la búsqueda lineal.

190
00:08:20,260 --> 00:08:23,250
En el peor de los casos, tuvimos
para dividir una lista de n elementos

191
00:08:23,250 --> 00:08:27,770
en repetidas ocasiones por la mitad para encontrar el objetivo,
ya sea porque el elemento de destino

192
00:08:27,770 --> 00:08:33,110
será en algún lugar de la última
división, o no existe en absoluto.

193
00:08:33,110 --> 00:08:37,830
Así que en el peor de los casos, tenemos que
dividir el array-- lo sabes?

194
00:08:37,830 --> 00:08:40,510
Iniciar sesión de n veces; nosotros
tener que cortar el problema

195
00:08:40,510 --> 00:08:42,610
en medio de un cierto número de veces.

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

197
00:08:45,160 --> 00:08:46,510
>> ¿Cuál es el mejor de los casos?

198
00:08:46,510 --> 00:08:48,899
Bueno, la primera vez que
calcular el punto medio,

199
00:08:48,899 --> 00:08:50,190
encontramos lo que estamos buscando.

200
00:08:50,190 --> 00:08:52,150
En todo lo anterior
ejemplos de búsqueda binaria

201
00:08:52,150 --> 00:08:55,489
que acabamos ido, si tuviéramos
estado buscando el elemento 15,

202
00:08:55,489 --> 00:08:57,030
habríamos encontrado que inmediatamente.

203
00:08:57,030 --> 00:08:58,321
Eso fue al principio.

204
00:08:58,321 --> 00:09:01,200
Ese fue el punto medio de
el primer intento de una división

205
00:09:01,200 --> 00:09:03,950
de una división en la búsqueda binaria.

206
00:09:03,950 --> 00:09:06,350
>> Y así, en el peor
caso, la búsqueda binaria funciona

207
00:09:06,350 --> 00:09:11,580
en el registro de n, que es sustancialmente mejor
de búsqueda lineal, en el peor de los casos.

208
00:09:11,580 --> 00:09:16,210
En el mejor caso, binario
búsqueda se ejecuta en el omega de 1.

209
00:09:16,210 --> 00:09:18,990
Así que la búsqueda binaria es mucho
mejor que la búsqueda lineal,

210
00:09:18,990 --> 00:09:23,270
pero usted tiene que tratar con el proceso de
ordenar la matriz antes de poder

211
00:09:23,270 --> 00:09:26,140
aprovechar el poder de búsqueda binaria.

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

213
00:09:27,130 --> 00:09:29,470
Esto es CS 50.

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