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