>> [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]