[Tónlist spila] 

ZAMYLA CHAN: The fyrstur hlutur þú might tilkynning um að finna er að við nú þegar hafa númerið skrifað fyrir okkur. Þetta er kallað dreifing númer. Þannig að við erum ekki bara að skrifa okkar eigin kóða frá grunni aftur. Frekar erum við að fylla í tóm í sumum fyrirliggjandi kóða. 

The find.c program hvetja til tölur að fylla Heysátan, leitar í Heysátan fyrir notanda lögð nál, og það gerir þetta með því að kalla tagi og leit, aðgerðir skilgreindar í helpers.c. Svo find.c er skrifað nú þegar. Starf þitt er að skrifa framreiðslu. 

Og hvað erum við að gera? Við erum að innleiða tvær aðgerðir. Leit, sem skilar true ef gildi er að finna í Heysátan, aftur false ef gildið er ekki í Heysátan. Og þá erum við líka að innleiða einhverskonar Hvaða tegund array sem heitir gildi. 

Svo skulum takast leit. Leit er nú útfærð sem línuleg leit, en þú getur gert mikið betur en það. Línuleg leit er framkvæmd í O af n tíma, sem er alveg hægt. Þrátt fyrir að það getur leitað Allir lista gefið. Starf þitt er að innleiða tvöfaldur leit, sem hefur rekið sinn o frá log n. Það er ansi hratt. 

En það er áskilnaður. Tvíundarleit getur aðeins leitað með fyrirfram raðað lista. Hvers vegna er það? 

Jæja við skulum líta á dæmi. Fá array af gildum, Heysátan, við erum að fara að horfa að nál. Og í þessu dæmi, heiltölunni þrjú. Leiðin að Tvíundarleit virkar er að við saman á miðju gildi array nálinni mikið eins og hvernig opnað símaskránni að miðju síðu í viku núll. 

Svo eftir að bera saman miðju gildi til nálina, getur þú henda annaðhvort vinstri eða hægri helminginn af array með því að herða mörk þín. Í þessu tilviki, þar sem þrjú, nál okkar, er minna en 10, miðju gildi, rétt bundið getur lækkað. En að reyna að gera mörk þínum eins þétt og mögulegt er. Ef miðju gildið ekki nálina, þá veistu að þú þarft ekki að fela það í leitinni. Svo þú ert rétt bundið getur herða Leita mörk bara örlítið aðeins meira, og svo framvegis og svo framvegis þar til þú finnur nálinni þína. 

Svo hvað þýðir sauðakóðanum líta út? Vel á meðan við erum enn að leita gegnum lista og enn hafa þætti til líta í, taka við miðjum listanum, og bera saman þessi miðju gildi til nál okkar. Ef þeir eru jafnir, þá þýðir að við höfum fann nálina og við getum return true. 

Að öðrum kosti, ef nálin er minna en miðju gildi, þá þýðir það að við getur fleygt hægri helminginn, og bara leita á vinstri hlið af the array. Annars verður við leit að hægra megin í fylkinu. Og í lok, ef þú ert ekki með neina fleiri þættir vinstri til að leita, en þú hef ekki fundið nál þína enn, þá þú return false því nálin örugglega er ekki í Heysátan. 

Nú snyrtilegur hlutur óður í this sauðakóðanum í tvöfaldur leit er að það getur verið túlka sem annað hvort endurtekningu eða endurkvæma framkvæmd. Svo það væri endurkvæma ef þú kallaðir leit virka innan leit virka á hvorum helmingi fylkisins. Við munum ná endurkvæmni svolítið síðar í Auðvitað, en veit að það er kostur ef þú vilt reyna. 

Nú skulum líta á tegund. Raða tekur við fylki og heiltölunni n, sem er á stærð fylkisins. Nú eru ýmsar mismunandi gerðir nokkurs konar, og þú getur litið á nokkur stuttbuxur fyrir kynningum og skýringum. Afrakstur gerð til okkar Raða virka er ógilt. Svo það þýðir að við erum ekki að fara að skila öllum array af tagi. Við erum í raun að fara að breyta mjög array sem var samþykkt í okkur. 

Og það er hægt vegna þess að fylki eru samþykkt með tilvísun í C. Nú munum við sjá meira um þetta síðar, en Meginmunur milli brottför í eitthvað eins heiltala og brottför í fylki, er að þegar þú fara í heiltala, C er bara að fara að gera afrit af þeim heiltölu og standast það við aðgerðina. Upphaflegt breytu verður ekki breytt Þegar aðgerð er lokið. Með fjölda, á hinn bóginn, er það ekki að fara að gera afrit, og þú munt raun verið að breyta mjög array sjálft. 

Svo er ein tegund af tagi val tagi. Val Raða virkar með því að byrja á upphaf, og þá þú iterate yfir og finna minnstu frumefni. Og þá þú skipta að minnsta þáttur við þá fyrstu. Og þá þú fara í annað frumefni , Finna næsta minnstu þáttur, og þá skipta að með Annað þáttur í array þar Fyrsti þátturinn er þegar raðað. Og svo þá sem þú heldur áfram að sérhver þáttur í að greina minnstu gildi og skipta um það út. 

Ég jafngildir 0, the mjög fyrstur þáttur til n mínus 1, ætlar þú að fara að bera saman hvert næsta gildi eftir það og finna vísitölu lágmarks gildi. Þegar þú hefur fundið lágmarks gildi vísitölu, þú getur skipti að verðmæti array lágmarki og array I. 

Önnur gerð af tagi sem þú getur hrinda í framkvæmd er kúla tegund. Svo kúla raða iterates yfir listanum bera samliggjandi þætti og skipta þau atriði sem eru í rangri röð. Og þetta leið, stærsti þátturinn mun kúla til enda. Og listinn er raðað einu sinni ekki meira þættir hafa verið skipti. 

Þannig að þeir eru tvö dæmi um tegund reiknirit sem hægt er að hrinda í framkvæmd fyrir að finna program. Þegar þú hefur lokið að raða, og þú hefur gert leit, þú ert búinn. Mitt nafn er Zamyla, og þetta er CS50. 

[Tónlist spila]