[Přehrávání hudby] 

DOUG LLOYD: Dobře. Takže binární vyhledávání je Algoritmus můžeme použít najít prvek uvnitř pole. Na rozdíl od lineární hledání, to vyžaduje Zvláštní podmínka být splněna předem, ale je to mnohem účinnější, pokud tato podmínka je, ve skutečnosti, se setkal. 

Takže to, co je tady nápad? je to rozděl a panuj. Chceme snížit velikost oblast hledání o polovinu každý čas s cílem nalézt cílové číslo. To je místo, kde tato podmínka přichází do hry, ačkoli. Můžeme využít pouze sílu odstranění poloviny prvků aniž by při pohledu na je v případě, že pole se třídí. 

Pokud je to úplný mix up, Nemůžeme jen tak z ruky zbavit polovina prvků, protože nevíme, co jsme vyřazení. Ale v případě, že pole je řazen, můžeme to udělat, protože jsme vím, že všechno, co k vlevo, kde jsme v současné době jsou musí být nižší, než je Hodnota jsme v současné době. A vše, co k právo na to, kde jsme musí být větší než hodnota jsme v současné době při pohledu na. 

Takže co je pseudokód kroky pro binární vyhledávání? Tento postup opakujeme, dokud nebude pole nebo, jak budeme postupovat přes, podsouborům, menší kusy původní pole je velikosti 0. Vypočtěte polovinu aktuálního podsouboru. 

Pokud je hodnota hledáte, je v tomto prvku pole, zastavit. Našel jsi to. To je skvělé. Jinak, pokud je cíl méně než to, co je ve středu, takže pokud hodnoty díváme pro nižší, než to, co vidíme, tento proces opakovat, ale změnit koncový bod, místo toho z toho, že původní dokončit celou řadou, být jen na levé straně kde jsme se jen podíval. 

Věděli jsme, že prostřední byla příliš vysoká, nebo cílovou byl menší, než ve středu, a tak, že musí existovat, je-li to vůbec existuje, v poli, někde na levé straně středového bodu. A tak jsme si nastavit pole poloha jen na levé straně midpoint jako nového koncového bodu. Naopak, pokud je cíl větší, než to, co je ve středu, uděláme přesně stejný proces, ale místo toho změnit počáteční bod, aby jen na pravé straně středu jsme prostě počítat. A pak jsme se znovu začít proces. 

Pojďme si představit to, OK? Takže je tu spousta děje, a na tu, ale tady je řada z 15 elementů. A budeme se sledování o mnohem víc věcí tentokrát. Takže lineární hledání, my jsme byli jen se starat o cíl. Ale tentokrát chceme péče o tom, kde jsme začíná vypadat, kde zastavujeme hledáte, a co je na střed aktuálního pole. Tak jdeme na to s binární vyhledávání. Jsme skoro dobré jít, ne? Já jsem prostě jít dát dolů níže zde množina indexů. To je v podstatě to, co právě element matice mluvíme. S lineární hledání, my péče, neboť my Potřebujeme vědět, kolik prvky, my iterace přes, ale nemáme vlastně jedno, co element jsme v současné době při pohledu na. V binární hledání, co děláme. A tak to jsou jen tam jako malý průvodce. 

Takže můžeme začít, ne? No, ne tak docela. Vzpomeň si, co jsem řekl, o binárního vyhledávání? Nemůžeme to udělat na netříděný pole nebo jinak, nejsme zaručit, že určité prvky nebo hodnoty nejsou náhodnému vypustí, když jsme právě rozhodnout ignorovat polovinu pole. 

Takže první krok s binární vyhledávání je musíte mít seřazené pole. A můžete použít některý z třídění algoritmy jsme mluvili o abyste se dostali do této pozice. Takže teď, jsme v pozici, kdy můžeme provádět binární vyhledávání. 

Takže pojďme proces opakovat krok za krokem a držet sledovat, co se děje, jak jsme jít. Takže nejprve musíme udělat, je výpočet střed ze stávajícího pole. No, budeme se říct, že jsme v první řadě všichni, hledá pro hodnotu 19. Snažíme se najít číslo 19. Prvním prvkem této pole je umístěn na indexu nula, a poslední prvek této pole je umístěn na indexu 14. A tak budeme říkat ty začátek a konec. 

Takže jsme vypočítat střed strany přidáním 0 a navíc 14 děleno 2; docela jednoduché střed. A můžeme říci, že střed je nyní 7. Takže je 15 to, co hledáme? Ne, to není. Hledáme 19. Ale my víme, že 19 je větší než to, co jsme našli ve středu. 

Takže to, co můžeme udělat, je změnit počáteční bod být jen napravo od střed, a znovu proces opakovat. A když to uděláme, můžeme nyní říci, Nový začátek bod je umístění pole 8. To, co jsme skutečně udělali, je ignoroval vše na levé straně 15. Odstranili jsme polovinu problému, a teď, místo toho, aby musel vyhledávat více než 15 prvků v našem poli, máme jen hledat přes 7. Takže 8 je nový výchozí bod. 14 je stále koncový bod. 

A teď jsme se projít znovu. Počítáme nový střed. 8 a 14, je 22, děleno 2, je 11. Je to to, co hledáme? Ne, to není. Hledáme hodnotu, která je méně, než to, co jsme našli. Takže budeme opakovat opět proces. Chystáme se změnit koncový bod na být jen na levé straně středu. Takže nový koncový bod se stane 10. A teď, to je jen část pole musíme uspořádat. Takže jsme nyní odstraněny 12 z 15 prvků. Víme, že v případě 19 existuje v poli, to musí existovat někde mezi prvkem číslo 8 a prvek číslo 10. 

Takže jsme vypočítat nový střed znovu. 8 a 10, je 18, děleno 2 je 9. A v tomto případě, podívejte se Cílem je u středu. Našli jsme přesně to, co hledáme. Můžeme se zastavit. Úspěšně jsme dokončili binární vyhledávání. Dobře. Takže víme, tento algoritmus funguje, pokud je cíl někde uvnitř matice. Má tento algoritmus pracovat, pokud cíl není v poli? No, začněme to znovu, a tentokrát, podívejme se i na prvku 16, který vizuálně vidíme neexistuje nikde v matici. 

Počáteční bod je opět 0. Konečný bod je opět 14. Ti, kteří jsou indexy první a poslední prvky kompletního pole. A půjdeme přes proces jsme právě Znovu prošel a snažil se najít 16, i když vizuálně, můžeme již říct, že to nebude tam. Chceme jen, aby se ujistil, tento algoritmus bude ve skutečnosti, stále pracovat určitým způsobem a ne jen opustit nás uvízl v nekonečné smyčce. 

Takže to, co je první krok? Vypočtěte polovinu aktuálního pole. Co je to střed současné pole? No, je to 7, ne? 14 a 0 děleno 2 je 7. Je 15 to, co hledáme? Ne. Je to docela blízko, ale my hledáme pro hodnotu o něco větší, než je. 

Takže víme, že to bude být nikde na levé straně 15. Cílem je větší než co je v středu. A tak jsme si stanovili nový počáteční bod na být jen vpravo od středu. Střed je v současné době 7, takže řekněme, že nový začátek bod 8. A to, co jsme skutečně jsem opět udělal je ignorován celá levá polovina matice. 

Nyní jsme opakovat zpracovat ještě jednou. Vypočítejte nový střed. 8 a 14, je 22, děleno 2, je 11. Je 23 to, co hledáme? Bohužel ne. Hledáme hodnotu která je menší než 23. A tak v tomto případě, jdeme změnit koncový bod být spravedlivý nalevo od aktuálního středového bodu. Současný střed je 11, a takže budeme nastavit nový koncový bod pro příště jdeme v tomto procesu až 10. 

Opět jsme projít procesem znovu. Vypočítejte střed. 8 a 10 děleno 2 je 9. Je 19 to, co hledáme? Bohužel ne. Stále hledáme číslo menší, než je. Takže budeme měnit koncového bodu, tentokrát být jen na levé straně od středu. Střed je v současné době 9, takže koncový bod bude 8. A teď, my jsme jen se dívá v jednom prvku pole. 

Co je střed tohoto pole? No, to začíná v 8, je končí v 8, střed je 8. Je to to, co hledáme? Hledáme 17? Ne, my hledáme pro 16. Takže pokud existuje v poli, že musí existovat někde na levé straně, kde jsou v současné době. Tak co budeme dělat? No, budeme nastavení koncového bodu, aby jen nalevo od aktuálního středového bodu. Takže budeme-li změnit koncový bod až 7. Vidíte, co se právě tady stalo, i když? Podívejte se tady. 

Start je nyní větší než konec. Účinně, jsou oba konce z naší nabídku překročily, a počáteční bod je Nyní po koncový bod. No, to není nějaký smysl, že jo? Takže teď, co můžeme říci, je, že jsme mají dílčí pole velikosti 0. A jakmile jsme dostali do tento bod, můžeme nyní zaručit, že prvek 16 neexistuje v matici, proto, že výchozí bod a koncový bod, které překročily. A tak je to tam není. Teď, všimněte si, že je to poněkud liší od počátečního bodu a na konci bod je stejný. Kdybychom hledali pro 17, mělo by to byl v poli, a počáteční bod a koncový bod té poslední iterace Než ty body přešel, bychom našli 17 tam. Je to pouze tehdy, když překročí, že můžeme zaručit, že element není existují v matici. 

Takže pojďme se hodně méně Kroky než lineární hledání. V nejhorším případě, měli jsme rozdělit se stanoví seznam n elementy opakovaně na polovinu najít cíl, a to buď proto, že cílový prvek bude někde v poslední divize, nebo neexistuje vůbec. Takže v nejhorším případě, musíme rozešli se array-- to víte? Log n časy; my muset snížit problém v polovině určitého počtu dob. To, kolikrát je log n. 

Jaký je nejlepší scénář? No, poprvé, kdy jsme vypočítat střed, najdeme to, co hledáme. Ve všech předchozí příklady na binární vyhledávání jsme právě probírali, kdybychom měli Hledal prvku 15, bychom zjistili, že okamžitě. To bylo na samém počátku. To byl střed První pokus o rozdělení z divize v binárním vyhledávání. 

A tak v nejhorším Případ, binární vyhledávání běží v log n, což je podstatně lepší než lineární vyhledávání, v nejhorším případě. V nejlepším případě, binární Vyhledávání probíhá v omega 1. Takže binární vyhledávání je hodně lepší než lineární vyhledávání, ale budete muset vypořádat s procesem třídění své pole dřív, než si můžete využít sílu binárního vyhledávání. 

Jsem Doug Lloyd. To je CS 50.