>> [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]