>> ZAMYLA CHAN: První věc, kterou by mohl Oznámení o nálezu je, že jsme již
se kód napsaný pro nás.
To se nazývá rozdělení kódu.
Takže jsme nejen psát naše vlastní kód od nuly už.
Spíše jsme vyplňování dutin v nějakém pre-existujícího kódu.
>> Program find.c vyzve k zadání čísla vyplnit kupce sena, hledá
haystack pro uživatele předloženy jehly, a to tím, že volá druh a
vyhledávání, funkce definované v helpers.c.
Takže find.c je psáno již.
Vaším úkolem je napsat pomocníky.
>> Tak co budeme dělat?
Jsme se provádí dvě funkce.
Vyhledávání, která vrací hodnotu true, pokud hodnota se nachází v kupce sena, vrací
false pokud je tato hodnota není v kupce sena.
A pak jsme také implementaci druh, která setřídí pole s názvem hodnoty.
Takže pojďme řešit hledání.
>> Vyhledávání je v současné době prováděna jako lineární vyhledávání.
Ale můžete to udělat mnohem lépe, než to.
Lineární vyhledávání je realizován v O n čas, což je docela pomalý, i když to
Můžete hledat seznam, který mu dává.
Vaším úkolem je provádět binární vyhledávání, který má běžet čas O log n.
To je docela rychlý.
>> Ale je tu podmínka.
Binární vyhledávání lze vyhledávat pouze díky předem roztříděných seznamech.
Proč je to tak?
Dobře, pojďme se podívat na příklad.
Vzhledem k tomu, pole hodnot, kupka sena, budeme hledat
jehlu, a v tomto například číslo 3.
>> Tak, že binární vyhledávání funguje tak, že Porovnáme-li střední hodnotu
pole s jehlou, stejně jako jak jsme otevřeli telefonní seznam do středu
Stránka v týdnu 0.
Takže po porovnání střední hodnoty jehla, můžete odhodit buď
levá nebo pravá polovina pole utažením své meze.
V tomto případě, protože 3, naše jehla, je méně než 10, střední hodnota,
přímo vázané může snížit.
>> Ale snaží se, aby vaše hranice tak pevně, jak je to možné.
Je-li střední hodnota není jehla, pak víte, že nemusíte
zahrnout do vyhledávání.
Takže vaše právo vázáno může dotáhnout hledání hranice jen trošičku víc,
a tak dále a tak dále, dokud můžete najít jehlu.
>> Takže to, co dělá pseudo Kód vypadat?
No, když jsme pořád dívá skrz Seznam a ještě
prvky, které vypadají v, vezmeme střed seznamu, a porovnat, že
střední hodnota naší jehlou.
Pokud jsou stejné, pak to znamená, že máme našel jehlu, a můžeme
return true.
>> V opačném případě, je-li jehla je menší než střední hodnota, pak to znamená, že
může vyřadit pravou polovinu a jen hledat na levé straně pole.
V opačném případě budeme hledat na pravé straně pole.
A na závěr, pokud nemáte žádné zbývá hledat další prvky, ale můžete
nenašli jste jehlu ještě, pak vrátí false.
Vzhledem k tomu, jehla rozhodně není v kupce sena.
>> Teď, jedna užitečná věc o tomto pseudo kód v binárním vyhledávání je, že může
být vykládáno buď jako opakující se nebo rekurzivní implementace.
Tak to by bylo rekurzivní, pokud jste volali vyhledávací funkce v rámci hledání
fungovat na obou polovině pole.
Budeme pokrývat rekurze trochu Později v průběhu.
Ale vím, že to je možnost pokud byste chtěli vyzkoušet.