>> 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 konar, Hvaða tegund array sem heitir gildi.
Svo skulum takast leit.
>> Leit er nú útfærð sem línuleg leit.
En þú getur gert miklu betur en það.
Línuleg leit er framkvæmd í O á n tími, sem er alveg hægt, þótt það
getur leitað póstlista 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ölu 3.
>> 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 0.
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 3, 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 rétt þinn 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 gerir hvað gervi númer líta út?
Jæja, á meðan við erum enn að leita gegnum lista og enn hafa
þættir sem þarf að líta á, að taka við á miðju af listanum og bera það
miðja 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, þá þú aftur ósatt.
Því nálin örugglega er ekki í Heysátan.
>> Nú, einn snyrtilegur hlutur óður í this falsaður kóða í tvöfaldur leit er að það getur
að 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 í námskeiðinu.
En veit að það er möguleiki ef þú vilt reyna.