>> [REPRODUCCIÓ DE MÚSICA]
>> DOUG LLOYD: D'acord.
Així que la recerca binària és un algoritme podem utilitzar
per trobar un element dins d'una matriu.
A diferència de recerca lineal, es requereix un condició especial es va reunir amb anterioritat,
però és molt més eficient si aquesta condició és, de fet, s'ha reunit.
>> Quina és la idea aquí?
és divideix i venceràs.
Volem reduir la mida de l'àrea de recerca a la meitat cada vegada
amb la finalitat de trobar un número de destinació.
Aquí és on aquesta condició entra en joc, però.
Només podem aprofitar el poder de eliminant mitjà dels elements
sense tan sols mirar si la matriu s'ordenen.
>> Si es tracta d'una barreja completa fins, No podem sortir de la mà
descartar mitjà dels elements, perquè no sabem el que estem rebutjant.
Però si la matriu està ordenada, podem fer això, perquè nosaltres
saber que tot a la esquerre d'on actualment estem
ha de ser inferior a la valor que estem actualment.
I tot a la dreta d'on estem
ha de ser més gran que el valor actualment estem veient.
>> Quin és el pseudocodi passos per a la recerca binària?
Repetim aquest procés fins que el matriu o, a mesura que avancem a través,
matrius sub, petites peces de la matriu original, és de mida 0.
Calcular el punt mitjà de la matriu sub actual.
>> Si el valor que estàs buscant és en aquest element de la matriu, per.
Vostè va trobar.
Això és genial.
Altrament, si l'objectiu és menys del que està al mig,
pel que si el valor que estem buscant per és menor que el que veiem,
repetir aquest procés una altra vegada, però canviar el punt final, en comptes
de ser l'original completar arsenal complet,
per ser just a l'esquerra d'on ens mirem.
>> Sabíem que el mitjà era massa alt, o l'objectiu era menys de la meitat,
i pel que ha d'existir, si existeix en absolut en l'array,
en algun lloc a l'esquerra del punt mitjà.
I així anem a establir la matriu ubicació just a l'esquerra
del punt mig com el nou punt final.
Al revés, si l'objectiu és més gran que el que està en el mig,
fem el mateix exacta procés, però en lloc d'això
canviar el punt d'inici per a ser just a la dreta del punt mig
simplement calculem.
I llavors, vam començar el procés de nou.
>> Anem a visualitzar això, d'acord?
Així que hi ha molt a fer i aquí, però aquí és una matriu dels 15 elements.
I farem el seguiment de moltes més coses en aquesta ocasió.
Així que en recerca lineal, estàvem simplement preocupar-se per un objectiu.
Però aquesta vegada volem preocupar-se per on som
començant a mirar, on ens aturem a la recerca,
i el que és el punt mig de la matriu actual.
Així que aquí anem amb recerca binària.
Estem bastant bo per anar, oi?
Jo només vaig a posar baix a continuació aquí un conjunt d'índexs.
Això és bàsicament el que l'element de la matriu que estem parlant.
Amb la recerca lineal, es cura, ja que ens
necessita saber quants elements que estem interactuant sobre,
però en realitat no importa el que element que actualment estem veient.
En recerca binària, el que fem.
I així, aquests són només allà com una petita guia.
>> Així que podem començar, no?
Bé, no del tot.
Recordeu el que vaig dir sobre recerca binària?
No podem fer-ho en una array sense ordenar o en cas contrari,
no estem garantint que el certs elements o valors no són
sent accidentalment rebutjat quan només
decidir ignorar mitjà de la matriu.
>> Així que passo una amb recerca binària és que ha de tenir un conjunt ordenat.
I vostè pot utilitzar qualsevol de la classificació algoritmes que hem parlat
per arribar a aquesta posició.
Així que ara, estem en una posició en la podem fer la cerca binària.
>> Així que repetirem el procés pas a pas i tenir
la pista del que està succeint a mesura que avancem.
Així que el primer que cal fer és calcular el punt mig de la matriu actual.
Bé, anem a dir que som, en primer tot, buscant el valor 19.
Estem tractant de trobar el número 19.
El primer element d'aquesta matriu es troba en l'índex zero,
i l'últim element d'aquesta matriu es troba en l'índex 14.
I així anem a cridar els d'inici i fi.
>> Així es calcula el punt mitjà per l'addició de 0, més 14 dividit per 2;
punt mitjà bastant senzill.
I podem dir que el punt mitjà és ara 7.
Així que és 15 el que estem buscant?
No, no ho és.
Estem buscant a 19.
Però sabem que 19 és més gran del que trobem al centre.
>> Així que el que podem fer és canviar el punt d'inici
per ser just a la dreta de la punt mig, i repetir el procés de nou.
I quan ho fem, diem ara la nou punt de partida és la ubicació matriu agost.
El que hem fet és efectiva tot el ignorat a l'esquerra 15.
Hem eliminat mitjana del problema, i ara,
en lloc d'haver de buscar més de 15 elements en la nostra sèrie,
només hem de buscar més de 7.
Així que 8 és el nou punt d'inici.
14 segueix sent el punt final.
>> I ara, anem sobre això de nou.
Calculem el nou punt mitjà.
8 més 14 és 22, dividit per 2 és 11.
És això el que estem buscant?
No, no ho és.
Estem buscant a un valor que és menys del que acabem de trobar.
Així que repetirem el procés de nou.
Anem a canviar el punt final a ser just a l'esquerra del punt mitjà.
Així que el nou punt final es converteix en 10.
I ara, aquesta és l'única part de la matriu que hem de classificar.
Així que ara hem eliminat 12 dels 15 elements.
Sabem que si 19 existeix en la matriu,
ha d'existir en algun lloc entre l'element número 8 i l'element número 10.
>> Així es calcula el nou punt mitjà nou.
8 més 10 és 18, dividit per 2 és 9.
I en aquest cas, mira, la objectiu està al centre.
Ens trobem exactament el que estem buscant.
Podem parar.
Hem completat amb èxit una recerca binària.
Tot bé.
Així que sabem que aquest algoritme funciona si l'objectiu és
en algun lloc dins de la matriu.
Funciona això algoritme si l'objectiu no està en la matriu?
Bé, anem a començar que de nou, i aquesta vegada,
anem a veure per l'element 16, que visualment es pot veure
no existeix en qualsevol part de la matriu.
>> El punt d'inici és de nou 0.
El punt final és de nou 14.
Aquests són els índexs de la primera i últims elements de la matriu completa.
I anem a anar a través del procés que acabem de va ser a través de nou, tractant de trobar 16,
tot i que visualment, ja podem diuen que no va a ser-hi.
Només volem assegurar-nos que aquest algorisme serà, de fet, segueixen treballant d'alguna manera
i no només ens deixen atrapat en un bucle infinit.
>> Quin és el primer pas?
Calcular el punt mitjà de la matriu actual.
Quin és el punt mig de la matriu actual?
Bé, és 7, no?
14 plus 0 dividit per 2 és 7.
És de 15 que estem buscant?
No.
Està bastant a prop, però estem buscant per un valor una mica més gran que això.
>> Així que sabem que es va a estar enlloc a l'esquerra 15.
L'objectiu és més gran que el que està en el punt mig.
I així ens vam posar en el nou punt de partida per a ser just a la dreta del centre.
El punt mitjà és actualment 7, de manera que diguem que el nou punt d'inici és 8.
I el que hem efectivament fet nou és ignorat
tota la meitat esquerra de la matriu.
>> Ara, repetim el processar una vegada més.
Calcular el nou punt mitjà.
8 més 14 és 22, dividit per 2 és 11.
És de 23 que estem buscant?
Lamentablement no.
Estem buscant a un valor que és menor que 23.
I així, en aquest cas, anem per canviar el punt final per ser just
a l'esquerra del punt mitjà actual.
El punt mitjà actual és 11, i així que anem a establir el nou punt final
per a la propera vegada que anem a través d'aquest procés a 10.
>> Un cop més, vam passar pel procés de nou.
Calcular el punt mitjà.
8 més de 10 dividit per 2 és 9.
És de 19 que estem buscant?
Lamentablement no.
Encara estem buscant un nombre menor que això.
Així que anem a canviar el punt final d'aquest temps per ser just a l'esquerra del punt mitjà.
El punt mitjà és actualment 9, de manera que el punt final serà de 8.
I ara, només estem buscant en un sol element de la matriu.
>> Quin és el punt mig d'aquest conjunt?
Bé, comença a les 8, que acaba a les 8, el punt mig és 8.
¿Això és el que estem buscant?
Estem buscant 17?
No, estem a la recerca de 16.
Així que si existeix en la matriu, ha d'existir en algun lloc
a l'esquerra d'on actualment som.
Llavors, què farem?
Bé, anem a establir el punt final a ser només a l'esquerra del punt mitjà actual.
Així que anem a canviar el punt final a 7.
Veus el que acaba de que va passar aquí, però?
Busqui aquí ara.
>> Start és ara més gran que fi.
Efectivament, els dos extrems de la nostra gamma han creuat,
i el punt d'inici és ara després que el punt final.
Bé, això no ho fa té sentit, oi?
Així que ara, el que podem dir és que tenir una matriu de mida sub 0.
I una vegada que estem arribat a aquest punt, podem ara
garantir que l'element 16 no existeix en la matriu,
pel fet que el punt de partida i el punt final han creuat.
I pel que no hi és.
Ara, observi que això és lleugerament diferent a la del punt d'inici i fi
punt que es trobi el mateix.
Si haguéssim estat buscant pel 17, tindria
estat de la matriu, i el punt d'inici i el punt final de l'última iteració
abans que aquests punts creuats, hauríem trobat 17 allà.
És només quan creuen que podem garanteix que l'element no
existir en la matriu.
>> Així que anem a fer molt menys passos que la recerca lineal.
En el pitjor dels casos, vam tenir per dividir una llista de n elements
en repetides ocasions per la meitat per trobar l'objectiu, ja sigui perquè l'element de destinació
serà en algun lloc de l'última divisió, o no existeix en absolut.
Així que en el pitjor dels casos, hem de dividir el array-- ho saps?
Iniciar sessió de n vegades; nosaltres haver de tallar el problema
enmig d'un cert nombre de vegades.
Aquest nombre de vegades que és log n.
>> Quin és el millor dels casos?
Bé, la primera vegada que calcular el punt mitjà,
trobem el que estem buscant.
En tot l'anterior exemples de recerca binària
que acabem anat, si tinguéssim estat buscant l'element 15,
hauríem trobat que immediatament.
Això va ser al principi.
Aquest va ser el punt mig de el primer intent d'una divisió
d'una divisió en la recerca binària.
>> I així, en el pitjor cas, la recerca binària funciona
en el registre de n, que és substancialment millor de recerca lineal, en el pitjor dels casos.
En el millor cas, binari recerca s'executa en l'omega d'1.
Així que la recerca binària és molt millor que la recerca lineal,
però vostè ha de tractar amb el procés de ordenar la matriu abans de poder
aprofitar el poder de cerca binària.
>> Sóc Doug Lloyd.
Això és CS 50.