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.