ZAMYLA CHAN: pirmas dalykas, kurį galėtų pranešimas apie radinį, kad mes jau yra kodas parašyta mums. Tai vadinama platinimo kodas. Taigi mes ne tik raštu mūsų pačių Kodas iš nulio nebėra. Atvirkščiai, mes užpildant ertmes kai iš anksto esamą kodą. 

Find.c programa paragina numerius užpildyti kaugė, ieško kaugė vartotojo pateikta adata, ir tai daroma telefonu rūšiuoti ir ieškoti, funkcijos apibrėžtos į helpers.c. Taigi find.c parašyta jau. Jūsų darbas yra rašyti pagalbininkai. 

Taigi, ką mes darome? Mes įgyvendinti dvi funkcijas. Paieška, kuri grąžina true, jei vertė randama šieno kupetoje, grįžta false, jei reikšmė yra ne kaugė. Ir tada mes taip pat įgyvendinant rūšiuoti, kuri rūšiuoja masyvas vadinamas vertės. Taigi galime spręsti paiešką. 

Paieška šiuo metu įgyvendinamas kaip linijinio paiešką. Bet jūs galite padaryti daug geriau nei tai. Linijinis paieška įgyvendinama O n laikas, kuris yra gana lėtas, tačiau jis gali ieškoti bet kokių jai suteiktus sąrašą. Jūsų darbas yra įgyvendinti dvejetainis paieškos, kuri skaičiuoti laiką O log n. Tai gana greitai. 

Tačiau yra nuostata. Dvejetainiai paieškos gali ieškoti tik per surūšiuotas sąrašus. Kodėl taip yra? Na, pažiūrėkime į pavyzdį. Atsižvelgiant vertybių masyvas, kaugė, mes ketiname būti ieškote Pereiti prie adatos, ir tai Pavyzdžiui, sveikasis skaičius 3. 

Taip, kad dvejetainis paieška veikia tai, kad mes palyginti vidurinį vertę masyvas adata, panašiai kaip mes atidarėme telefonų knygą į vidurį puslapis 0 savaitės. Taigi palyginus vidurinį vertę adata, galite išmesti arba kairę arba į dešinę pusę masyvo veržiant savo ribas. Šiuo atveju, kadangi 3, mūsų adata, yra mažiau nei 10, viduriniosios vertė, teisė riba gali sumažėti. 

Bet pabandyti padaryti savo ribas taip griežtai, kaip įmanoma. Jei vidurinioji vertė yra ne adata, tuomet jūs žinote, kad jums nereikia įtraukti jį į savo paiešką. Taigi, jūsų teisė jungiasi gali sugriežtinti Paieškos ribų Truputėlį daugiau, ir taip toliau ir taip toliau, kol jums rasti adatą. 

Taigi, ką daro pseudo kodas atrodo? Na, o mes vis dar ieško per sąrašas ir dar elementai ieškoti, mes per vidurį sąrašo ir palyginkite, kad vidutinio vertė mūsų adata. Jei jie vienodi, tada tai reiškia, kad mes rasti adatą, ir mes galime return true. 

Priešingu atveju, jei adata yra mažesnis nei vidutinio vertė, tai reiškia, kad mes gali išmesti tinkamą pusę ir tik ieškoti kairėje pusėje masyvo. Priešingu atveju, mes ieškoti Dešinėje pusėje masyvo. Ir pabaigoje, jei jūs neturite daugiau elementų paliko ieškoti bet jūs neradau savo adatą dar, tada return false. Nes adata tikrai nėra šieno kupetoje. 

Dabar vienas tvarkingas dalykas apie šį pseudo kodas dvejetainėje paieškos yra tai, kad ji gali būti aiškinama arba kaip kartotinis arba grįžtamojo įgyvendinimas. Taigi būtų grįžtamojo jei vadinamas paieškos funkcija per paiešką veikti abiejose masyvo pusę. Mes padengti rekursija truputį vėliau į paskaitas. Bet žinau, kad tai yra galimybė jei norite pabandyti.