>> [REPRODUCCIÓN DE MÚSICA]
>> DOUG LLOYD: De acuerdo.
Así que la búsqueda binaria es un algoritmo podemos utilizar
para encontrar un elemento dentro de una matriz.
A diferencia de búsqueda lineal, se requiere un condición especial se reunió con anterioridad,
pero es mucho más eficiente si esa condición es, de hecho, se ha reunido.
>> ¿Cuál es la idea aquí?
es divide y vencerás.
Queremos reducir el tamaño de el área de búsqueda a la mitad cada vez
con el fin de encontrar un número de destino.
Aquí es donde esa condición entra en juego, sin embargo.
Sólo podemos aprovechar el poder de eliminando medio de los elementos
sin siquiera mirar si la matriz se ordenan.
>> Si se trata de una mezcla completa hasta, No podemos salir de la mano
descartar medio de los elementos, porque no sabemos lo que estamos desechando.
Pero si la matriz está ordenada, podemos hacer eso, porque nosotros
saber que todo a la izquierdo de donde actualmente estamos
debe ser inferior a la valor que estamos actualmente.
Y todo a la derecha de donde estamos
debe ser mayor que el valor actualmente estamos viendo.
>> ¿Cuál es el pseudocódigo pasos para la búsqueda binaria?
Repetimos este proceso hasta que el matriz o, a medida que avancemos a través,
matrices sub, pequeñas piezas de la matriz original, es de tamaño 0.
Calcular el punto medio de la matriz sub actual.
>> Si el valor que estás buscando es en ese elemento de la matriz, para.
Lo encontraste.
Eso es genial.
De lo contrario, si el objetivo es menos de lo que está en el medio,
por lo que si el valor que estamos buscando para es menor que lo que vemos,
repetir este proceso otra vez, pero cambiar el punto final, en vez
de ser el original completar arsenal completo,
para ser justo a la izquierda de donde nos miramos.
>> Sabíamos que el medio era demasiado alto, o el objetivo era menos de la mitad,
y por lo que debe existir, si existe en absoluto en el array,
en algún lugar a la izquierda del punto medio.
Y así vamos a establecer la matriz ubicación justo a la izquierda
del punto medio como el nuevo punto final.
A la inversa, si el objetivo es mayor que lo que está en el medio,
hacemos lo mismo exacta proceso, pero en lugar de eso
cambiar el punto de inicio para ser justo a la derecha del punto medio
simplemente calculamos.
Y entonces, comenzamos el proceso de nuevo.
>> Vamos a visualizar esto, ¿de acuerdo?
Así que hay mucho que hacer y aquí, pero aquí es una matriz de los 15 elementos.
Y vamos a hacer el seguimiento de muchas más cosas en esta ocasión.
Así que en búsqueda lineal, estábamos simplemente preocuparse por un objetivo.
Pero esta vez queremos preocuparse por dónde estamos
empezando a mirar, donde nos detenemos en busca,
y lo que es el punto medio de la matriz actual.
Así que aquí vamos con búsqueda binaria.
Estamos bastante bueno para ir, ¿verdad?
Yo sólo voy a poner abajo a continuación aquí un conjunto de índices.
Esto es básicamente lo que el elemento de la matriz de que estamos hablando.
Con la búsqueda lineal, se cuidado, ya que nos
necesita saber cuántos elementos que estamos interactuando sobre,
pero en realidad no importa lo que elemento que actualmente estamos viendo.
En búsqueda binaria, lo que hacemos.
Y así, esos son sólo allí como una pequeña guía.
>> Así que podemos empezar, ¿no?
Bueno, no del todo.
Recuerde lo que dije sobre búsqueda binaria?
No podemos hacerlo en una array sin ordenar o de lo contrario,
no estamos garantizando que el ciertos elementos o valores no son
siendo accidentalmente desechado cuando sólo
decidir ignorar medio de la matriz.
>> Así que paso una con búsqueda binaria es que debe tener un conjunto ordenado.
Y usted puede utilizar cualquiera de la clasificación algoritmos que hemos hablado
para llegar a esa posición.
Así que ahora, estamos en una posición en la podemos realizar la búsqueda binaria.
>> Así que vamos a repetir el proceso paso a paso y tener
la pista de lo que está sucediendo a medida que avanzamos.
Así que lo primero que hay que hacer es calcular el punto medio de la matriz actual.
Bueno, vamos a decir que somos, en primer todo, buscando el valor 19.
Estamos tratando de encontrar el número 19.
El primer elemento de esta matriz se encuentra en el índice cero,
y el último elemento de esta matriz se encuentra en el índice 14.
Y así vamos a llamar a los de inicio y fin.
>> Así se calcula el punto medio por la adición de 0, más 14 dividido por 2;
punto medio bastante sencillo.
Y podemos decir que el punto medio es ahora 7.
Así que es 15 lo que estamos buscando?
No, no es.
Estamos buscando a 19.
Pero sabemos que 19 es mayor de lo que encontramos en el centro.
>> Así que lo que podemos hacer es cambiar el punto de inicio
para ser justo a la derecha de la punto medio, y repetir el proceso de nuevo.
Y cuando lo hacemos, decimos ahora la nuevo punto de partida es la ubicación matriz 8.
Lo que hemos hecho es efectiva todo lo ignorado a la izquierda de 15.
Hemos eliminado media del problema, y ​​ahora,
en lugar de tener que buscar más de 15 elementos en nuestra serie,
sólo tenemos que buscar más de 7.
Así que 8 es el nuevo punto de inicio.
14 sigue siendo el punto final.
>> Y ahora, vamos sobre esto de nuevo.
Calculamos el nuevo punto medio.
8 más 14 es 22, dividido por 2 es 11.
¿Es esto lo que estamos buscando?
No, no es.
Estamos buscando a un valor que es menos de lo que acabamos de encontrar.
Así que vamos a repetir el proceso de nuevo.
Vamos a cambiar el punto final a ser justo a la izquierda del punto medio.
Así que el nuevo punto final se convierte en 10.
Y ahora, esa es la única parte de la matriz que tenemos que clasificar.
Así que ahora hemos eliminado 12 de los 15 elementos.
Sabemos que si 19 existe en la matriz,
debe existir en algún lugar entre el elemento número 8 y el elemento número 10.
>> Así se calcula el nuevo punto medio nuevo.
8 más 10 es 18, dividido por 2 es 9.
Y en este caso, mira, la objetivo está en el centro.
Nos encontramos exactamente lo que estamos buscando.
Podemos parar.
Hemos completado con éxito una búsqueda binaria.
Correcto.
Así que sabemos que este algoritmo funciona si el objetivo es
en algún lugar dentro de la matriz.
¿Funciona esto algoritmo si el objetivo no está en la matriz?
Bueno, vamos a empezar que de nuevo, y esta vez,
vamos a ver para el elemento 16, que visualmente se puede ver
no existe en cualquier parte de la matriz.
>> El punto de inicio es de nuevo 0.
El punto final es de nuevo 14.
Esos son los índices de la primera y últimos elementos de la matriz completa.
Y vamos a ir a través del proceso que acabamos de fue a través de nuevo, tratando de encontrar 16,
a pesar de que visualmente, ya podemos dicen que no va a estar allí.
Sólo queremos asegurarnos de que este algoritmo será, de hecho, siguen trabajando de alguna manera
y no sólo nos dejan atrapado en un bucle infinito.
>> ¿Cuál es el primer paso?
Calcular el punto medio de la matriz actual.
¿Cuál es el punto medio de la matriz actual?
Bueno, es 7, ¿no?
14 plus 0 dividido por 2 es 7.
Es de 15 lo que estamos buscando?
No.
Está bastante cerca, pero estamos buscando por un valor un poco más grande que eso.
>> Así que sabemos que se va a estar en ninguna parte a la izquierda de 15.
El objetivo es mayor que lo que está en el punto medio.
Y así nos pusimos en el nuevo punto de partida para ser justo a la derecha del centro.
El punto medio es actualmente 7, por lo que digamos que el nuevo punto de inicio es 8.
Y lo que hemos efectivamente hecho nuevo es ignorado
toda la mitad izquierda de la matriz.
>> Ahora, repetimos el procesar una vez más.
Calcular el nuevo punto medio.
8 más 14 es 22, dividido por 2 es 11.
Es de 23 lo que estamos buscando?
Lamentablemente no.
Estamos buscando a un valor que es menor que 23.
Y así, en este caso, vamos para cambiar el punto final para ser justo
a la izquierda del punto medio actual.
El punto medio actual es 11, y así que vamos a establecer el nuevo punto final
para la próxima vez que vayamos a través de este proceso a 10.
>> Una vez más, pasamos por el proceso de nuevo.
Calcular el punto medio.
8 más 10 dividido por 2 es 9.
Es de 19 lo que estamos buscando?
Lamentablemente no.
Todavía estamos buscando un número menor que eso.
Así que vamos a cambiar el punto final de este tiempo para ser justo a la izquierda del punto medio.
El punto medio es actualmente 9, por lo que el punto final será de 8.
Y ahora, sólo estamos buscando en un solo elemento de la matriz.
>> ¿Cuál es el punto medio de este conjunto?
Bueno, empieza a las 8, que termina a las 8, el punto medio es 8.
¿Eso es lo que estamos buscando?
¿Estamos buscando 17?
No, estamos en busca de 16.
Así que si existe en la matriz, debe existir en alguna parte
a la izquierda de donde actualmente somos.
¿Entonces, que vamos a hacer?
Bueno, vamos a establecer el punto final a ser sólo a la izquierda del punto medio actual.
Así que vamos a cambiar el punto final a 7.
¿Ves lo que acaba de que pasó aquí, sin embargo?
Busque aquí ahora.
>> Start es ahora mayor que fin.
Efectivamente, los dos extremos de nuestra gama han cruzado,
y el punto de inicio es ahora después de que el punto final.
Bueno, eso no lo hace tiene sentido, ¿verdad?
Así que ahora, lo que podemos decir es que tener una matriz de tamaño sub 0.
Y una vez que estamos llegado a este punto, podemos ahora
garantizar que el elemento 16 no existe en la matriz,
debido a que el punto de partida y el punto final han cruzado.
Y por lo que no está ahí.
Ahora, observe que esto es ligeramente diferente a la del punto de inicio y fin
punto que se encuentre el mismo.
Si hubiéramos estado buscando para el 17, tendría
estado de la matriz, y el punto de inicio y el punto final de la última iteración
antes de que esos puntos cruzados, habríamos encontrado 17 allí.
Es sólo cuando cruzan que podemos garantiza que el elemento no
existir en la matriz.
>> Así que vamos a echar mucho menos pasos que la búsqueda lineal.
En el peor de los casos, tuvimos para dividir una lista de n elementos
en repetidas ocasiones por la mitad para encontrar el objetivo, ya sea porque el elemento de destino
será en algún lugar de la última división, o no existe en absoluto.
Así que en el peor de los casos, tenemos que dividir el array-- lo sabes?
Iniciar sesión de n veces; nosotros tener que cortar el problema
en medio de un cierto número de veces.
Ese número de veces que es log n.
>> ¿Cuál es el mejor de los casos?
Bueno, la primera vez que calcular el punto medio,
encontramos lo que estamos buscando.
En todo lo anterior ejemplos de búsqueda binaria
que acabamos ido, si tuviéramos estado buscando el elemento 15,
habríamos encontrado que inmediatamente.
Eso fue al principio.
Ese fue el punto medio de el primer intento de una división
de una división en la búsqueda binaria.
>> Y así, en el peor caso, la búsqueda binaria funciona
en el registro de n, que es sustancialmente mejor de búsqueda lineal, en el peor de los casos.
En el mejor caso, binario búsqueda se ejecuta en el omega de 1.
Así que la búsqueda binaria es mucho mejor que la búsqueda lineal,
pero usted tiene que tratar con el proceso de ordenar la matriz antes de poder
aprovechar el poder de búsqueda binaria.
>> Soy Doug Lloyd.
Esto es CS 50.