ROB BOWDEN: Ahoj, ja som Rob. Ako používame binárne hľadanie? Poďme zistiť. Takže, na vedomie, že toto hľadanie ideme vykonávať rekurzívne. Dalo by sa tiež vykonávať binárne vyhľadávanie iteratívne, takže ak to urobíte, To je úplne v poriadku. 

Teraz prvýkrát, poďme si spomenúť, čo Parametre pre hľadanie majú byť. Tu vidíme int hodnotu, ktorá je má byť hodnota užívateľ vyhľadávanie. Vidíme pole int hodnoty, ktoré je pole, v ktorom sme hľadá hodnotu. A vidíme, int n, čo je dĺžka nášho poľa. 

Teraz, prvá vec, ktorú ako prvý. Skontrolujte sme sa zistiť, či n sa rovná 0, sa takom prípade sa vrátime false. To len hovorím, ak máme prázdna pole, hodnota je jednoznačne nie je prázdne pole, takže sa môžeme vrátiť false. 

Teraz sme vlastne chcete urobiť binárne Vyhľadávanie súčasťou binárneho vyhľadávania. Takže, chceme nájsť stred prvok tohto poľa. Tu hovoríme, stredné rovná n delí o 2, pretože prostredný element je bude dĺžka naše pole delené 2. Teraz budeme kontrolovať, či prostredný element rovná hodnote stojíme vyhľadávanie. Takže ak hodnoty strednej rovná hodnote, sme môže vrátiť true, pretože sme zistili, že hodnota v našom poli. 

Ale v prípade, že to nie je pravda, teraz musíme urobiť rekurzívne krok binárne vyhľadávanie. Musíme hľadať buď vľavo na pole alebo na uprostred poľa. Tak tu, môžeme povedať, že hodnoty na stred je menšia ako hodnota, ktorá znamená, že hodnota bol väčší než uprostred z poľa. Takže hodnota musí byť vpravo prvok, ktorý sme práve pozrel na. 

Tak tu, ideme na hľadať rekurzívne. A my sa pozrieme na to, čo sme okolo k tomu v druhom. Ale budeme hľadať na vpravo od stredného prvku. A v druhom prípade, to znamená, že hodnota bola nižšia ako uprostred pole, a tak ideme hľadať na ľavej strane. Teraz, vľavo bude trochu jednoduchšie pozrieť sa na. Takže, tu vidíme, že sme rekurzívne volanie, kde prvý hľadanie argument je opäť hodnota pozeráme cez. Druhý argument sa bude pole, ktoré sme hľadali cez. A posledný prvok je teraz uprostred. Nezabudnite, posledný parameter je naša int n, tak to je dĺžka nášho poľa. 

V rekurzívne volanie pre hľadanie, sme Teraz hovorí, že dĺžka pole je stredná. Takže, ak naše pole bolo o veľkosti 20 a my hľadal na index 10, pretože stred je 20 deleno 2, to znamená, že sme okolo 10 ako nový dĺžka nášho poľa. Pamätajte si, že keď máte pole dĺžky 10, to znamená, že platí prvky sú v indexoch 0 až 9. Tak to je presne to, čo chceme špecifikovať náš aktualizovaný poľa - ľavé poľa od stredu prvku. 

Takže, hľadá na pravej strane je trochu zložitejšie. Teraz po prvýkrát, poďme zvážiť dĺžku z poľa na pravej strane prostredný prvok. Takže, ak naše pole bolo veľkosti n, potom Nová rada bude mať veľkosť n mínus stredná mínus 1. Takže, poďme si n mínus uprostred. 

Opäť platí, že v prípade, že pole bola veľkosti 20 a delíme o 2 dostať stred, takže uprostred je 10, potom n mínus strednej bude nám 10, takže 10 prvky napravo od stredu. Ale máme tiež túto mínus 1, pretože nechceme, aby patrí stred sám. Tak n mínus strednej mínus 1 nám dáva celkový počet prvkov na pravej strane stredného indexu v poli. 

A teraz si uvedomte, že stredná parameter je hodnota poľa. Takže tu máme okolo aktualizovať hodnoty poľa. Tieto hodnoty, plus stredná plus 1 je vlastne hovorí rekurzívne volať vyhľadávanie, odovzdávanie do nového poľa, kde že nová rada začína v stredu a jeden z našich pôvodných hodnôt poľa. 

Alternatívne syntaxe, že teraz ste začal vidieť odkazy, je ampersand hodnoty strednej plus 1. Takže, chytiť adresu stredu a jeden prvok z hodnôt. 

Teraz, ak ste neboli pohodlný zmenou poľa, ako to, že ste by tiež zaviedli tento používania rekurzívne funkcie pomocník, kde že pomocná funkcia sa viac argumentov. Takže namiesto toho, aby len hodnoty, pole, a veľkosť poľa, pomocná funkcia môže trvať viac argumenty, vrátane nižším indexom , Ktorý by sa staral o v poli a horný index, ktorý vám záleží o pole. 

A tak sledovanie aj nižšia index a horný index, vy nie je potrebné vždy upraviť pôvodnej hodnoty poľa. Môžete len pokračovať použiť hodnoty poľa. Ale tu si všimnite, nepotrebujeme pomocníka fungovať tak dlho, ako budeme ochotný zmeniť pôvodné hodnoty poľa. Sme ochotní odovzdať aktualizovanej hodnoty. 

Teraz, nemôžeme binárne hľadanie cez pole, ktoré je netriedený. Takže, poďme si to vyrieši. Teraz si všimnite, že druh je okolo dvoch parametre int hodnoty, ktorá je pole, ktoré sme triedenie a int n, čo je dĺžka poľa, ktoré sme triedenie. Takže, tu chceme realizovať triedenie algoritmus , Ktorý je o n na druhú. Tie by mohli zvoliť bubble sort, výber druh, alebo vloženie triedenia, alebo nejaký iný druh nemáme vidieť vo svojej triede. Ale tu, ideme na použite pre výber druhu. 

Takže, budeme iterovat cez celé pole. No, tu vidíme, že sme iterácie od 0 do n mínus 1. Prečo nie celú cestu až na n? No, ak sme už je zoradený prvý n mínus 1 elementy, potom Posledným prvkom toho, čo už musí byť na správnom mieste, tak v priebehu radenia Celé pole. 

A teraz si uvedomte, ako výber druh práce. Chystáme sa ísť cez celé pole hľadá pre minimálnu hodnotu v pole a palicu, ktorá na začiatku. Potom sme ísť cez celé pole opäť hľadá sekundu najmenší prvok, a palica, ktorá v druhej pozícii v pole, a tak ďalej. Tak, to je to, čo to robí. 

Tu vidíme, že sme nastavenie aktuálneho minimálna hodnota indexu i-teho. Takže v prvej iterácii, ideme vziať do úvahy minimálna hodnota bude Začiatok nášho poľa. Potom budeme iterovat cez Zvyšok poľa, kontrola na zistiť, či existuje nejaké prvkami menej ako jedno, že sme v súčasnej dobe s ohľadom na minimum. 

Tak tu, hodnoty j plus jedna - to je menej než to, čo sme v súčasnej dobe s ohľadom na minimum. Potom budeme aktualizovať, čo si myslíme, že je minimálna, aby index j plus 1. Takže, to, že cez celé pole, a potom, čo to pre slučky, minimálna by mala byť minimálna prvok z pozície i-teho v poli. 

Akonáhle budeme mať, môžeme vymeniť Minimálna hodnota do pozície i-teho v poli. Takže je to len štandardné swap. Uložíme do dočasnej hodnoty - hodnota i-ty v poli - dať do hodnoty i-tého v poli Minimálna hodnota, ktorá tam patrí, a potom uložiť späť do ktorých aktuálna minimálna hodnota býval i-tá hodnota v poli, tak že sme nemali stratiť. 

Tak, že pokračuje ďalšie iterácii. Budeme začať hľadať pre druhé minimálna hodnota a vložiť, že do druhé miesto. Na tretej iterácii, sa pozrieme na Tretie minimálna hodnota a vložka , Že do tretej polohy, a preto kým máme zoradené poľa. Volám sa Rob, a to bol výber sort.