[Prehrávanie hudby] 

DOUG LLOYD: Dobre. Takže binárne vyhľadávanie je Algoritmus môžeme použiť nájsť prvok vnútri poľa. Na rozdiel od lineárnej hľadania, to vyžaduje Osobitná podmienka byť splnená vopred, ale je to oveľa účinnejšie, ak táto podmienka je, v skutočnosti, sa stretol. 

Takže to, čo je tu nápad? je to rozdeľ a panuj. Chceme znížiť veľkosť oblasť hľadania o polovicu každý čas s cieľom nájsť cieľové číslo. To je miesto, kde táto podmienka prichádza do hry, hoci. Môžeme využiť iba silu odstránenie polovice prvkov bez pri pohľade na je v prípade, že pole sa triedi. 

Ak je to úplný mix up, Nemôžeme len tak z ruky zbaviť polovica prvkov, pretože nevieme, čo sme vyradenie. Ale v prípade, že pole je radený, môžeme to urobiť, pretože sme viem, že všetko, čo k vľavo, kde sme v súčasnej dobe sú musí byť nižšia, než je Hodnota sme v súčasnosti. A všetko, čo k právo na to, kde sme musí byť väčšia ako hodnota sme v súčasnosti pri pohľade na. 

Takže čo je pseudokód kroky pre binárne vyhľadávanie? Tento postup opakujeme, kým nebude poľa alebo, ako budeme postupovať cez, podsouborům, menšie kusy pôvodnej poľa je veľkosti 0. Vypočítajte polovicu aktuálneho podsúboru. 

Ak je hodnota hľadáte, je v tomto prvku poľa, zastaviť. Našiel si to. To je skvelé. Inak, ak je cieľ menej než to, čo je v strede, takže ak hodnoty pozeráme pre nižšie, ako to, čo vidíme, tento proces opakovať, ale zmeniť koncový bod, namiesto toho z toho, že pôvodná dokončiť celou radou, byť len na ľavej strane kde sme sa len pozrel. 

Vedeli sme, že prostredný bola príliš vysoká, alebo cieľovú bol menší, ako v stredu, a tak, že musí existovať, ak je to vôbec existuje, v poli, niekde na ľavej strane stredového bodu. A tak sme si nastaviť pole poloha len na ľavej strane midpoint ako nového koncového bodu. Naopak, ak je cieľ väčšie, než to, čo je v strede, urobíme presne rovnaký proces, ale namiesto toho zmeniť počiatočný bod, aby len na pravej strane stredu sme jednoducho počítať. A potom sme sa znovu začať proces. 

Poďme si predstaviť to, OK? Takže je tu veľa deje, a na tú, ale tu je rad z 15 elementov. A budeme sa sledovanie o oveľa viac vecí tentoraz. Takže lineárne hľadanie, my sme boli len sa starať o cieľ. Ale tentoraz chceme starostlivosť o tom, kde sme začína vyzerať, kde zastavujeme hľadáte, a čo je na stred aktuálneho poľa. Tak ideme na to s binárne vyhľadávanie. Sme skoro dobré ísť, nie? Ja som jednoducho ísť dať dole nižšie tu množina indexov. To je v podstate to, čo práve element matice hovoríme. S lineárne hľadanie, my starostlivosti, pretože my Potrebujeme vedieť, koľko prvky, my iterácie cez, ale nemáme vlastne jedno, čo element sme v súčasnosti pri pohľade na. V binárne hľadanie, čo robíme. A tak to sú len tam ako malý sprievodca. 

Takže môžeme začať, nie? No, nie tak celkom. Spomeň si, čo som povedal, o binárneho vyhľadávania? Nemôžeme to urobiť na netriedený poľa alebo inak, nie sme zaručiť, že určité prvky alebo hodnoty nie sú náhodnému vypustí, keď sme práve rozhodnúť ignorovať polovicu poľa. 

Takže prvý krok s binárne vyhľadávanie je musíte mať zoradené poľa. A môžete použiť niektorý z triedenia algoritmy sme hovorili o aby ste sa dostali do tejto pozície. Takže teraz, sme v pozícii, kedy môžeme vykonávať binárne vyhľadávanie. 

Takže poďme proces opakovať krok za krokom a držať sledovať, čo sa deje, ako sme ísť. Takže najprv musíme urobiť, je výpočet stred z existujúceho poľa. No, budeme sa povedať, že sme v prvom rade všetci, hľadá pre hodnotu 19. Snažíme sa nájsť číslo 19. Prvým prvkom tejto poľa je umiestnený na indexe nula, a posledný prvok tejto poľa je umiestnený na indexe 14. A tak budeme hovoriť tie začiatok a koniec. 

Takže sme vypočítať stred strany pridaním 0 a navyše 14 deleno 2; celkom jednoduché stred. A môžeme povedať, že stred je teraz 7. Takže je 15 to, čo hľadáme? Nie to nie je. Hľadáme 19. Ale my vieme, že 19 je väčšia ako to, čo sme našli v stredu. 

Takže to, čo môžeme urobiť, je zmeniť počiatočný bod byť len napravo od stred, a znovu proces opakovať. A keď to urobíme, môžeme teraz povedať, Nový začiatok bod je umiestnenie poľa 8. To, čo sme skutočne urobili, je ignoroval všetko na ľavej strane 15. Odstránili sme polovicu problému, a teraz, namiesto toho, aby musel vyhľadávať viac ako 15 prvkov v našom poli, máme len hľadať cez 7. Takže 8 je nový východiskový bod. 14 je stále koncový bod. 

A teraz sme sa prejsť znovu. Počítame nový stred. 8 a 14, je 22, deleno 2, je 11. Je to to, čo hľadáme? Nie to nie je. Hľadáme hodnotu, ktorá je menej, než to, čo sme našli. Takže budeme opakovať opäť proces. Chystáme sa zmeniť koncový bod na byť len na ľavej strane stredu. Takže nový koncový bod sa stane 10. A teraz, to je len časť pole musíme usporiadať. Takže sme teraz odstránené 12 z 15 prvkov. Vieme, že v prípade 19 existuje v poli, to musí existovať niekde medzi prvkom číslo 8 a prvok číslo 10. 

Takže sme vypočítať nový stred znova. 8 a 10, je 18, deleno 2 je 9. A v tomto prípade, pozrite sa Cieľom je u stredu. Našli sme presne to, čo hľadáme. Môžeme sa zastaviť. Úspešne sme dokončili binárne vyhľadávanie. Dobre. Takže vieme, tento algoritmus funguje, ak je cieľ niekde vo vnútri matice. Má tento algoritmus pracovať, pokiaľ cieľ nie je v poli? No, začnime to znova, a tentoraz, pozrime sa aj na prvku 16, ktorý vizuálne vidíme neexistuje nikde v matici. 

Počiatočný bod je opäť 0. Konečný bod je opäť 14. Tí, ktorí sú indexy prvý a posledná prvky kompletného poľa. A pôjdeme cez proces sme práve Znovu prešiel a snažil sa nájsť 16, aj keď vizuálne, môžeme už povedať, že to nebude tam. Chceme len, aby sa uistil, tento algoritmus bude v skutočnosti, stále pracovať určitým spôsobom a nie len opustiť nás uviazol v nekonečnej slučke. 

Takže to, čo je prvý krok? Vypočítajte polovicu aktuálneho poľa. Čo je to stred súčasné pole? No, je to 7, nie? 14 a 0 deleno 2 je 7. Je 15 to, čo hľadáme? Nie. Je to celkom blízko, ale my hľadáme pre hodnotu o niečo väčší, než je. 

Takže vieme, že to bude byť nikde na ľavej strane 15. Cieľom je väčšia než čo je v strede. A tak sme si stanovili nový počiatočný bod na byť len vpravo od stredu. Stred je v súčasnej dobe 7, takže povedzme, že nový začiatok bod 8. A to, čo sme skutočne som opäť urobil je ignorovaný celá ľavá polovica matice. 

Teraz sme opakovať spracovať ešte raz. Vypočítajte nový stred. 8 a 14, je 22, deleno 2, je 11. Je 23 to, čo hľadáme? Bohužiaľ nie. Hľadáme hodnotu ktorá je menšia ako 23. A tak v tomto prípade, ideme zmeniť koncový bod byť spravodlivý naľavo od aktuálneho stredového bodu. Súčasný stred je 11, a takže budeme nastaviť nový koncový bod pre nabudúce ideme v tomto procese až 10. 

Opäť sme prejsť procesom znova. Vypočítajte stred. 8 a 10 deleno 2 je 9. Je 19 to, čo hľadáme? Bohužiaľ nie. Stále hľadáme číslo menšie, než je. Takže budeme meniť koncového bodu, tentoraz byť len na ľavej strane od stredu. Stred je v súčasnej dobe 9, takže koncový bod bude 8. A teraz, my sme len sa pozerá v jednom prvku poľa. 

Čo je stred tohto poľa? No, to začína v 8, je končí v 8, stred je 8. Je to to, čo hľadáme? Hľadáme 17? Nie, my hľadáme pre 16. Takže ak existuje v poli, že musí existovať niekde na ľavej strane, kde sú v súčasnej dobe. Tak čo budeme robiť? No, budeme nastavenie koncového bodu, aby len naľavo od aktuálneho stredového bodu. Takže budeme chcete zmeniť koncový bod až 7. Vidíte, čo sa práve tu stalo, aj keď? Pozrite sa tu. 

Štart je teraz väčšia ako koniec. Účinne, sú oba konce z našej ponuku prekročili, a počiatočný bod je Teraz po koncový bod. No, to nie je nejaký zmysel, že jo? Takže teraz, čo môžeme povedať, je, že sme majú čiastkové pole veľkosti 0. A akonáhle sme dostali do tento bod, môžeme teraz zaručiť, že prvok 16 neexistuje v matici, preto, že východiskový bod a koncový bod, ktoré prekročili. A tak je to tam nie je. Teraz, všimnite si, že je to trochu líši od počiatočného bodu a na konci bod je rovnaký. Keby sme hľadali pre 17, malo by to bol v poli, a počiatočný bod a koncový bod tej poslednej iterácie Než tie body prešiel, by sme našli 17 tam. Je to len vtedy, keď prekročí, že môžeme zaručiť, že element nie je existujú v matici. 

Takže poďme sa veľa menej Kroky než lineárne hľadania. V najhoršom prípade, mali sme rozdeliť sa ustanovuje zoznam n elementy opakovane na polovicu nájsť cieľ, a to buď preto, že cieľový prvok bude niekde v poslednej divízie, alebo neexistuje vôbec. Takže v najhoršom prípade, musíme rozišli sa array-- to viete? Logn časy; my musieť znížiť problém v polovici určitého počtu čias. To, koľkokrát je log n. 

Aký je najlepší scenár? No, prvýkrát, keď sme vypočítať stred, nájdeme to, čo hľadáme. Vo všetkých predchádzajúca príklady na binárne vyhľadávanie sme práve preberali, keby sme mali Hľadal prvku 15, by sme zistili, že okamžite. To bolo na samom začiatku. To bol stred Prvý pokus o rozdelení z divízie v binárnom vyhľadávania. 

A tak v najhoršom Prípad, binárne vyhľadávanie beží v log n, čo je podstatne lepší než lineárne vyhľadávanie, v najhoršom prípade. V najlepšom prípade, binárne Vyhľadávanie prebieha v omega 1. Takže binárne vyhľadávanie je veľa lepšie ako lineárne vyhľadávanie, ale budete musieť vysporiadať s procesom triedenie svoje polia skôr, než si môžete využiť silu binárneho vyhľadávania. 

Som Doug Lloyd. To je CS 50.