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