>> ZAMYLA Chan: Ensimmäinen asia, saatat ilmoitus siitä löytää on se, että meillä on jo
on koodi kirjoitettu meille.
Tätä kutsutaan jakelu koodi.
Joten emme vain kirjallisesti oman koodata tyhjästä enää.
Pikemminkin olemme täyttämällä huokoset Joissakin ennestään koodi.
>> Find.c ohjelma kysyy numerot täyttää heinäsuovasta, etsii
heinäpaali varten käyttäjä toimitti neula, ja se tekee tämän soittamalla lajitella ja
haku, tehtävät määritellään vuonna helpers.c.
Joten find.c on kirjoitettu jo.
Sinun tehtäväsi on kirjoittaa auttajia.
>> Joten mitä me teemme?
Olemme täytäntöön kaksi tehtävää.
Haku, joka palauttaa true, jos arvo löytyy Heinäsuovan palaavat
false jos arvo on ei heinäsuovasta.
Ja sitten me toteuttaa myös lajitella, joka järjestää taulukon nimeltään arvoja.
Joten puuttua haku.
>> Haku toteutetaan nykyisin lineaarisena haku.
Mutta voit tehdä paljon parempaa.
Lineaarinen haku toteutetaan O n aika, joka on melko hidas, vaikka se
voi etsiä luettelon sille antaneet.
Sinun tehtäväsi on toteuttaa binäärihaku, joka on ajoaika O log n.
Se on melko nopeasti.
>> Mutta on määräys.
Binäärihaku hakea vain kautta valmiiksi lajiteltu luetteloita.
Miksi näin?
No, katsotaanpa esimerkki.
Ottaen huomioon arvomatriisin, heinäsuovasta, aiomme olla etsimässä
neulaa, ja tässä Esimerkiksi kokonaisluku 3.
>> Siten, että binäärihaku toimii on, että vertaamme keskellä arvo
array neula, aivan kuten miten avasimme puhelinluettelosta keskelle
sivu viikolla 0.
Niin sen jälkeen verrattiin keskisuuria arvoa neula, voit hylätä joko
vasemmalle tai oikealle puolet array kiristämällä rajasi.
Tässä tapauksessa, koska 3, meidän neula, on vähemmän kuin 10, keskimmäinen arvo,
oikea raja voi vähentää.
>> Mutta yritä tehdä rajoja mahdollisimman tiukka.
Jos keskimmäinen arvo ei ole neulaa, niin tiedät, että sinun ei tarvitse
sisällyttää sen haun.
Joten oikea raja voi kiristää haku bounds vain pikkuisen enemmän,
ja niin edelleen ja niin edelleen, kunnes huomaat neulan.
>> Joten mitä pseudo koodi näyttää?
No, kun olemme vielä silmäilyn luettelo ja vielä
elementit katsoa, ​​otamme keskellä luettelon ja vertaa sitä
keskimmäinen arvo meidän neula.
Jos he ovat yhtä, niin se tarkoittaa, olemme löytyi neula, ja voimme
return true.
>> Muussa tapauksessa, jos neula on pienempi kuin keskimmäinen arvo, niin se tarkoittaa, me
voi hävitä oikea puoli ja vain etsi vasemmalla puolella jono.
Muuten me etsiä oikea puoli array.
Ja lopussa, jos sinulla ei ole mitään enemmän elementtejä vasemmalle etsiä mutta et
ei löytynyt neulan vielä, sitten palaat vääriä.
Koska neula ehdottomasti ei ole heinäsuovasta.
>> Nyt yksi siisti juttu tämä pseudo koodin binäärihaku on, että se voi
tulkita joko iteratiivinen tai rekursiivinen täytäntöönpano.
Joten olisi rekursiivinen, jos olet soittanut hakutoiminto sisällä haku
toimiakseen joko puolet array.
Me kattaa rekursio vähän myöhemmin kurssin.
Mutta tiedän, että se on vaihtoehto jos haluat kokeilla.