[MUSIC JOC] 

DOUG LLOYD: Bine. Deci căutare binară este un algoritm putem folosi pentru a găsi un element în interiorul unui tablou. Spre deosebire de căutare liniară, este nevoie de o condiție specială trebuie îndeplinite în prealabil, dar este atât de mult mai eficientă dacă această condiție este, de fapt, sa întâlnit. 

Deci, ce este ideea aici? e divide și cuceri. Vrem pentru a reduce dimensiunea de zona de căutare de jumătate de fiecare dată în scopul de a găsi un număr de țintă. Acest lucru este în cazul în care această condiție intră în joc, deși. Putem parghie numai puterea de eliminând jumătate din elementele fără măcar să se uite la le în cazul în care matrice este sortat. 

Daca este un amestec complet în sus, nu putem doar din mână aruncați jumătate din elementele, deoarece nu știm ce ne aruncarea. Dar dacă matrice este sortat, putem face asta, pentru că am Știu că totul la stânga de unde în prezent ne aflăm trebuie să fie mai mică decât Valoarea suntem în prezent la. Si totul la drept de unde suntem trebuie să fie mai mare decât valoarea ne caută în prezent. 

Deci, ce-i Pseudocodul pași pentru căutare binare? Repetăm ​​acest proces până când matrice sau, așa cum vom proceda prin, sub tablouri, bucăți mai mici de matrice originală, este de dimensiuni 0. Calculați punctul de mijloc Sub matrice curent. 

În cazul în care valoarea ce căutați este prin aceea că elementul de matrice, opri. Ai găsit. Grozav. În caz contrar, în cazul în care obiectivul este mai puțin de ceea ce este la mijloc, Deci, dacă valoarea pe care o căutați este mai mică decât ceea ce vedem, repeta acest proces din nou, dar schimba punctul de final, în loc de a fi original finaliza gamă completă, să fie doar la stânga de unde ne-am uitat. 

Stiam ca mijloc era prea mare, sau ținta a fost mai mică decât la mijloc, și așa trebuie să existe, în cazul în care există la toate în matrice, undeva în stânga punctul de mijloc. Și astfel vom stabili matrice locație doar la stânga din punctul de mijloc ca noul punct final. În schimb, în ​​cazul în care obiectivul este mai mare decât ceea ce este la mijloc, facem exact același proces, dar în schimb am a schimba punctul de pornire pentru a fi doar la dreptul de punctul de mijloc ne-am calculat. Și apoi, vom începe din nou procesul. 

Să vizualiza acest, bine? Deci, există o mulțime întâmplă și aici, dar aici este o serie de 15 elemente. Și am de gând să fie urmărirea de mult mai multe lucruri de data asta. Deci, în căutarea liniară, am fost doar pese o țintă. Dar de data aceasta vrem să pasă de unde suntem începe să arate, în cazul în care ne-am oprit în căutarea, și ceea ce este punctul de mijloc de matrice curent. Deci, aici vom merge cu căutare binară. Suntem destul de mult bun pentru a merge, nu? Mă duc pentru a pune în jos de mai jos aici un set de indici. Aceasta este de fapt doar ceea ce element de de matrice vorbim despre. Cu căutare liniară, am îngrijire, în măsura în care ne trebuie să știe cât de multe Elemente ne iterarea peste, dar nu-mi pasă de fapt ce Element ne caută în prezent. În căutare binară, facem. Și așa acestea sunt doar acolo ca un mic ghid. 

Astfel încât să putem începe, nu? Ei bine, nu chiar. Amintiți-vă ce am spus despre căutarea binar? Noi nu putem face acest lucru pe o matrice nesortate sau altceva, nu suntem garantarea faptului că anumite elemente sau valori nu sunt fiind accidental aruncată când ne-am decide să ignore jumătate din matrice. 

Deci, pas cu unul de căutare binară este că trebuie să aibă o gamă sortate. Și vă puteți folosi oricare din sortarea algoritmi am vorbit despre pentru a ajunge la această poziție. Deci, acum, suntem într-o poziție în care putem efectua căutare binară. 

Deci, haideți să repetați procesul de pas cu pas și să păstreze cont de ceea ce se intampla ca mergem. Deci, primul trebuie să facem este calcula punctul de mijloc al matrice curent. Ei bine, vom spune că suntem, în primul toate, în căutarea pentru valoarea 19. Încercăm să găsim numărul 19. Primul element al acestui matrice este situat la index de zero, și ultimul element al acestei matrice este situat la index 14. Și astfel vom suna cele de început și sfârșit. 

Așa că am calcula punctul de mijloc de adăugarea 0 plus 14 împărțit la 2; punctul de mijloc destul de simplă. Și putem spune că punctul de mijloc este acum 7. Deci, este de 15 ceea ce căutăm? Nu, nu este. Căutăm 19. Dar noi știm că 19 este mai mare decât ceea ce am găsit la mijloc. 

Deci, ce putem face este schimba punctul de start să fie doar pentru a dreapta punctul de mijloc, și repetați din nou procesul. Și când facem asta, spunem acum nou punct de plecare este matrice locație 8. Ce am făcut în mod eficient este totul ignorat în partea stângă a 15. Am eliminat jumătate a problemei, iar acum, în loc de a avea pentru a căuta peste 15 elemente în oferta noastră, avem doar pentru a căuta peste 7. Deci 8 este noul punct de pornire. 14 este în continuare punctul final. 

Și acum, ne-am trece peste asta din nou. Se calculează noul mijloc. 8 plus 14 este 22, împărțit la 2 este 11. Este aceasta ceea ce căutăm? Nu, nu este. Căutăm o valoare care este mai puțin de ceea ce am găsit. Așa că am de gând să repet procesul din nou. Vom schimba punctul final la fie doar la stânga de punctul de mijloc. Deci noul punct final devine 10. Și acum, asta e doar o parte a matrice avem pentru a sorta prin. Deci, am eliminat acum 12 din cele 15 elemente. Știm că, dacă 19 există în matrice, se trebuie să existe undeva între elementul numărul 8 și numărul 10 element de. 

Deci, vom calcula din nou noul mijloc. 8 plus 10 este 18, împărțit la 2 este 9. Și în acest caz, uite, țintă este la mijloc. Am gasit exact ceea ce căutăm. Ne putem opri. Am finalizat cu succes o căutare binară. In regula. Deci, noi știm acest algoritm funcționează în cazul în care obiectivul este undeva în interiorul matrice. Face acest lucru în cazul în care algoritm obiectivul nu este in matrice? Ei bine, hai să înceapă din nou, și de această dată, să ne uităm pentru elementul 16, care vizual putem vedea nu există nicăieri în matrice. 

Punctul de pornire este din nou 0. Punctul final este din nou 14. Acestea sunt indicii ale primului și ultimele elemente ale tabloului complet. Și vom merge prin procesul de ne-am a trecut prin din nou, încercând să găsească 16, chiar dacă vizual, putem deja spune că nu va fi acolo. Vrem doar să vă asigurați acest algoritm va, de fapt, încă de lucru într-un fel și nu doar ne lase blocat într-o buclă infinită. 

Deci, ce este pas prima? Calculați punctul de mijloc de matrice curent. Care este punctul de mijloc de matrice curent? Ei bine, e 7, nu? 14 plus 0 împărțit la 2 este 7. Este de 15 ceea ce căutăm? Nu. E destul de aproape, dar căutăm pentru o valoare puțin mai mare decât cea. 

Deci, știm că o să fi nicăieri la stânga de 15. Ținta este mai mare de ceea ce este în punctul de mijloc. Și astfel ne-am stabilit noul punct de pornire pentru fie doar la dreptul de mijloc. Punctul de mijloc este în prezent 7, așa să spunem noi punctul de pornire este de 8. Și ceea ce am în mod eficient făcut din nou este ignorată întregul jumătatea stângă a șirului. 

Acum, ne-am repeta procesa încă o dată. Calculați noul mijloc. 8 plus 14 este 22, împărțit la 2 este 11. Este de 23 ceea ce căutăm? Din păcate nu. Căutăm o valoare care este mai mică de 23. Și astfel, în acest caz, vom pentru a schimba punctul final să fie doar la stânga punctului de mijloc curent. Actualul mijloc este de 11, și asa ca vom stabili noul punct final pentru data viitoare vom merge prin acest proces la 10. 

Din nou, vom merge prin procesul din nou. Calculați punctul de mijloc. 8 plus 10 împărțit la 2 este 9. Este ceea ce 19 căutăm? Din păcate nu. Suntem încă în căutarea pentru un număr mai mic decât cel. Deci, vom schimba punctul final de această dată să fie doar la stânga de punctul de mijloc. Punctul de mijloc este în prezent 9, astfel încât punctul final va fi de 8. Și acum, suntem în căutarea doar la un singur element de matrice. 

Care este punctul de mijloc al acestui tablou? Ei bine, aceasta începe la 8, ea se termină la 8, punctul de mijloc este de 8. Este că ceea ce căutăm? Căutăm 17? Nu, suntem în căutarea pentru 16. Deci, dacă există în matrice, trebuie să existe undeva în partea stângă a în cazul în care în prezent ne aflăm. Deci, ce ne facem? Ei bine, vom stabili punctul final să fie doar la stânga punctului de mijloc curent. Deci, vom schimba punctul final la 7. Vedeți ce doar sa întâmplat aici, deși? Uită-te aici, acum. 

Start este acum mai mare decât la sfârșitul. Efectiv, cele două capete de oferta noastră au trecut, și punctul de pornire este acum, după punctul final. Ei bine, asta nu face nici un sens, nu? Deci, acum, ceea ce putem spune este că au o gamă de dimensiuni sub 0. Și odată ce suntem ajuns la acest punct, putem acum garantează că elementul 16 nu există în matrice, deoarece punctul de pornire și punctul final au trecut. Și așa că nu e acolo. Acum, observați că acest lucru este ușor diferit de punctul de început și de sfârșit punctul fiind același. Dacă am fi fost în căutarea pentru 17, aceasta ar trebui fost în matrice, și punctul de start și punctul final al acestei ultime repetare înainte de aceste puncte trecut, am fi găsit acolo 17. Este doar atunci când acestea trec pe care putem garanta că elementul nu există în matrice. 

Deci, haideți să aruncăm o mulțime mai pași decât căutarea liniară. În cel mai rău caz, am avut să împartă o listă de n elemente în mod repetat, în jumătate pentru a găsi țintă, fie din cauză că elementul țintă va fi undeva în ultimul divizare, sau nu există deloc. Deci, în cel mai rău caz, trebuie să ne împărțit de array-- știi? Log de n ori; noi trebuie să taie problema în jumătate un anumit număr de ori. Acest număr de ori este log n. 

Care este cel mai bun caz? Ei bine, prima dată WE calcula punctul de mijloc, găsim ceea ce căutăm. În toate precedent exemple de căutare binară tocmai am trecut peste, dacă am avea căutat pentru elementul 15, am fi descoperit că imediat. Asta a fost la început. Acesta a fost punctul de mijloc al prima încercare de o fracțiune de de o divizie în căutare binară. 

Și astfel în cel mai rău caz, căutare binară ruleaza în jurnalul n, care este substanțial mai bine decât căutarea liniară, în cel mai rău caz. În cel mai bun caz, binar căutare ruleaza in omega de 1. Deci binar de căutare este mult mai bine decât căutarea liniară, dar trebuie să se ocupe de procesul de sortare matrice dumneavoastră înainte de a putea pârghie de putere de căutare binară. 

Sunt Doug Lloyd. Aceasta este CS 50.