[Muusika mängib] 

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 lineaarne otsida, kuid mida saate teha palju paremini. Linear otsing rakendatakse O n ajal, mis on üsna aeglane. Kuigi see võib otsida Suvalise loendi 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 nõela. Ja selles näites täisarv kolm. Nii, et binaarne otsing toimib on see, me võrdleme keskel väärtus massiivi nõela meelega kuidas avasime telefoniraamat keskel lehekülje nädal null. 

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 kolm meie nõela on väiksem kui 10, keskväärtusena, 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 õiges seotud ei pinguta otsi piire natukene rohkem, ja nii edasi ja nii edasi, kuni leiad nõela. 

Mis siis pseudokoodi välja näeb? Noh, kui me otsime veel läbi nimekirja ja veel elemente vaata, me keskel nimekirja ja võrrelda seda keset väärtust meie nõel. Kui nad võrdsed, siis see tähendab, et me oleme leidsin nõela ja suudame 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 tagasi false sest nõel kindlasti ei ole heinakuhjas. 

Nüüd puhas asi see pseudokoodi aastal Kahendotsingupuu on, et see võib olla tõlgendada kas iteratiivne või rekursiivne rakendamine. Seega oleks rekursiivne kui sa helistasid otsingu funktsiooni otsing toimida kas pooles massiivi. Me katame rekursioon veidi hiljem muidugi, aga tean, et see on valik, kui soovite, et proovida. 

Nüüd vaatame sort. Sort võetakse massiivi ja täisarv n, mis on suuruse massiivi. Nüüd on mitmeid erinevaid kehvasti, ja saate vaadata mõned püksid demos ja selgitused. Tagasipöördumise tüüp meie funktsioon on tühine. See tähendab, et me ei lähe tagastama array sort. Me tegelikult muudame väga massiiv, mis oli läinud meile. 

Ja see on võimalik, sest massiivid on möödunud viitena C. Nüüd me vaata rohkem sellest hiljem, kuid oluline vahe möödaminnes midagi nagu täisarv ja mööduv massiiv, on see, et kui sa pass täisarv, C on lihtsalt läheb koopia teha, et täisarv ja liigu seda funktsiooni. Originaal muutuja ei muutu kui funktsioon on lõppenud. Reis massiivi, teiselt poolt, on see ei kavatse teha koopia ja sa tegelikult toimetamine väga massiiv ise. 

Nii üht tüüpi sort on valik sort. Valiku sort töötab alates aasta alguses, ja siis kinnitada, üle ja leida kõige väiksem element. Ja siis vaheta see väiksema elemendi esimene. Ja siis liikuda teise elemendi , Leida järgmise väikseim element ja seejärel vahetada, et koos teine ​​element massiivi sest Esimene element on juba järjestatud. Ja nii siis jätkub kõik element väljaselgitamisel väikseim väärtus ja vahetada see välja. 

Sest ma võrdub 0, kõige esimene element kuni n miinus 1, sa lähed, et võrrelda iga järgnev väärtus pärast seda ja leiavad indeksi minimaalne väärtus. Kui leiate minimaalse väärtuse indeksi saab vahetada, et väärtus massiivi miinimum ja array I. 

Teist tüüpi sort, mida saate rakendamiseks on mull sort. Nii mull omamoodi kordab üle nimekirja võrreldes külgnevate elementide ja vahetada elemente on vales järjekorras. Ja sel viisil, suurima elemendi tahe mull lõpuni. Ja nimekiri on sorteeritud kord enam elemendid on vahetatud. 

Nii et need on kaks näidet sort algoritme, mis saab rakendada Leia programm. Kui olete sorteerida ning olete teha otsing, sa oled valmis. Minu nimi on Zamyla ja see on CS50. 

[Muusika mängib]