[Musiikki soi] 

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 on tällä hetkellä toteutettu lineaarista hakua, mutta voit tehdä paljon parempaa. Lineaarinen haku on toteutettu O n: n ajan, mikä on varsin hidasta. Vaikka se voi etsiä listassa 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ä esimerkissä, kokonaisluku kolme. Siten, että binäärihaku toimii on, että vertaamme keskellä arvo array neula, aivan kuten miten avasimme puhelinluettelo keskelle sivu viikolla nolla. 

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 kolme, 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 olet oikeassa sidottu voi kiristää haku bounds vain pikkuisen enemmän, ja niin edelleen ja niin edelleen, kunnes huomaat neulan. 

Joten mitä pseudokoodin näyttää? No kun olemme vielä silmäilyn luettelo ja vielä elementtejä katso, otamme keskellä luettelon, ja vertaa, että keski arvoa meidän neula. Jos he ovat yhtä, niin se tarkoittaa, olemme löysi neulan 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 ole löytänyt neulan vielä, niin olet palauttaa false, koska neula varmasti ei ole heinäsuovasta. 

Nyt siisti asia tässä pseudokoodina binary haku on, että se voi olla tulkitaan 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 Tietenkin, mutta tiedän, että se on vaihtoehto, jos haluat kokeilla. 

Nyt katsokaamme tavallaan. Järjestä vie array ja kokonaisluku n, joka on koko jono. Nyt on olemassa erilaisia ​​erittäin lajittelee, ja voit katsoa joitakin shortsit demoja ja selityksiä. Palautuva meidän lajittelu on mitätön. Niin se tarkoittaa, että emme aio palauttamaan array lajitella. Olemme todella aikoo muuttaa hyvin array, joka johdettiin meille. 

Ja se on mahdollista, koska ryhmät ovat läpäissyt viitteeksi C. Nyt me Katso lisää tästä myöhemmin, mutta Olennainen ero ohimennen jokseenkin kokonaisluku ja kulkee array, on, että kun pass kokonaisluku, C on juuri menossa tehdä kopio, että kokonaisluku ja siirtää sen toiminnon. Alkuperäinen muuttuja ei muutu kun toiminto on valmis. Kun joukko, toisaalta, se on aio tehdä kopio, ja voit todella muokkaamalla hyvin array itse. 

Joten yksi tyyppi sort on valinta lajitella. Valinta lajitella toimii aloittamalla alussa, ja sitten kerrata yli ja löytää pienin alkio. Ja sitten vaihtaa, että pienin elementti, jossa ensimmäinen. Ja sitten siirtyä toiseen elementtiin , Löytää seuraavaksi pienin elementti, ja sitten vaihtaa että Toinen alkio, koska ensimmäinen elementti on jo järjestetty. Ja niin sitten jatkat jokaiselle elementti tunnistamisessa pienin arvon ja vaihtamalla sen ulos. 

Sillä minä ollessa 0, ensimmäinen elementti N miinus 1, olet menossa vertailla jokainen seuraava arvon jälkeen ja löytää indeksi on pienin arvo. Kun löydät minimiarvon indeksi, voit vaihtaa että arvo array vähimmäis-ja array I. 

Toinen tyyppi tavallaan, että voit täytäntöön on kupla tavallaan. Joten kupla lajitella iteroi lista vertaamalla vierekkäisten elementtien ja vaihtava elementtejä, jotka ovat väärässä järjestyksessä. Ja tällä tavalla, suurin osa tulee kupla loppuun. Ja luettelo on järjestetty kerran enää elementit ovat vaihtuneet. 

Joten ne ovat kaksi esimerkkiä sort algoritmeja, jotka voit toteuttaa Find Program. Kun olet lajitella ja olet tehty haku, olet valmis. Nimeni on Zamyla, ja tämä on CS50. 

[Musiikki soi]