>> ZAMYLA Chan: Esimene asi, mida võiks teadet leid on see, et meil on juba
on kood kirjutatud meile.
Seda nimetatakse jaotus koodi.
Nii et me ei ole ainult kirjalikult oma koodi nullist enam.
Pigem me täidame tühjad mõnes olemasoleva koodi.
>> Find.c programm küsib numbrid täita heinakuhjas, otsib
heinakuhjas kasutajale esitatud nõel, ja ta teeb seda, kutsudes sorteerida ning
Otsingu funktsioonid määratletud aastal helpers.c.
Nii find.c on kirjutatud juba.
Sinu ülesanne on kirjutada abilised.
>> Niisiis, mida me teeme?
Me rakendamisel kaks ülesannet.
Search, mis tagastab tõene kui väärtus leitakse heinakuhjas, tagasi
false, kui väärtus on ei heinakuhjas.
Ja siis me ka rakendatakse sort, mis sordib massiivi nimetatakse väärtused.
Teeme tegeleda otsing.
>> Otsi praegu rakendatakse lineaarse otsing.
Aga sa saad teha palju paremini.
Linear otsing rakendatakse O n aega, mis on üsna aeglane, kuigi see
saate otsida iga nimekirja talle antud.
Sinu ülesanne on viia ellu binaarne otsing, mis on otsa aeg O log n.
See on päris kiire.
>> Aga seal on klausel.
Binary otsing vaid otsida läbi eelnevalt sorteeritud nimekirja.
Miks see nii on?
Noh, vaatame näiteks.
Kuna massiivi väärtusi, heinakuhjas, me otsima
võtta nõel ja selles Näiteks täisarv 3.
>> Nii, et binaarne otsing toimib on see, me võrdleme keskel väärtus
massiivi nõela meelega kuidas avasime telefoniraamatust keskel
lehekülje Week 0.
Nii et pärast võrreldes keskmise väärtuse nõel, võite visata kas
vasakule või paremale poole massiivi pingutades oma piire.
Sel juhul, kuna 3, meie nõel on vähem kui 10, keskmine väärtus,
seonduv õigus võib väheneda.
>> Aga proovi teha oma piire nii range kui võimalik.
Kui keset väärtus ei ole nõela siis sa tead, et sa ei pea
lisada selle oma otsingut.
Nii et sa oled kindlasti ei pinguta otsi piire natukene rohkem,
ja nii edasi ja nii edasi, kuni leiad nõela.
>> Mis siis pseudo kood välja näeb?
Noh, kui me otsime veel läbi nimekirja ja veel
elemente, et uurida, võtame keskel nimekirja ja võrrelda seda
keskel väärtust meie nõel.
Kui nad võrdsed, siis see tähendab, et me oleme leidsin nõela, ja me saame
tagasi true.
>> Vastasel juhul, kui nõel on alla keskel väärtus, siis see tähendab, et me
ära visata paremal poolel ja lihtsalt search vasakul massiiv.
Vastasel juhul me kontrollime paremal pool massiivi.
Ja lõpuks, kui sa ei ole üldse rohkem elemente vasakule otsida aga sa
ei ole leidnud oma nõela veel siis tagastab false.
Kuna nõel kindlasti ei heinakuhjas.
>> Nüüd üks kena asi see pseudo koodi binaarne otsing on see, et see ei
võib tõlgendada kas iteratiivne või rekursiivne rakendamine.
Seega oleks rekursiivne kui sa helistasid otsingu funktsiooni otsing
toimida kas pooles massiivi.
Me katame rekursioon natuke hiljem muidugi.
Aga tean, et see on võimalus Kui soovite, et proovida.