ROB BOWDEN: Ahoj, já jsem Rob. Jak používáme binární hledání? Pojďme zjistit. Takže, na vědomí, že toto hledání jedeme provádět rekurzivně. Dalo by se také provádět binární vyhledávání iterativně, takže pokud to uděláte, To je naprosto v pořádku. 

Nyní poprvé, pojďme si vzpomenout, co Parametry pro hledání mají být. Zde vidíme int hodnotu, která je má být hodnota uživatel vyhledávání. Vidíme pole int hodnoty, které je pole, ve kterém jsme hledá hodnotu. A vidíme, int n, což je délka našeho pole. 

Nyní, první věc, kterou jako první. Zkontrolujte jsme se zjistit, jestli n se rovná 0, se takovém případě se vrátíme false. To jen říkám, máme-li prázdná pole, hodnota je jednoznačně není prázdné pole, takže se můžeme vrátit false. 

Teď jsme vlastně chcete udělat binární Vyhledávání součástí binárního vyhledávání. Takže, chceme najít střed prvek tohoto pole. Zde říkáme, střední rovná n dělí o 2, protože prostřední element je bude délka naše pole děleno 2. Teď budeme kontrolovat, zda prostřední element rovná hodnotě stojíme vyhledávání. Takže pokud hodnoty střední rovná hodnotě, jsme může vrátit true, protože jsme zjistili, že hodnota v našem poli. 

Ale v případě, že to není pravda, teď musíme udělat rekurzivní krok binární vyhledávání. Musíme hledat buď vlevo na pole nebo na uprostřed pole. Tak tady, můžeme říci, že hodnoty na střed je menší než hodnota, která znamená, že hodnota byl větší než uprostřed z pole. Takže hodnota musí být vpravo prvek, který jsme právě podíval na. 

Tak tady, jedeme na hledat rekurzivně. A my se podíváme na to, co jsme kolem k tomu v druhém. Ale budeme hledat na vpravo od středního prvku. A v druhém případě, to znamená, že hodnota byla nižší než uprostřed pole, a tak jdeme hledat na levé straně. Nyní, vlevo bude trochu jednodušší podívat se na. Takže, zde vidíme, že jsme rekurzivně volání, kde první hledání argument je opět hodnota díváme přes. Druhý argument se bude pole, které jsme hledali přes. A poslední prvek je nyní uprostřed. Nezapomeňte, poslední parametr je naše int n, tak to je délka našeho pole. 

V rekurzivní volání pro hledání, jsme Nyní říká, že délka pole je střední. Takže, pokud naše pole bylo o velikosti 20 a my hledal na index 10, protože střed je 20 děleno 2, to znamená, že jsme kolem 10 jako nový délka našeho pole. Pamatujte si, že když máte pole délky 10, to znamená, že platí prvky jsou v indexech 0 až 9. Tak to je přesně to, co chceme specifikovat náš aktualizovaný pole - levé pole od středu prvku. 

Takže, hledá na pravé straně je trochu složitější. Nyní poprvé, pojďme zvážit délku z pole na pravé straně prostřední prvek. Takže, pokud naše pole bylo velikosti n, pak Nová řada bude mít velikost n mínus střední minus 1. Takže, pojďme si n mínus uprostřed. 

Opět platí, že v případě, že pole byla velikosti 20 a dělíme o 2 dostat střed, takže uprostřed je 10, pak n minus střední bude nám 10, takže 10 prvky napravo od středu. Ale máme také tuto minus 1, protože nechceme, aby patří střed sám. Tak n minus střední minus 1 nám dává celkový počet prvků na pravé straně středního indexu v poli. 

A teď si uvědomte, že střední parametr je hodnota pole. Takže tady máme kolem aktualizovat hodnoty pole. Tyto hodnoty, plus střední plus 1 je vlastně říká rekurzivně volat vyhledávání, předávání do nového pole, kde že nová řada začíná ve středu a jeden z našich původních hodnot pole. 

Alternativní syntaxe, že nyní jste začal vidět odkazy, je ampersand hodnoty střední plus 1. Takže, chytit adresu středu a jeden prvek z hodnot. 

Nyní, pokud jste nebyli pohodlný změnou pole, jako to, že jste by také zavedli tento používání rekurzivní funkce pomocník, kde že pomocná funkce se více argumentů. Takže místo toho, aby jen hodnoty, pole, a velikost pole, pomocná funkce může trvat více argumenty, včetně nižším indexem , který by se staral o v poli a horní index, který vám záleží o pole. 

A tak sledování i nižší index a horní index, vy ne je třeba vždy upravit původní hodnoty pole. Můžete jen pokračovat použít hodnoty pole. Ale tady si všimněte, nepotřebujeme pomocníka fungovat tak dlouho, jak budeme ochoten změnit původní hodnoty pole. Jsme ochotni předat aktualizované hodnoty. 

Nyní, nemůžeme binární hledání přes pole, které je netříděný. Takže, pojďme si to vyřeší. Nyní si všimněte, že druh je kolem dvou parametry int hodnoty, která je pole, které jsme třídění a int n, což je délka pole, které jsme třídění. Takže, tady chceme realizovat třídění algoritmus , který je o n na druhou. Ty by mohly zvolit bubble sort, výběr druh, nebo vložení třídění, nebo nějaký jiný druh nemáme vidět ve své třídě. Ale tady, jedeme na použijte pro výběr druhu. 

Takže, budeme iterovat přes celé pole. No, tady vidíme, že jsme iterace od 0 do n minus 1. Proč ne celou cestu až na n? No, pokud jsme již řazeno první n mínus 1 elementy, pak Posledním prvkem toho, co již musí být na správném místě, tak v průběhu řazení Celé pole. 

A teď si uvědomte, jak výběr druh práce. Chystáme se jet přes celé pole hledá pro minimální hodnotu v pole a hůl, která na začátku. Pak jsme jít přes celé pole opět hledá sekundu nejmenší prvek, a hůl, která ve druhé pozici v pole, a tak dále. Tak, to je to, co to dělá. 

Zde vidíme, že jsme nastavení aktuálního minimální hodnota indexu i-tého. Takže v první iteraci, jedeme vzít v úvahu minimální hodnota bude Začátek našeho pole. Pak budeme iterovat přes Zbytek pole, kontrola na zjistit, jestli existuje nějaké prvky menší než jedno, že jsme v současné době s ohledem na minimum. 

Tak tady, hodnoty j plus jedna - to je méně než to, co jsme v současné době s ohledem na minimum. Pak budeme aktualizovat, co si myslíme, že je minimální, aby index j plus 1. Takže, to, že přes celé pole, a poté, co to pro smyčky, minimální by měla být minimální prvek z pozice i-tého v poli. 

Jakmile budeme mít, můžeme vyměnit Minimální hodnota do pozice i-tého v poli. Takže je to jen standardní swap. Uložíme do dočasné hodnoty - hodnota i-tý v poli - dát do hodnoty i-tého v poli Minimální hodnota, která tam patří, a poté uložit zpět do kterých aktuální minimální hodnota býval i-tá hodnota v poli, tak že jsme neměli ztratit. 

Tak, že pokračuje další iteraci. Budeme začít hledat pro druhé minimální hodnota a vložit, že do druhé místo. Na třetí iteraci, se podíváme na Třetí minimální hodnota a vložka , že do třetí polohy, a proto dokud máme seřazené pole. Jmenuji se Rob, a to byl výběr sort.