[MUSIC PŘEHRÁVÁNÍ] 

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é provádí jakousi 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í hledání, ale můžete dělat mnohem lepší než to. Lineární vyhledávání je realizován v O n času, což je poměrně pomalé. I když to může vyhledávat jakýkoli seznam uveden na něj. 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? 

No podívejme se na příklad. Vzhledem k tomu, pole hodnot, kupka sena, budeme hledat jehlu. A v tomto případě, číslo tři. 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 nulové. 

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 tři, naše jehla, je menší 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 máš pravdu vázán lze utá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 se v pseudokódu vypadat? No, když jsme stále hledají přes Seznam a ještě prvky Podívejte se do bereme uprostřed seznamu, a porovnat, že střední hodnoty naše jehla. 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 se return false, protože jehla rozhodně není v kupce sena. 

Nyní užitečná věc o tomto pseudokódu v binární hledání je, že může být interpretovat 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 rekurzi trochu později Samozřejmě, ale vím, že to je volba, pokud byste chtěli vyzkoušet. 

Nyní se pojďme podívat na druhu. Seřadit bere pole a číslo n, což je velikost pole. Teď tam jsou různé typy druhů, a můžete se podívat na některé šortky pro ukázky a vysvětlení. Návratový typ pro naše Funkce třídění je neplatné. Takže to znamená, že nejdeme vrátit jakoukoli nabídku od druhu. Jsme skutečně změní velmi pole, který byl předán do nás. 

A to je možné, protože pole jsou prošel odkazem v C. Nyní se budeme viz více o tom později, ale Podstatný rozdíl mezi procházení něco jako celé číslo a procházení v poli, je, že když předat celé číslo, C je jen tak vytvořit kopii tohoto integer a projít že do funkce. Původní proměnné se nezmění Jakmile je funkce dokončena. S pole, na druhé straně, to je nebudu dělat kopii, a budete skutečně úpravách Velmi pole sám. 

Takže jeden druh druhu je výběr třídění. Výběr třídit funguje tak, že počínaje začátek, a pak iterovat nad a najít nejmenší prvek. A pak vyměnit, že nejmenší prvek s prvním. A pak se přesunout na druhý prvek , Naleznete další nejmenší prvek, a pak vyměnit, že se Druhým prvkem v poli, neboť První element je již řazeno. A tak se pak budete pokračovat za každou prvkem při určování nejmenší hodnota a vymění ji. 

Vždyť já se rovná 0, úplně první prvek na n minus 1, budete porovnávat každá další hodnota po tom a najít index minimální hodnoty. Jakmile zjistíte, index minimální hodnoty, můžete prohodit, že hodnota pole minimální a řada I. 

Dalším typem druhu, který můžete realizovat je bublina třídění. Takže bubble sort přes seznamu iterace porovnání sousedních prvků a vyměňovat prvky, které jsou ve špatném pořadí. A to způsobem, největší prvek bude bubliny až do konce. A seznam je seřazen jednou více prvky byly vyměněny. 

Takže to jsou dva příklady druhu algoritmy, které můžete realizovat pro Program find. Jakmile dokončíte třídit, a vy jste provedeno hledání, budete hotovi. Jmenuji se Zamyla, a to je CS50. 

[MUSIC PŘEHRÁVÁNÍ]