[MUSIC PLAYBACK] 

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ž vykonáva akúsi ktorá zotriedi pole s názvom hodnoty. 

Takže poďme riešiť hľadanie. Vyhľadávanie je v súčasnej dobe vykonáva ako lineárne hľadanie, ale môžete robiť oveľa lepšie ako to. Lineárne vyhľadávanie je realizovaný v O n času, čo je pomerne pomalé. Aj keď to môže vyhľadávať akýkoľvek zoznam uvedený na neho. 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? 

No pozrime sa na príklad. Vzhľadom k tomu, pole hodnôt, kôpka sena, budeme hľadať ihlu. A v tomto prípade, číslo tri. 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 nulové. 

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 tri, naše ihla, je menšia 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 máš pravdu viazaný možno utiahnuť 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 sa v pseudokódu vyzerať? No, keď sme stále hľadajú cez Zoznam a ešte prvky Pozrite sa do berieme uprostred zoznamu, a porovnať, že stredné hodnoty naše ihla. 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 sa return false, pretože ihla rozhodne nie je v kope sena. 

Teraz užitočná vec o tomto pseudokódu v binárnej hľadanie je, že môže byť interpretovať 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ť rekurziu trochu neskôr Samozrejme, ale viem, že to je voľba, ak by ste chceli vyskúšať. 

Teraz sa poďme pozrieť na druhu. Zoradiť berie pole a číslo n, čo je veľkosť poľa. Teraz tam sú rôzne typy druhov, a môžete sa pozrieť na niektoré šortky pre ukážky a vysvetlenie. Návratový typ pre naše Funkcia triedenia je neplatné. Takže to znamená, že nejdeme vrátiť akúkoľvek ponuku od druhu. Sme skutočne zmení veľmi poľa, ktorý bol odovzdaný do nás. 

A to je možné, pretože pole sú prešiel odkazom v C. Teraz sa budeme pozri viac o tom neskôr, ale Podstatný rozdiel medzi prechádzanie niečo ako celé číslo a prechádzanie v poli, je, že keď odovzdať celé číslo, C je len tak vytvoriť kópiu tohto integer a prejsť že do funkcie. Pôvodné premenné sa nezmenia Akonáhle je funkcia dokončená. S pole, na druhej strane, to je nebudem robiť kópiu, a budete skutočne úpravách Veľmi pole sám. 

Takže jeden druh druhu je výber triedenia. Výber triediť funguje tak, že počnúc začiatok, a potom iterovat nad a nájsť najmenší prvok. A potom vymeniť, že najmenší prvok s prvým. A potom sa presunúť na druhý prvok , Nájdete ďalšie najmenší prvok, a potom vymeniť, že sa Druhým prvkom v poli, pretože Prvý element už je zoradený. A tak sa potom budete pokračovať za každú prvkom pri určovaní najmenšej hodnota a vymení ju. 

Veď ja sa rovná 0, úplne prvý prvok na n mínus 1, budete porovnávať každá ďalšia hodnota po tom a nájsť index minimálnej hodnoty. Akonáhle zistíte, index minimálne hodnoty, môžete prehodiť, že hodnota poľa minimálna a rad I. 

Ďalším typom druhu, ktorý môžete realizovať je bublina triedenie. Takže bubble sort cez zoznamu iterácie nákupný susedných prvkov a vymieňať prvky, ktoré sú v zlom poradí. A to spôsobom, najväčší prvok bude bubliny až do konca. A zoznam je usporiadaný raz viac prvky boli vymenené. 

Takže to sú dva príklady druhu algoritmy, ktoré môžete realizovať pre Program find. Akonáhle dokončíte triediť, a vy ste vykonané hľadanie, budete hotoví. Volám sa Zamyla, a to je CS50. 

[MUSIC PLAYBACK]