>> 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.