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