>> 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.