>> ZAMYLA CHAN: Prvá vec, ktorú by mohol Oznámenie o náleze je, že sme už
sa kód napísaný pre nás.
To sa nazýva rozdelenie kódu.
Takže sme nielen písať naše vlastné kód od nuly už.
Skôr sme vyplňovanie dutín v nejakom pre-existujúceho kódu.
>> Program find.c vyzve na zadanie čísla vyplniť kope sena, hľadá
stoh sena pre užívateľa predložené ihly, a to tým, že volá druh a
vyhľadávanie, funkcie definované v helpers.c.
Takže find.c je napísané už.
Vašou úlohou je napísať pomocníkmi.
>> Tak čo budeme robiť?
Sme sa vykonáva dve funkcie.
Vyhľadávanie, ktorá vracia hodnotu true, ak hodnota sa nachádza v kope sena, vracia
false ak je táto hodnota nie je v kope sena.
A potom sme tiež implementáciu druh, ktorá zotriedi pole s názvom hodnoty.
Takže poďme riešiť hľadanie.
>> Vyhľadávanie je v súčasnosti vykonávajú ako lineárny vyhľadávanie.
Ale môžete to urobiť oveľa lepšie, než to.
Lineárne vyhľadávanie je realizovaný v O n čas, čo je celkom pomalý, aj keď to
Môžete hľadať zoznam, ktorý mu dáva.
Vašou úlohou je vykonávať binárne vyhľadávanie, ktorý má bežať čas O log n
To je celkom rýchly.
>> Ale je tu podmienka.
Binárne vyhľadávanie je možné vyhľadávať iba vďaka vopred roztriedených zoznamoch.
Prečo je to tak?
Dobre, poďme sa pozrieť na príklad.
Vzhľadom k tomu, pole hodnôt, kôpka sena, budeme hľadať
ihlu, a v tomto napríklad číslo 3.
>> Tak, že binárne vyhľadávanie funguje tak, že Ak porovnáme strednú hodnotu
pole s ihlou, rovnako ako ako sme otvorili telefónny zoznam do stredu
Stránka v týždni 0.
Takže po porovnaní strednej hodnoty ihla, môžete odhodiť buď
ľavá alebo pravá polovica poľa utiahnutím svoje medze.
V tomto prípade, pretože 3, naša ihla, je menej ako 10, stredná hodnota,
priamo viazané môže znížiť.
>> Ale snaží sa, aby vaše hranice tak pevne, ako je to možné.
Je-li stredná hodnota nie je ihla, potom viete, že nemusíte
zahrnúť do vyhľadávania.
Takže vaše právo viazané môže dotiahnuť hľadanie hranice len trošičku viac,
a tak ďalej a tak ďalej, až kým môžete nájsť ihlu.
>> Takže to, čo robí pseudo Kód vyzerať?
No, keď sme stále pozerá cez Zoznam a ešte
prvky, ktoré vyzerajú v, vezmeme stred zoznamu, a porovnať, že
stredná hodnota našej ihlou.
Ak sú rovnaké, potom to znamená, že máme našiel ihlu, a môžeme
return true.
>> V opačnom prípade, ak je ihla je menšia ako stredná hodnota, potom to znamená, že
môže vyradiť pravú polovicu a len hľadať na ľavej strane poľa.
V opačnom prípade budeme hľadať na pravej strane poľa.
A na záver, ak nemáte žiadne zostáva hľadať ďalšie prvky, ale môžete
nenašli ste ihlu ešte, potom vráti false.
Vzhľadom k tomu, ihla rozhodne nie je v kope sena.
>> Teraz, jedna užitočná vec o tomto pseudo kód v binárnom vyhľadávania je, že môže
byť vykladané buď ako opakujúce sa alebo rekurzívne implementácia.
Tak to by bolo rekurzívne, ak ste volali vyhľadávacie funkcie v rámci hľadania
fungovať na oboch polovici poľa.
Budeme pokrývať rekurzia trochu Neskôr v priebehu.
Ale viem, že to je možnosť ak by ste chceli vyskúšať.