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.