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.