[Música tocando] 

Doug LLOYD: Todo ben. Entón, é unha procura binaria algoritmo podemos utilizar para atopar un elemento dentro dunha matriz. A diferenza de busca lineal, require un condición especial responderse previamente, pero é moito máis eficiente que esta condición é, de feito, cumpridos. 

Entón, cal é a idea aquí? é dividir e conquistar. Queremos reducir o tamaño da a área de investigación para a metade de cada vez a fin de atopar un número de destino. Este é o lugar onde esta condición entra en xogo, con todo. Nós só pode alavancar o poder de eliminando a metade dos elementos sen sequera ollar para Los a matriz está clasificada. 

Se é unha mestura complétase, Non podemos simplemente fóra de man descartar a metade dos elementos, porque Non sabemos o que estamos descartando. Pero, se a matriz é clasificada, podemos facer iso, porque nós sei que todo o deixou de onde estamos actualmente debe ser inferior a valor que estamos actualmente. E todo para o seguro de onde estamos debe ser maior que o valor actualmente estamos mirando. 

Entón, cal é o pseudocódigo pasos para a investigación binaria? Nós repetimos este proceso ata que o matriz ou, a medida que proseguimos a través, matrices sub, pequenos anacos de a matriz orixinal, é de tamaño 0. Calcular o punto medio do sub matriz actual. 

Se o valor que está a buscar en que elemento da matriz, pare. Atopou. Isto é óptimo. Se non, se o destino menos que o que está no medio, por iso, se o valor que estamos a buscar para é menor que o que vemos, cabo este proceso de novo, pero cambiar o punto final, en vez de ser o orixinal completar gama completa, para ser só para a dereita de onde nós só mirou. 

Sabiamos que o medio era moi alto, ou o destino era menos que a media, e por iso debe existir, se existe de todo na matriz, un lugar para a esquerda do punto medio. E por iso imos definir a matriz localización, só á esquerda do punto medio como o punto final. Por outra banda, se o destino maior que o que está no medio, facemos exactamente o mesmo proceso, pero no seu lugar, cambiar o punto de inicio para ser só para a dereita do punto medio nós só calculado. E entón, comezamos o proceso de novo. 

Imos ver iso, OK? Polo tanto, hai moita cousa a suceder e aquí, pero aquí está unha matriz de 15 elementos. E nós estamos indo a ser manter o control de moito máis cousas neste momento. Así, en busca lineal, fomos só preocuparse un obxectivo. Pero esta vez queremos se preocupan onde estamos empezando a mirar, onde que estamos parando mirando, e cal é o punto medio da matriz actual. Entón, imos con busca binaria. Estamos practicamente listo para ir, non? Eu só vou poñer para abaixo debaixo aquí un conxunto de índices. Esta é basicamente só o elemento da matriz que estamos falando. Coa busca lineal, nós coidado, na medida en que Debe saber cantas elementos que estamos iterando, pero nós realmente non ligo para o que elemento que está mirando. En busca binaria, o que facemos. E así estes son só alí como un pequeno guía. 

Así, podemos comezar, non? Ben, non exactamente. Lembre que eu dixen preto de busca binaria? Non podemos facelo nun matriz sen clasificar ou máis, que non son garantir que o certos elementos ou valores non son sendo accidentalmente descartados cando nós só decidir ignorar a metade da matriz. 

Entón, paso un investigación binaria é que ten que ter unha matriz clasificada. E pode utilizar calquera dos selección algoritmos que falamos para chegar a esa posición. Entón, agora, estamos nunha posición onde podemos realizar a procura binaria. 

Entón, imos repetir o proceso paso a paso e manter ao tanto do que está a suceder a medida que avanzamos. Así, o primeiro que temos que facer é calcular o punto medio da gama actual. Ben, imos dicir que estamos, en primeiro lugar todo, ollando para o valor 19. Estamos intentando atopar o número 19. O primeiro elemento do presente matriz está situada no índice cero, eo último elemento da presente matriz está situada no índice 14. E por iso imos chamar os inicio e fin. 

Entón nós calculamos o punto medio por adición de 0, máis 14 dividido por 2; punto medio moi sinxelo. E podemos dicir que o punto medio é agora 7. Así, é de 15 o que estamos a buscar? Non, non é. Estamos á procura de 19. Pero sabemos que 19 é maior que o que nós no medio. 

Entón, o que podemos facer é cambiar o punto de inicio ser só dereito da punto medio, e repita o proceso de novo. E cando facemos iso, nós agora din que a novo punto de partida é a localización matriz 8. O que fixemos é eficaz ignorado todo á esquerda de 15. Nós eliminamos metade do problema, e agora, en vez de ter que buscar máis de 15 elementos na nosa matriz, só temos que buscar máis de 7. Entón 8 é o punto de partida. 14 aínda é o punto final. 

E agora, nós imos sobre iso de novo. Nós calculamos o punto medio. 8 máis 14 é 22, dividido por 2 é de 11. Isto é o que estamos a buscar? Non, non é. Estamos á procura de un valor que é menos que o que acaba de atopar. Entón, nós estamos indo a repetir o proceso de novo. Nós imos cambiar o punto final para ser só para a dereita do punto medio. Así, o punto final pasa a ser 10. E agora, que é a única parte do a matriz temos que clasificar completamente. Polo tanto, temos agora eliminado 12 dos 15 elementos. Sabemos que, se 19 existe na matriz, el debe existir nalgún lugar entre o elemento número 8 e elemento de número 10. 

Entón nós calculamos o punto central de novo. 8 engade 10 é 18, dividido por 2 é 9. E neste caso, mira, o obxectivo está no medio. Atopamos o que estamos buscando. Podemos parar. Nós Feito con éxito unha investigación binaria. Todo ben. Entón, nós sabemos que este algoritmo funciona se o destino é algures no interior da matriz. Será que este algoritmo de traballo se o obxectivo non está na matriz? Ben, imos volvelo de novo, e esta vez, imos ollar para o elemento 16, que visualmente vemos non existe en calquera lugar na matriz. 

O punto de partida é de novo 0. O punto final é novo 14. Estes son os índices da primeira e últimos elementos da matriz completa. E nós imos pasar polo proceso que acabamos pasou por unha vez, intentando atopar 16, aínda visualmente, xa podemos dicir que non vai estar alí. Nós só queremos que seguro este algoritmo será, de feito, seguen a traballar de algunha maneira e non só deixar-nos preso nun loop infinito. 

Entón, cal é o primeiro paso? Calcular o punto medio da matriz actual. Cal é o punto medio da matriz actual? Ben, é 7, non? 14 máis 0 dividido por 2 a 7. 15 é o que estamos a buscar? Non. É moi preto, pero nós estamos mirando para un valor algo maior que iso. 

Entón, nós sabemos que vai estar en ningunha parte da esquerda de 15. O obxectivo é maior que o que está no punto medio. E, así, establecer o punto de partida para ser só dereito de medio. O punto medio é actualmente 7, así digamos que o punto de partida é 8. E o que temos efectivamente feito de novo é ignorado toda a metade esquerda da matriz. 

Agora, repetimos o procesar unha vez máis. Calcular o punto medio. 8 máis 14 é 22, dividido por 2 é de 11. 23 é o que estamos a buscar? Desgraciadamente non. Estamos á procura de un valor que é inferior a 23. E así, neste caso, imos para cambiar o punto final para ser só á esquerda do punto medio do curso. O punto medio de corrente é de 11, e así que imos definir o punto final para a próxima vez que imos por este proceso a 10. 

De novo, nós pasar polo proceso de novo. Calcular o punto medio. 8 máis 10 dividido por 2 é 9. 19 é o que estamos a buscar? Desgraciadamente non. Aínda estamos a buscar un número menor que iso. Entón, nós imos cambiar o punto final a estas alturas ser só para a dereita do punto medio. O punto medio é actualmente 9, de xeito que o punto final será 8. E agora, estamos só buscando a matriz dun único elemento. 

Cal é o punto medio desta matriz? Ben, comeza ás 8, el remata en 8, o punto medio é de 8. É iso o que estamos a buscar? Estamos á procura de 17? Non, nós estamos mirando para 16. Polo tanto, se está na matriz, debe existir algún lugar á esquerda de onde estamos hoxe. Entón, o que imos facer? Ben, imos definir o punto final para ser só á esquerda do punto medio do curso. Entón, nós imos cambiar o punto final a 7. Ve o que pasou aquí, aínda? Olle aquí enriba agora. 

Iniciar agora é maior que final. Efectivamente, as dúas extremidades da nosa matriz cruzar, e é o punto de partida Agora, tras o punto final. Ben, iso non fai fai calquera sentido, non? Entón, agora, o que podemos dicir é que ten un sub matriz de tamaño 0. E xa que estamos chegara a Neste punto, podemos agora garantir que elemento 16 non existe na matriz, porque o punto de partida e punto final cruzaron. E así el non está alí. Agora, teña en conta que este é lixeiramente diferente do que o punto de inicio e final apuntar sendo o mesmo. Se tivésemos sido buscando para 17, tería foi na matriz, eo punto de inicio e punto final desta última iteración antes deses puntos cruzados, que encontraría 17 alí. É só cando cruzan o que pudermos garantir que o elemento non fai existen na matriz. 

Entón, imos ter unha chea menos etapas que busca lineal. No peor caso, tivemos para dividir unha lista de n elementos repetidamente ao medio para atopar o destino, ben porque o elemento obxecto vai estar nalgún lugar no último división, ou que non existe en todo. Entón, no peor dos casos, hai que dividir os array-- sabe? Rexistro de n veces; nós Ten que cortar o problema en metade dun certo número de veces. Ese número de veces que se log n. 

Cal é o mellor escenario? Ben, a primeira vez que calcular o punto medio, atopamos o que estamos buscando. En toda a anterior exemplos de busca binaria nós só ir máis, se tivésemos está a buscar o elemento 15, que encontraría inmediatamente. Isto foi no inicio. Ese foi o punto medio de o primeiro intento dunha escisión dunha división na procura binaria. 

E así, no peor caso, busca binaria execútase no rexistro n, o cal é substancialmente mellor que busca lineal, no peor dos casos. No mellor dos casos, binario busca execútase en omega de 1. Así, busca binaria é moi mellor que a procura lineal, pero tes que xestionar o proceso de clasificando súa matriz antes de se alavancar o poder de busca binaria. 

Eu son Doug Lloyd. Este é CS 50.