[Muusika mängib] 

ANDI PENG: Welcome to nädalas 3 punkti. Aitäh, kutid, kõik tulevad sellele varem algusaeg täna. Meil on kena, veidi intiimne rühm täna. Loodetavasti jõuame viimistlus, ehk alguses, natuke varajane täna. Nii kiiresti, vaid mõned Teated päevakorda täna. Enne kui hakkame me oleme läheb lihtsalt minna üle põgusat logistiliste küsimuste, pset küsimused, Küsitlusel asju. Ja siis me ka kohe. Me kasutame siluri nimetatakse GDB, et alustada paljastaja meie kood, mis David selgitatud loeng. Me läheme üle nelja liiki kehvasti. Me läheme üle neid päris kiiresti kuna nad on üsna intensiivsed. Aga tean, et kõik slaidid ja lähtekoodi on alati online. Nii vabalt, on teie tutvumiseks, et tagasi minna ja heita pilk selle. 

Me läheme läbi asümptootilise märke, mis on lihtsalt fancy viis öelda "runtimes" kus meil on suur O, mis David selgitatud loeng. Ja meil on ka Omega, mis on alampiir tööaega. Ja me räägime natuke rohkem põhjalikku selle kohta, kuidas need tööd. Ja lõpuks, me läheme üle Kahendotsingupuu, sest paljud, kes on juba heitis pilgu oma psets ilmselt teate, et see on küsimus, mis on oma pset. Nii saate kõik olla õnnelik et me katta see täna. 

Ja lõpuks, ühe oma paragrahvi tagasisidet, ma tegelikult lahkus umbes 15 minutit temperatuuril lõppu lihtsalt minema üle logistika pset3, küsimusi, võibolla natuke juhendamist, kui soovite, Enne kui hakkame programmeerimine. Nii proovime läbi saama materjal päris kiiresti. Ja siis me saame veeta aega võttes rohkem küsimusi jaoks pset. OKEI. 

Kiiresti, lihtsalt mõned Teated enne kui hakkame täna. Esiteks, tere tegemine läbi kaks oma psets. Võtsin pilk your-- jah, olgem saada aplausi, et üks. Tegelikult olin tõesti, tõesti muljet. Ma sorteeritud esimene pset kutid Viimase nädala ja kutid tegid uskumatu. 

Stiil oli punkt Lisaks mõned kommentaarid. Veenduge, et olete alati Kommenteerides oma koodi. Aga teie psets olid punkti. Ja hoida see üles. Ja see on hea teehöövel näha, et kutid on hakanud nii palju vaeva oma stiili ja oma disaini oma koodi et me tahaksime näha, kuidas. Nii et ma kulgeb piki oma tänulikkust ülejäänud TAS. 

Kuid seal on paari Küsitluse küsimused Ma tahan minna üle, et teeks nii minu elu ja palju teisi Ajutise töötaja elu veidi lihtsamaks. Esiteks, ma olen märganud seda Varem week-- kui paljud teist käinud check50 kohta koodi enne kui saadate? OKEI. Nii et igaüks peaks tegema check50, because-- secret-- me tegelikult joosta check50 osana meie õigsuse skripte testida oma kood. Seega, kui teie kood ei suuda check50, suure tõenäosusega see on ilmselt läheb ei meie kontrolli ka. Mõnikord poisid on õiged vastused. Jms, ahne, mõned Teil on õigus numbrid, sa lihtsalt välja printida mõned ekstra kraam. Ja see ekstra kraam tegelikult ei kontrolli, sest arvuti ei tea, mis see on otsite. Ja nii see lihtsalt joosta, näha, et oma toodangut ei mängu, mida me ootame vastust olla, ja märkige see on vale. 

Ja ma tean, mis juhtus mõned juhtumid sel nädalal. Nii et ma läksin tagasi ja käsitsi Humberliigitatud igaühe koodi. Tulevikus aga Palun veendu, et näed vaadake 50 oma koodi. Sest see on selline valu TA to pean minema tagasi ja käsitsi ümberliigitamisotsuse iga pset iga ühe, natuke jäi näiteks. Nii et ma ei võtnud ära kõik punktid. Ma arvan, et ma võtsin võibolla üks või kaks disain. Tulevikus aga kui sa ei suuda check50, aspekti võetakse off õigsuse eest. 

Lisaks psets on tõttu reedeti kell. Ma arvan, et seal on seitse minutit lõpus ajapikendust, et anname. Per Harvard aega, nad lubatud seitse minutit hiljaks kõike. Nii et siin Yale'i, siis me järgima, et samuti. Aga päris palju, kell 00:07, kui teie pset ei ole, see saab olema märgistatud nii hilja. Ja nii, kui see on märgitud nii hilja, siis TA-- ma olen ikka läheb liigitamise oma psets. Nii näete ikka hinne ilmuda. Samas teame, et lõpuks semester, kõik hilja psets lihtsalt olla automaatselt nullida arvuti. 

Me teeme seda kahel põhjusel. Üks, mõnikord saame vabandatav, nagu Dean vabandusi, hiljem, et ma ei tea veel. Nii me tahame veenduda, et me oleme liigitamine kõik igaks juhuks, nagu ma olen puudu Dean vabandust. Ja teiseks, pidage meeles, sa võid veel tilk üks pset, et on täies ulatuses punktid. Ja nii me tahame hinne kõik oma psets lihtsalt veenduda, et teie ulatus on seal ja sa üritad neid. Nii et isegi kui see on hilja, siis ikka laenu saada ulatus punktid, ma arvan. 

Nii loo moraal on, et Veenduge, et teie psets on õigeaegne. Ja kui nad ei ole õigeaegne, tean, et see ei ole suur. Jah, enne kui ma liikuda, kas keegi on küsimusi pset tagasisidet? Jah. 

Sihtrühm: Kas sa ütlesid me võib langeda ühe psets? 

ANDI PENG: Jah. Nii et üheksa psets üldist jooksul semestri. Ja kui teil on ulatus points-- nii ulatus on lihtsalt, päris palju, mida sa selle katse Probleem on teil kasutusele aja, sa näitab, et olete näidanud olete lugenud spec. See on päris palju ruumi. Ja kui te täitmisel ulatus punktid, me võib langeda madalaim ühe välja täies ulatuses. Nii et oma eelise täiendada ja proovida iga pset. 

Isegi upload-- kui ükski need tööd, laadige neid kõiki. Ja siis me loodetavasti võimalik annan teile mõned neist punktid tagasi. Cool. Muid küsimusi? Hea. 

Teiseks, kontoris hours-- mõne kiire märkmeid tööaega. Nii esimene, tulevad varakult sel nädalal. Keegi on kunagi varem tööaega esmaspäeviti. Christabel tuli tööaega eile õhtul. Jah, Christabel. Ja mida on meil kontoris tundi eile õhtul, Christabel? 

Sihtrühm: Meil ​​oli jäätis. 

ANDI PENG: Nii see on õige, meil oli jäätise tööaega eile õhtul. Kuigi ma ei saa lubada, et me peame jäätist tööaega iga nädal, mida ma luban on see, et seal on tunduvalt parem õpilane TA suhe. Nagu legit, see on nagu 00:57. Arvestades, võrdlen Neljapäev, sul umbes 150 tõesti rõhutas lapsed ja no jäätist. Ja see lihtsalt ei ole produktiivne kellelegi. Nii loo moraal on, tule varakult to tööaega ja head asjad juhtub. 

Samuti tulevad valmis küsimusi esitada. Sa tead? Sõltumata sellest, mida ajutise töötaja, ma arvan, on öelnud, oleme olnud saada paar õpilased kes tulevad neljapäeval kell, nagu, 10:50 ei lugenud spec on nagu mind aidata, aidake mind. Kahjuks sel hetkel, seal on ei ole palju me saame teha, et aidata teil. Nii et palun tule varakult sel nädalal. Tule varakult tööaega. Tule valmis küsimusi esitada. Veenduge, et teie üliõpilane, on kus sa pead olema nii, et Ajutise töötaja võivad aidata teil mööda, mis on see, mida tööaega tuleks jaotus. 

Teiseks, nii et ma tean, professorid meeldib meid üllatada testidega. Mul oli professor need nagu, yo, muide, mäletan, et Kontrolltöö sul on järgmisel esmaspäeval. Jah, ma ei teadnud, et kongressi. Nii et ma lähen, et TA mis meenutab teile kõigile, et viktoriin 0--, sest sa tead, et me oleme CS. Nüüd, kui me oleme teinud massiivid, saad miks see viktoriin 0, ei viktoriin 1, eh? OKEI. Oh, ma sain mõned chuckles, et üks. OKEI. 

Nii viktoriini 0 on 14. oktoober, kui sa oled esmaspäeval kolmapäevani osa ja 15. oktoobril, kui sa oled teisipäeval-neljapäev osa. See ei kehti Neile, Harvardi Kes-- Ma arvan, et sa kõik olla võttes oma viktoriinid 14.. 

Nii et jah, järgmisel nädalal, kui David, loengus, läheb, Jah, nii umbes, et viktoriin järgmisel nädalal, siis kõik ei Ehmusin sa tulid osa ja te teate, et teie Viktoriin 0 on kaks nädalat. Ja me peame läbivaatamine istungid ja puha. Nii ei ole muret on hirmul selle eest. Kõik küsimused before-- küsimusi üldse kohta logistiliste küsimuste, liigitamine, tööaega, lõigud? Jah. 

Sihtrühm: Nii viktoriini on läheb ajal loeng? 

ANDI PENG: Jah. Nii viktoriin, ma arvan, on 60 minuti eraldatud selle aja pesa et sa lihtsalt võtta loengute. Nii et sa ei pea tulema kohta, nagu juhuslik 07:00. See kõik on hea. Jah. Cool. 

Hästi. Nii et me läheme kasutusele mõiste teile sel nädalal, et David on juba selline on käsitlenud loengus seda viimase nädala jooksul. Seda nimetatakse GDB. Ja kui paljud teist, samas käigus kirjalikult oma psets, märganud suur nupp, mis ütleb, "Debug" peal oma IDE? OKEI. Nüüd me tegelikult saada väljakaevamine mõistatus, mida see nupp tegelikult teeb. Ja ma garanteerin teile, et see on ilus, ilus asi. 

Nii siiani, ma arvan seal on olnud kaks asja õpilased on tavaliselt teed, kui silumine psets. Üks, nad kas lisada printf () - nii iga paar rida, lisavad nad on printf () - oh, mis see on muutuv? Oh, mis see on muutuv now-- ja sa sellist näha progresseerumise oma koodi, kuna see töötab. Või teine ​​meetod lapsed teha, on et nad lihtsalt kirjutada kogu asi ja siis niimoodi lõpus. Loodetavasti see toimib. Ma garanteerin teile, GDB on parem kui mõlemal viisil. Jah. Nii see on teie uus parim sõber. Sest see on ilus asi mis visuaalselt näitab nii mida teie kood on teinud kindlal samuti seda, mida kõik oma muutujad on kaasas, nagu mida nende väärtused on, tollel kindlal hetkel. Ja sel viisil, saab tõesti määrata murdepunkti oma koodi. Võite käivitada läbi rida-realt. Ja GDB peavad lihtsalt eest sa, kuvatakse teile, Mis kõik oma muutujad on, mida nad teevad, mis toimub kood. Ja sellisel viisil, et see on nii palju lihtsam näha mis toimub asemel printf-se või kirjalikult ette oma avaldustega. 

Nii et me teeme näide sellest hiljem. Nii et see tundub natuke abstraktne. Ära muretse, me teeme näiteid. Ja nii sisuliselt kolm suuremat, enamkasutatavaid funktsioone peate GDB on Next Step üle, ja Astu nupud. Ma lähen pea üle seal, tegelikult, just nüüd. 

Nii saab kutid kõik näeme, et või peaks ma suumida natuke? Aasta tagasi, kas sa nägid seda? Kas ma suumida? Natuke? OK, lahe. Seal me läheme. OKEI. 

Nii et mul on siin, minu rakendamise eest ahne. Ja kui palju te poisid kirjutas ahne samas loop form-- et on täiesti vastuvõetav viis seda teha see-- üks viis seda teha on lihtsalt lõhe moodul. Sest siis võite lasta hinna ja siis on teie ülejäänud. Ja siis saate lihtsalt lisada see kõik koos. Kas loogika, mida ma teen siin mõtet igaüks, Enne kui hakkame? Midagi sarnast? Cool. Hea. See on päris seksikas tükk koodi, ma ütleks. Nagu ma ütlesin, Taavet Loeng, mõne aja pärast, saate kõik ilmuvad koodi midagi, mis on ilus. Ja mõnikord, kui sa näed ilus kood, see on selline imeline tunne. 

Nii aga samas see kood on väga ilus, see ei tööta korralikult. Nii saab käivitada check50 selle. Vaata 50 20-- oop. 2? Kas see pset2? Jah. Oh, pset1. OKEI. Nii võtame check50. 

Ja kui poisid näevad siin see ei suuda paar juhtudel. Ja mõned teist, et Loomulikult teeme oma probleem komplekti, sa oled nagu, ah, miks see ei tööta. Miks on töötanud mõned väärtusi, kuid mitte teiste jaoks? Noh, GDB läheb, et aidata teil arv miks need sisendid ei tööta. 

OKEI. Vaatame, üks kontrolli Olin löögiks check50 oli sisendkäibemaksu 0,41. Nii et õige vastus, et siis peaks olema saada on 4. Kuid selle asemel, mida ma väljatrükk on 3-n, mis on vale. Nii saab lihtsalt käivitada käsitsi, lihtsalt veenduge, et check50 töötab. Teeme ./greedy. Oih, ma pean tegema ahne. Seal me läheme. Nüüd ./greedy. 

Kui palju on võlgu? Teeme 0.41. Ja eks me näe siin et see väljastamiseks, 3 kui õiget vastust, tegelikult peaks olema 4. Nii saab sisestada GDB ja kuidas me võib minna, millega määratakse kindlaks selle probleemi. 

Seega esimene samm alati silumist koodi on määrata murdepunkti, või koht, kus sa soovite, et arvuti või siluri alustada vaadates. Nii et kui sa tõesti ei tea, mis su probleem on, Tavaliselt, tüüpiline asi, mida me tahame tegema, on määrata oma murdepunkti on peamine. Nii et kui te poisid ei vaata seda punast nuppu seal, yep, mis oli mulle määramisel murdepunkti põhiülesanne. Ma klõpsake seda. 

Ja siis ma saan minna oma Debug nuppu. Ma tabanud seda nuppu. Lubage mul taas vähendamiseks, kui saan. Seal me läheme. Nii et meil on siin, paneel õigus. Vabandust, poisid taga, siis ei saa tõesti näha tõesti hästi. Aga sisuliselt kõik Selle õiguse paneel teeb on jälgida nii esile line, mis on rida koodi et arvuti töötab praegu, samuti kõiki oma muutujate siia alla. 

Nii et sul senti, mündid, n, kõik deklareeritud erinevaid asju sel hetkel. Ära muretse, sest me ei ole tegelikult vormindatud neid ühtegi veel muutujaid. Nii arvuti, teie arvuti lihtsalt näinud, oh, 32767 viimati kasutatud funktsiooni Selle mälu minu arvutis. Ja nii see on, kus senti praegu on. Aga no, et kui sa jooksed koodi see peaks olema vormindatud. 

Nii lähme läbi, rida line, mis toimub siin. OKEI. Nii siin on kolm nuppe, et ma lihtsalt seletada. Sul on Play või Run funktsiooni, nuppu, siis on samm üle nuppu, ja teil ka Astu nuppu. Ja sisuliselt kõik kolm neid lihtsalt minna läbi oma koodi ja teha erinevaid asju. 

Nii tavaliselt, kui sa silumine, me ei taha lihtsalt vajuta Play, sest Play lihtsalt joosta oma koodi selle lõpus. Ja siis sa tegelikult ei tea, mida oma probleemiga on, kui seate mitu murdepunktid. Kui seate mitu murdepunktid, See lihtsalt automaatselt kestab üks murdepunkt, Järgmise, et järgmine. Aga sel juhul me oleme lihtsalt, et üks, sest me tahan töötada meie tee ülevalt alla alt. Nii et me läheme ignoreerida seda nuppu just nüüd Käesoleva programmi. 

Nii Astuüle funktsioon lihtsalt sammud üle iga rea ja ütleb teile, mida arvuti teeb. Samm funktsionaalsusest läheb tegelikud funktsiooni see on sinu rida koodi. Nii näiteks, nagu printf (), mis on funktsioon, eks? Kui ma tahtsin füüsiliselt sammu arvesse printf () funktsiooni, Ma tegelikult minema tükk kood, kus printf () kirjutatud ja vaata Mis seal toimub. 

Aga tavaliselt eeldame, et kood, mis me teile toimib. Eeldame printf () töötab. Me eeldame, et GetInt () töötab. Seega puudub vajadus samm neid funktsioone. Aga kui seal funktsioonid et sa kirjutad ise mis sa tahad, et kontrollida teada, mis toimub, sa tahaksid astuda arvesse, et funktsioon. 

Nii just nüüd lihtsalt lähen astuda üle selle tüki koodi. Vaatame. Oh, print, "Oh hai, kuidas palju muutusi on ees? " Me ei hooli. Me teame, et see töötab, nii me samm üle. 

Nii n, mis on meie float, et me oleme initialized-- või declared-- kuni tipus, me oleme nüüd võrdsustades et GetFloat (). Nii saab astuda üle, et. Ja me näeme juures alumine siin, programmi annab märku, et ma sisend väärtus. Nii saab sisestada väärtuse tahame testida siit, mis on 0,41. Hea. 

Nüüd n-- te poisid näha Siin on bottom-- see stored-- sest me ei ole ümardatud veel, et see on salvestatakse see nagu hiiglaslik float, et on ,4099999996, mis on piisavalt lähedal, et meie eesmärkidel, just nüüd, 0,41. Ja siis me näeme hiljem, kui me jätkuvalt üle astuda programmi pärast siin, n on muutunud ümar ja senti on saanud 41. Hea. Nii et me teame, et meie ümardamine töövõime. Me teame, et meil on õige arv senti, nii et me teame, et see on ei ole tõesti probleem. 

Nii jätkame tõhustamist kohta selles programmis. Käime siin. Ja nii pärast seda rida koodi, me peaks teadma, kui palju neljandikku meil. Me astume üle. Ja sa näed me tegelikult üks kvartalis, sest me oleme maha 25 meie esialgne väärtus 41. Ja meil on 16 vasakul meie senti. 

Kas igaüks aru, kuidas Programmi astutakse läbi ja miks senti on nüüd 16 ja miks nüüd, mündid on muutunud 1? Kas kõik seda loogikat järgida? Cool. Nii nagu seda hetkel, Programmi töö, eks? Me teame, et see teeb täpselt mida me tahame seda. Ja me tegelikult ei välja trükkida, oh, mida on senti sel hetkel, Mis on mündid selles punktis. 

Jätkame läbimas programmi. Samm üle. Cool. Me läheme üle dimes. Hea. Me näeme, et see on võetud off $ 0.10 peenraha. Ja nüüd on meil kaks münti. See on õige. 

Me läheme üle penni ja näeme et meil jääb üle senti. Hmm, see on kummaline. Siin üleval on programm, pidin et on lahutatakse oma penni. Võib-olla ma lihtsalt ei olnud tehes seda rida paremalt. Ja oh häda, näed siin, sest me teame, et meil sekkub sisseviivaid 32 ja 33, see on koht, kus meie programmi valesti oli muutujad joosta. Nii saame vaadata ja näha, oh, Ma lahutades senti siin aga ma ei ole tegelikult lisada oma mündi väärtus. Ma lisades senti. Ja ma ei taha lisada senti, ma tahan lisada, et münte. Nii et kui me muudame, et münte, meil tööprogrammi. Ma saan käivitada check50. Sa võid väljuda GDB õigus siin ja seejärel käivitage check50 uuesti. Ma võiks lihtsalt teha. Ma pean tegema ahne. 0.41. Ja siin see on trükkimine välja õige vastuse. 

Nii nagu te poisid ei vaata, GDB on tõesti võimas vahend sest kui meil on nii palju koodi läheb edasi ja nii palju muutujaid et see on raske meie jaoks, nagu inimene, jälgida. Arvuti, on GDB siluri, on võime jälgida kõike. Ma tean, in Visionaire, kutid ilmselt oleks tabanud mõnda killustatust vead sest sa jooksid auti oma valikut. Näites Caesar, mis on täpselt, mida ma olen rakendanud siin. 

Nii et ma unustasin, et kontrollida Mis juhtuks, kui ma ei olnud kaks käsurea argumente. Ma lihtsalt ei pane, et kontrollida. Ja kui ma saan Debug-- seadsin minu murdepunkti, et seal. Ma saan Debug. 

OKEI. Jah. Seega tegelikult GDB pidi et on mulle rääkinud seal oli killustatust süü olemas. Ma ei tea, mis juhtus seal, aga kui ma jooksin seda, see töötas. Kui sul tekib rida koodi abil ja GDB võib lihtsalt lõpetavad järsku sulle, Mine ja vaata, mis punase viga on. See ütlen teile, hei, sa oli killustatust süü, mis tähendab, et sa üritasid pääseda ruumi massiivi, et ei ole olemas. Jah. 

Nii järgmises probleemi seada sel nädalal, kutid Tõenäoliselt on palju muutujad ujuvad ringi. Sa ei kavatse olla kindel, mida nad kõik tähendavad teatud hetkel. Nii GDB tõesti aitab teil figuring välja, mida nad kõik on võrdsed ja on võimalik näha, et visuaalselt. Kas keegi segi kuidas ükskõik mis töötas? Cool. Hästi. Nii et pärast, et oleme läheb sukelduda õigus arvesse on neli erinevat tüüpi kehvasti sel nädalal. Kui paljud teist, esimene kõik, enne kui hakkame, lugenud kogu spec pset3? OKEI. Ma olen uhke teie kutid. See on nagu pool klassi, mis on oluliselt rohkem kui eelmisel korral. 

Nii see on suurepärane, sest kui me räägime sisu in lecture-- või kahju, in section-- Mulle meeldib seostada palju, et tagasi sellele, mida pset on ja kuidas sa tahad rakendada, et oma pset. Nii et kui sa tuled, millel loe spec, siis see olla palju lihtsam mõista mida ma räägin, kui ma ütlen, oh hei, see võib olla tõesti Hea koht rakendada sellist. Nii neile, kes on lugenud spec tean, et osa oma pset, sa lähed pea kirjutada tüüpi omamoodi. Nii et see võib olla väga kasulik jaoks palju sa täna. 

Nii me alustad, Sisuliselt kõige lihtsam tüübist omamoodi, valik omamoodi. Tüüpiline algoritm kuidas me tahaks edasi minna on-- David läbis need kõik loeng, nii et ma kiiresti edasi liikuda siin-- sisuliselt, siis on massiivi väärtusi. Ja siis leiad Väikseim sorteerimata väärtus ja sa vahetada, et väärtus Esimeses sorteerimata väärtus. Ja siis muudkui korrates ülejäänud oma nimekirja. 

Ja siin on visuaalne selgitus kuidas see töötaks. Nii näiteks, kui olime alustada array viiest elemendist, indeks 0-4, 3, 5, 2, 6 ja 4 väärtuste paigutatud array-- seda praegu, Me elame eeldada et nad kõik sorteerimata sest me pole harjunud teisiti. 

Niisiis, kuidas valik omamoodi oleks Töö on see, et see oleks esimene jookseb läbi kogu sorteerimata massiivi. Oleks noppida väikseim väärtus. Sel juhul 3, eks Nüüd, on väikseim. Läheb 5. Nope, 5 ei ole suurem than-- või kahju, ei ole vähem than-- 3. Nii minimaalne väärtus on veel 3. Ja siis sa saad 2. Arvuti näeb, oh, 2 on väiksem kui 3. 2 Nüüd tuleb minimaalne väärtus. Ja nii 2 vahetustehingud selle esimene väärtus. 

Nii et pärast ühe pass, me tõepoolest näha et 2 ja 3 on vahetatud. Ja me lihtsalt läheb jätkata teed Selle jälle ülejäänud massiivi. Nii et me läheme lihtsalt joosta Viimase nelja indeksid massiivi. Me näeme, et 3 on Järgmise minimaalne väärtus. Nii et me läheme vahetada, et 4. Ja siis me lihtsalt läheb hoida kulgeb läbi kuni lõpuks sa saada sortida massiivi kus 2, 3, 4, 5 ja 6 on kõik järjestatud. Kas kõik mõistavad loogika kuidas valik omamoodi töötab? 

Sa pead lihtsalt mingisugune maksumusega vähemalt. Sa jälgida, mis see on. Ja iga kord, kui te leida seda, kui swap see esimese väärtus array-- või mitte esimene value-- Järgmise väärtuse massiivi. Cool. 

Nii nagu te poisid liiki nägin lühike pilguheit, me ei kavatse pseudokoodi seda. Nii et kui te poisid taga taha moodustavad rühma, igaüks laua võib moodustada väike partner, ma lähen teile sinusuguseid kolm minutit lihtsalt rääkida läbi loogika, inglise, kuidas me võiksime olla võimeline rakendama pseudokoodi kirjutada valikut omamoodi. Ja seal on kristalliseerunud. Palun tulla ja saada kommi. Kui oled taga ja soovid kommi, ma ei viska kristalliseerunud sind. Tegelikult teevad sina-- lahe. Oi vabandust. OKEI. 

Nii et kui me tahaksime, kui klassi, kirjutada pseudokoodi kuidas võiks läheneda Selle probleemi lihtsalt vabalt. Ma lihtsalt ringi käia ja selleks, küsida rühmad Järgmise rida mida me peaksime tegema. Nii et kui te tahate alustada off, mis on esimene asi, mida teha, kui sa üritad rakendada nii, et lahendada see programm valikuliselt sortida nimekirja? Lihtsalt eeldame me on massiiv, eks? 

Sihtrühm: Sa tahad luua mõned omamoodi [kuuldamatu], et sa oled kulgeb läbi oma terve rida. 

ANDI PENG: Right. Nii et sa lähed tahan kinnitada, läbi iga ruum, eks? Nii suur. Kui te tahate, et anna mulle Järgmine LINE yeah, taga. 

Sihtrühm: Kontrollige neid kõik seotud väikseim. 

ANDI PENG: Seal me läheme. Nii et me tahame minna läbi ja kontrollige vaata, mida minimaalne väärtus on, eks? Ma lähen lühendada, et "min". Mis te poisid tahavad teha pärast olete leidnud minimaalne väärtus? 

Sihtrühm: [kuuldamatu] ANDI PENG: Nii et sa lähed tahan lülitage see on esimene, mis massiivi, õige? See on alguses, ma lähen ütlen. Hästi. Nüüd, et olete vahetasid esimese üks, mida sa tahad teha pärast seda? Nüüd me teame, et see siin peab olema väikseim väärtus, eks? Siis on veel ülejäänud massiiv, mis on sorteerimata. Mida sa tahad teha siin, kui te poisid tahavad mulle reale? Sihtrühm: Nii siis tahan korrata kogu ülejäänud massiivi. ANDI PENG: Jah. Ja mis ei iterating läbi Selline tähenda me ilmselt vaja? Mis tüüpi of-- 

Sihtrühm: Oh, veel muutuja? ANDI PENG: Tõenäoliselt teine ​​silmus, eks? Nii et me ilmselt läheb taha itereerima through-- suur. Ja siis läheme tagasi ilmselt kontrollige minimaalset uuesti, õige? Ja sa lähed, et hoida korrates Selles, sest silmad lihtsalt läheb hoida töötab, eks? 

Nii nagu te poisid ei vaata, me lihtsalt üldine pseudokoodi kuidas me tahame seda programmi vaatama. See Kerrata siin, mida me Tavaliselt on vaja kirjutada oma koodi Kui me tahame korrata kaudu massiiv, mis tüüpi struktuuriga? Ma arvan Christabel juba öelnud seda varem. 

Sihtrühm: A loop. 

ANDI PENG: A loop? Täpselt. Nii et see on ilmselt saab olema silmus. Mis on check siin läheb tähenda? Tavaliselt, kui sa tahad, et kontrollida kui midagi on midagi else-- 

Sihtrühm: Kui. 

ANDI PENG: IF, eks? Ja siis swap siin, siis me minna üle hiljem, sest David läks läbi, et loeng samuti. Ja siis teine ​​Kerrata implies-- 

Sihtrühm: Teine silmus. 

ANDI PENG: --another silmus, täpselt. Nii et kui me vaatame sel õigesti, me näete, et me ilmselt läheb vaja astmelist silmus koos tingimisi avalduse olemas ja siis tegelik tükk kood, mis on läheb vahetada väärtusi. Nii et ma olen lihtsalt üldiselt kirjutatud pseudokoodi koodi siin. Ja siis me tegelikult toimub füüsiliselt, rühmana proovida rakendada seda täna. Lähme tagasi selle IDE. 

Uh-oh. Miks see nii on Mitte-- seal on. OKEI. Vabandame, lubage mul proovida suumida natuke rohkem. Seal me läheme. Kõik, mida ma siin teen on lõin programmi nimega "valik / sort.c." Olen loonud hulgaliselt üheksa väärtusi, 4, 8, 2, 1, 6, 9, 7, 5, 3. Praegu kui võimalik vaata, nad on ebakorrapärane. n saab olema number, ütleb summa väärtused sa pead oma valikut. Sel juhul on meil üheksa väärtusi. Ja ma olen just for loop siin mis prindib sorteerimata massiivi. 

Ja lõpuks, ma sain ka eest loop, et lihtsalt trükib need välja. Nii teoreetiliselt kui see programm töötab korralikult, lõpus, näed trükitud loop milles 1, 2, 3, 4, 5, 6, 7, 8, 9 on kõik korrektne. 

Nii on meil meie pseudokoodi siin. Kas keegi taha mina-- Ma olen lihtsalt lähe küsima volunteers-- ütle mulle täpselt, mida kirjutada, kui tahame kõigepealt lihtsalt kordamiseks läbi alguses massiivi? Mis koodirida ma olen ilmselt läheb vaja siin? 

Sihtrühm: [kuuldamatu] 

ANDI PENG: Jah, tunnen tasuta mina-- kahju, siis ei pea seisma up-- tunne tasuta häält tõsta natuke. 

Sihtrühm: For int i võrdub 0-- 

ANDI PENG: Jah, hea. 

Sihtrühm: i on väiksem kui massiivi pikkus. 

ANDI PENG: Nii hoida pahanda siin, sest me ei ole funktsioon, mis ütleb meile pikkus array, meil on juba väärtus, mis salvestab seda. Õigus? Teine asi, mida meeles in mind-- massiivi üheksa väärtused, mida on indeksid? Ütleme nii, et see massiiv oli 0-3. Sa näed, et viimane indeks on tegelikult 3. See ei ole 4, kuigi seal neli väärtust massiivi. 

Nii siin, me peame olema väga ettevaatlikud mida meie tingimus pikkus läheb. 

Sihtrühm: Kas ei oleks n miinus 1? ANDI PENG: See läheb n miinus 1, täpselt. Kas see mõtet, miks see on n miinus 1, igaüks? See on sellepärast, massiivid on null-indekseeritud. Nad algavad 0 ja kestab kuni n miinus 1. Jah, see on natuke keeruline. OKEI. Ja siis-- Sihtrühm: Isnt'1 et juba hoolitsenud küll, lihtsalt ei ütle, "väiksem või võrdne "ja lihtsalt öelda" alla? " 

ANDI PENG: See on tõesti hea küsimus. Nii et jah. Aga ka see, kuidas me oleme rakendamise kontrollimise õigus, on vaja võrrelda kahte väärtust. Nii et sa tegelikult tahad jäta ", et" tühjad. Sest kui võrrelda see, et sa ei kavatse midagi pärast seda võrrelda, eks? Jah. Nii i ++. Lisame meie sulgudes. Oih. Hea. Nii et meil on algusest Meie välimine loop. Nüüd me ilmselt tahad luua muutuja hoidmiseks jälgida väikseim väärtus, eks? Kas keegi taha mulle anda koodirida, mis teha? Mida me vajame, kui me läheme tahad salvestada midagi? 

Õigus. Võib-olla õigem nimetus, mis oleks olla-- "temp" täiesti works-- võibolla rohkem tabavalt nimeks oleks, Kui me tahame, et väikseim value-- 

Sihtrühm: Min. ANDI PENG: min, siis me läheme. min oleks hea. Ja nii siin, mida me soovid täita seda? See on natuke keeruline. Sest just nüüd on alguses see rida, Te ei ole uurinud midagi, eks? Mis siis, automaatselt, kui me oleme lihtsalt i võrdub 0, Mida me tahame initsialiseerida Meie esimene minimaalne väärtus? Sihtrühm: i. ANDI PENG: i, täpselt. Christabel, miks me tahame initsialiseerida see i? 

Sihtrühm: Sest, noh, me alustades 0. Nii et meil on midagi võrrelda see on minimaalne lõpuks on 0. 

ANDI PENG: Täpselt. Nii ta on täpselt õige. Kuna meil ei ole tegelikult vaatasin veel midagi, Me ei tea, mis meie minimaalne väärtus on. Tahame lihtsalt initsialiseerida see i, mis praegu on siinsamas. Ja kui me jätkuvalt liiguta alla selle massiiv, Me näeme, et iga täiendavaid pass, i kaupa. Ja nii sel hetkel, i on ilmselt läheb tahan olla minimaalne, sest see saab olema iganes on algusest sortimata massiivi. Cool. 

Nüüd tahame lisada jaoks silmus siin see on läheb itereerima läbi sorteerimata või ülejäänud seda valikut. Kas keegi taha mulle koodirida, mis teha? Hint-- mida me vajame siin? Mis toimub minna seda loop? Jah. Sihtrühm: Nii et me tahaks on erinev täisarv sest meil hakkab läbi ülejäänud massiivi asemel i, et äkki j. 

ANDI PENG: Jah, j kõlab hästi mulle. Vastus? 

Sihtrühm: Nii oleks i pluss 1, sest sa oled hakanud järgmisel väärtus. Ja siis väljatöötamiseni seda uuesti, j on väiksem kui n miinus 1, ja siis j ++. ANDI PENG: Hea. 

Ja siis siin, me ei kavatse taha vaadata, kui meie tingimus on täidetud, õige? Sest sa tahad muuta minimaalne väärtus kui see on tegelikult väiksem kui see, mida Sa võrdled seda, eks? Mida me siis tahame siin? Saate näha. Mis tüüpi aruanne me ilmselt läheb ti soovite kasutada, kui me soovite kontrollida midagi? 

Sihtrühm: kui avaldus. 

ANDI PENG: kui avaldus. Nii kui-- ja mida saab olema tingimusel, et me tahame sees Meie, kui avaldus? 

Sihtrühm: Kui väärtus j on väiksem kui väärtus i-- 

ANDI PENG: Täpselt. Nii kui-- nii see massiivi nimetatakse "massiivi." Hea. Nii et kui array-- mis see oli? Ütle, et uuesti. 

Sihtrühm: Kui massiiv-j alla array-i, siis muudaks min. Nii min oleks j. 

ANDI PENG: Kas see on mõtet? OKEI. Ja nüüd siin, me tegelikult tahan rakendada swap, eks? Nii meenutavad loengu, et David, kui Ta püüdis vahetada the-- mis oli see-- apelsinimahla ja milk-- 

Sihtrühm: See oli raske. 

ANDI PENG: Jah, see oli omamoodi raske. Aga see oli päris hea mõiste näitab aeg. Nii et mõtle oma väärtusi siin. Sul massiivi min, massiivi i, või mis iganes me üritasime vahetada siin. Ja siis ilmselt ei saa valada need üksteist samal ajal, eks? Mida me läheme et on vaja luua siin et vahetada väärtusi õigesti? 

Sihtrühm: Ajutine muutuja. 

ANDI PENG: Ajutine muutuja. Nii teeme int temp. Vt käesoleva oleks parem aeg mina-- oot, mis see oli? OKEI. Nii et see oleks olnud parem aega nimetada muutuja "temp." Nii teeme int temp. Mida me saame seada temp võrdne siin? Sihtrühm: Min? ANDI PENG: See on natuke keeruline. See tegelikult ei ole oluline, et lõpuks. See ei ole oluline milliseid Et valida swap nii kaua, kui sa üritad kindel, et sa oled jälgida, mida sa vahetada. 

Sihtrühm: See võiks olla massiiv-i. 

ANDI PENG: Jah, teeme hulgaliselt-i. Ja mis siis on järgmisel real koodi me tahame siin? Sihtrühm: array-i võrdub massiivi-j. ANDI PENG: Ja lõpuks? Sihtrühm: array-j võrdub massiivi-i. Sihtrühm: Või array-j võrdsete array-temp-- või temp. 

ANDI PENG: OK. Nii saab käivitada ja vaata kui see läheb tööle. Kus on, et juhtub? Oh, see on probleem. Vaata, real 40, me oleme üritab kasutada massiivi-j? Kuid kust j olemas ainult? 

Sihtrühm: In silmus. ANDI PENG: Right. Mida me siis peame tegema? 

Sihtrühm: määratleda väljaspool the-- Sihtrühm: Jah, ma arvan, et teil on kasutada teise if, eks? Nii nagu, kui miinimum-- Olgu, las ma mõtlen. 

ANDI PENG: Poisid, proovige heita Olgem vaata, mida on midagi, mida me teha saame siin? 

Sihtrühm: OK. Nii et kui minimaalse ei võrdu j-- nii et kui miinimum on ikka i-- siis ei oleks meil vahetada. 

ANDI PENG: Kas see on võrdne i? Mida sa tahad öelda? 

Sihtrühm: Või jah, kui Minimaalne ei võrdu i, yeah. ANDI PENG: OK. Noh, mis lahendab, millist meie probleeme. Aga see ikka ei lahenda probleemi, mis juhtub, kui j-- kuna j ei ole olemas väljaspool seda, mida sa tahame teha? Kuulutada välja? Proovime töötab see. Uh-oh. Meie omamoodi ei tööta. 

Nagu näete, meie esialgne massiiv oli neid väärtusi. Ja hiljem ta peaks olema olnud 1, 2, 3, 4, 5, 6, 7, 8, 9. See ei tööta. Ahh. Mida me siis teeme? Sihtrühm: Debug. ANDI PENG: Okei, saame proovida seda. Saame siluda. Zoom out natuke. Räägime meie murdepunkti. Lähme like-- OK. 

Nii, sest me juba teame, et need read, 15 kuni 22, on working-- sest kõik, mida ma teen on lihtsalt iterating läbi ja printing-- Võin minna ja jäta see. Alustame kell line 25. Oop, lase mind lahti saada sellest. 

Sihtrühm: Nii murdepunkti on kus silumine hakkab? ANDI PENG: või seiskub. Sihtrühm: või seiskub. ANDI PENG: Jah. Võimalik on määrata mitu murdepunktid ja see võib ainult hüpata ühest teise. Aga sel juhul me ei tea kus viga juhtub. Nii et me lihtsalt tahame alustada ülevalt alla. Yep. OKEI. 

Nii et see joon siin, saame samm. Näete siin, meil massiivi. Need on väärtused, mis on massiiv. Kas te näete, et kui indeks 0, siis vastab value-- oh, Ma lähen, et proovida suurendada. Vabandame, see on tõesti raske to see-- kell massiivi indeks 0, meil on väärtus 4 ja Seejärel neljanda ja nii edasi. Meil on kohalikud muutujad. Praegu i on võrdne 0, mida me tahame seda. 

Ja nii Jätame astutakse läbi. Meie miinimum on võrdne 0, mida me ka tahame seda. Ja siis me siseneda meie sekundis loop, kui massiiv-j on väiksem kui massiivi-i, mida ta ei olnud. Nii sa nägid, kuidas et vahele üle, et? 

Sihtrühm: Nii peaks, kui minimaalne, kõik selle-- ei tohiks see sees esimene silmus? ANDI PENG: Ei, sest sa ikka tahad testida. Sa tahad teha võrdluse iga aega, isegi pärast sa jooksed läbi. Sul ei ole lihtsalt tahan seda teha Esimesel läbipääs. Sa tahad seda teha Iga täiendava pass uuesti. Nii et sa tahad, et kontrollida Teie seisundi sees. Nii et me lihtsalt läheb hoida läbiv siin. Ma annan sulle poisid vihje. See on seotud asjaoluga, et kui loed oma tingimuseks, sa ei kontrolliks õige indeks. Nii kohe loed jaoks massiivi indeks j on väiksem kui massiivi indeks i. Aga mida sa teed üles Alguses silmus? Kas sa ei kehtestamisel j võrdne i? 

Jah, nii saame tegelikult väljumiseks siluri siin. Võtame pilk meie pseudokoodi. For-- läheme start kell i võrdub 0. Me läheme kuni n miinus 1. Kontrollime, kas meil on see õige? Yep, et oli õige. 

Siis sees siin, me oleme kavatse luua minimaalne väärtus ja määrata, et võrdne i. Kas me seda teeme? Yep, tegin seda. Nüüd on meie sisemine silmus, me oleme kavatseb teha j võrdub i kuni n miinus 1. Kas me seda teeme? Tõepoolest, me tegime seda. 

Nii aga mida me võrrelda siin? 

Sihtrühm: j pluss 1. ANDI PENG: Täpselt. Ja siis sa lähed soovite seada Sinu minimaalne võrdne j pluss 1 samuti. Nii et ma läksin läbi, et tõesti kiiresti. Kas te poisid aru miks see j pluss 1? OKEI. 

Nii oma rida, in Sinu esimese läbida, Sinu jaoks silmus, et int i võrdub 0, olgem lihtsalt oletame, et tegemist ei ole veel muutunud. Meil on hulgaliselt, täiesti, vaid nelja sorteerimata elemente, eks? Nii et me tahame initsialiseerida i võrdne 0. Ja ma ei kavatse lihtsalt jookseb läbi selle silmuse. Ja nii esimeses pass, me ei kavatse initsialiseerida muutuja nimega "min" et ka võrdne i, sest meil ei ole minimaalset väärtust. Nii et praegu on võrdne 0 samuti. Ja siis me läheme läbi. Ja me tahame korrata uuesti. Nüüd, kui oleme leidnud selle, mida meie miinimum on, me tahame korrata läbi uuesti näha, kas see on võrreldes, eks? Nii j, siin läheb võrdsele i, mis on 0. Ja siis, kui massiivi j pluss i, mis on see, et järgmiseks üle, kui vähem kui see, mida teie praegune minimaalne väärtus on, tahad vahetada. 

Nii ütleme lihtsalt me ​​oleme sai, nagu, 2, 5, 1, 8. Just nüüd, ma on võrdne 0 ja j on võrdne 0. Ja see on meie miinimumi. Kui massiiv-j pluss i-- nii et kui üks see on pärast üht me vaatame on suurem kui esimene enne, see saab muutuda minimaalne. 

Nii et siin me näeme, et 5 ei ole vähem. Nii see läheb ei ole 5. Me näeme, et 1 on alla 2, eks? Nüüd me teame, et meie miinimum saab olema indeksi väärtus 0, 1, 2. Jah? Ja siis, kui sa siin, saab vahetada õige väärtusi. 

Nii et kui te poisid olid lihtsalt võttes j Enne, sa ei vaata ühe pärast seda. Sa otsisid sama väärtusega, mis Sellepärast ta lihtsalt ei tee midagi. Kas see mõtet kõigile, miks meil on vaja, et pluss 1 on? OKEI. Nüüd lihtsalt jookseb läbi see, et Kindlasti ülejäänud kood on õige. Miks on see juhtub? Ah, see on min siin. Olime võrrelda vale väärtus. Oh ei. 

Oh yeah, siia alla olime Vahetatakse vale väärtuste samuti. Kuna otsisime i ja j. Need on need, olime kontrollida. Me tegelikult tahad vahetada vähemalt praeguse minimaalne, iganes see väljaspool on. Ja kui poisid ei vaata alla siin on meil sorteeritud massiivi. See lihtsalt oli pistmist asjaolu, et kui olime kontrollimine väärtusi meid võrrelda, me ei otsinud õigel väärtusi. Otsisime samal ühe Siin ei ole tegelikult see vahetada. Sul on vaadata ühe järgmise seda ja siis saate vahetada. Nii et see, mis oli omamoodi pealtkuulamise meie koodi enne. Ja mida ma tegin siin on kõike siluri oleks võinud teha teile Ma lihtsalt tegin seda kohta pardal, sest see on lihtsam näha selle asemel suumimiseks siluri. Kas see mõtet kõigile? Cool. 

Hästi. Me saame liikuda edasi rääkima asümptootilise märke, mis on lihtsalt fancy viis öelda runtimes kõiki neid kehvasti. Nii et ma tean, David, loengus, puudutanud runtimes. Ja ta käis läbi kogu valem kuidas arvutada runtimes. Ära muretse selle pärast. Kui sa oled tõesti uudishimulik kuidas see töötab, julgelt minuga rääkida pärast osa. Me ei käi valemid koos. Aga kõik kutid on tõesti tean, et n ruudus jagatud 2 on sama asi nagu n ruudus. Kuna kõige rohkem, astendaja, kasvab kõige. Ja nii meie eesmärkidel, kõik me hoolime on see, et hiiglane number, mis on kasvanud. 

Mis on parimal juhul Runtime valiku omamoodi? Kui sa lähed on itereerima läbi nimekirja ja siis korrata läbi ülejäänud seda nimekirja, mitu korda on sa lähed ilmselt, halvimal case-- on Parimal juhul sorry-- joosta? Võib-olla on parem küsimus on küsida, milline on kõige mustema Runtime valiku omamoodi. Sihtrühm: n ruudus. ANDI PENG: See on n ruudus, eks. Nii lihtne mõelda see on nagu, iga kord, kui on kaks pesitseda jaoks silmuseid, see saab olema n ruudus. Sest mitte ainult sa läbiv taas sa pead minema tagasi ümber ja jookseb läbi see jälle sees iga väärtus. Nii et juhul, näed n korda n ruudus, mis on-- vabandust, n korda n, mis võrdub n ruudus. 

Ja omamoodi on ka natuke unikaalne selles mõttes, et see ei ole oluline, kas need väärtused on juba selleks. See on ikka läbiks niikuinii. Ütleme nii, et see oli 1, 2, 3, 4. Sõltumata sellest, kas see oli Selleks, et ikka oleks jooksis läbi ja veel kontrollida minimaalne väärtus. See oleks teinud Sama arvu kontrolli iga kord, isegi kui see tegelikult ei puutu midagi. 

Nii sellisel juhul paremini ja halvemini runtimes on tegelikult samaväärne. Nii et oodata runtime Valiku omamoodi, millele meil määrata sümboliga beta, teeta, sel juhul Samuti oleks n ruudus. Kõik need kolm oleks n ruudus. Kas kõik selge, miks Runtime on n ruudus? 

Hästi. Nii et ma olen lihtsalt läheb kiiresti käivitada läbi ülejäänud kehvasti. Algoritmi mull sort-- mäletan, see oli esimene David läks üle loengus. Sisuliselt sa samm läbi kogu nimekiri ja sa swap-- sa lihtsalt võrrelda kahte korraga. Ja kui üks on suurem, kui sa lihtsalt vahetada neid. Nii et kui need on suuremad, siis oleks vahetada. Mul ametlik siin. 

Nii ütleme lihtsalt sul oli 8, 6, 4, 2. Sa võrrelda 8 ja 6. Sa pead vahetada neid. Sa oleks võrrelda 8 ja 4. Sa pead vahetada neid. Kui teil on vahetada 8 ja 2, muuta neid samuti. Nii selline tunne, näete, mängitakse läbi pika aja jooksul, kuidas väärtused mingi mull otsad, mis on, miks me nimetame seda mull omamoodi. 

Me lihtsalt joosta uuesti Meie teine ​​pass, ja meie kolmas pass, ja meie neljas pass. Sisuliselt mull omamoodi lihtsalt jookseb kuni sa ei tee enam vahetustehinguid. Nii selles mõttes, et see on lihtsalt üldise pseudokoodi ta. Ära muretse, need kõik on online. Me ei pea tegelikult minna üle selle. 

Me lihtsalt initsialiseerida counter muutuja, mis algab 0. Ja me korrata läbi terve rea. Ja kui üks väärtus on-- kui see väärtus on suurem kui väärtus, sa lähed, et vahetada neid. Ja siis sa oled lihtsalt läheb edasi. Ja sa lähed loota. Ja sa oled lihtsalt kavatse hoida teed Käesoleva samas lugeja suurem kui 0, mis tähendab, et iga kord, sa pead swap, sa tead sa tahad minna tagasi ja vaadata uuesti. Sa tahad, et hoida kontrolli kuni te ei tea et sa ei pea vahetada enam. 

Mis on parim ja halvim Juhul runtimes mull omamoodi? Ja hint-- see on tegelikult erinev valikust omamoodi mõttes et need kaks vastust ei ole samad. Mõelge, mis juhtuks juhul, kui see oli juba järjestatud. Ja mõelda, mida juhtuks, kui see oli puhul, kus see ei järjestatud. Ja saab omamoodi joosta läbi, miks see juhtub. Ma annan sulle poisid, nagu, 30 sekundit mõelda seda. 

OKEI. Kas keegi on vist see, mida Halvimal juhul runtime mull sorteerida on? Jah. 

Sihtrühm: see oleks nagu, n korda n miinus 1 või midagi sellist? Nagu iga kord, kui ta jookseb, see on lihtsalt, nagu üks swap vähem mis iganes see oli. 

ANDI PENG: Jah, nii sa oled täiesti õige. Ja see on juhtum, kus oma Vastus oli tegelikult keerulisem kui üks peame andma. Nii see läheb run-- ma olen läheb kustutab kõik see siin. Kas kõik hea? Kas ma saan kustutada selle? OKEI. Sa lähed joosta n korda esmakordselt, eks? Ja nad ei kavatse joosta n miinus 1 teine ​​kord, eks? Ja siis sa lähed hoida läheb, n minu 2, jne. Taavet tegi seda loengus, kus Kui te liita kõik need väärtused, sa saad midagi, mis on like-- yeah-- üle 2, mis oma olemuselt lihtsalt vähendab alla n ruudus. Sa lähed, et saada imelik osa seal. Ja nii lihtsalt tean, et n ruudus alati ülimuslik osa. Ja nii sel juhul, halvimal Runtime oleks n ruudus. Kui see oli kahanevas Selleks, arvan, sa pead tegema swap iga kord. 

Mis oleks, potentsiaalselt Parimal juhul runtime? Ütleme lihtsalt, kui loetelu on juba selleks, milline oleks Runtime olla? 

Sihtrühm: n. ANDI PENG: See on n, täpselt. Ja miks on see n? Sihtrühm: Sest sa lihtsalt kontrollima iga kord. ANDI PENG: Täpselt. Nii parimal võimalikul runtime, kui see nimekiri oli juba sorted-- oletame 1, 2, 3, 4-- sa oleks lihtsalt läbi minema, siis oleks vaadata, sa näeksid, oh, nad kõik üle viia. Ma ei pea vahetama. Olen lõpetanud. Nii et juhul, see on lihtsalt n või mitmeid samme sa lihtsalt oli kontrollida esimeses nimekirja. 

Ja pärast, nüüd tabas sisestamise sorteerida, kus algoritm on sisuliselt lõhe see sorditud ja sortimata osa. Ja siis ükshaaval sorteerimata väärtused lisada oma asjakohased positsioone loendi alguses. 

Nii näiteks on meil nimekiri 3, 5, 2, 6, 4 uuesti. Me teame, et see on praegu sorteerimata sest oleme lihtsalt Hakkasin uurima seda. Me vaatleme ja me teame, et esimene väärtus on järjestatud, eks? Kui oled ainus vaadates massiivi suurus ühe, sa tead, et see on järjestatud. 

Nii siis me teame, et Ülejäänud neli sorteerimata. Me läheme läbi ja me näeme, et väärtus. Lähme tagasi. Vaata, et väärtus 5? Me vaatleme seda. Me võrdleme seda 3. Me teame, et see on suurem kui 3, nii et me teame, et see on järjestatud. Nii et me teame nüüd, et kaks esimest on järjestatud ja viimased kolm ei ole. 

Me vaatleme 2. Kõigepealt vaadake seda 5. Kas see on väiksem kui 5? See ei ole. Nii et me peame hoidma alla vaadates. Siis vaadake 2 välja 3. Kas see vähem kui? Ei. Nii et sa tead 2 tuleb lisada arvesse ees ja 3 ja 5 Nii tuleb välja lükata. Tehke seda jälle 6 ja 4. Ja me lihtsalt hoida kontrolli sisuliselt kus me lihtsalt vaadata, vaadata, vaadata. Ja kuni see on õiges positsioon, meil sellist lihtsalt pistke see õiges asendis, mis on nime korral see tuli. 

Nii et lihtsalt algoritm, pseudokoodi per se, omamoodi, kuidas me ellu insertsioonis omamoodi. Pseudokoodi on siin. See kõik on online. Ära muretse, kui teiega on üritab kopeerida selle alla. Nii et taas, sama question-- mida oleks parim ja halvim runtimes sisestamiseks omamoodi? See on väga sarnane viimasele küsimusele. Ma annan sulle poisid, nagu, 30 sekundit mõtlema ka. 

OK Kas keegi taha mulle halvim runtime? Jah. 

Sihtrühm: n ruudus. 

ANDI PENG: See on n ruudus. Ja miks on see n ruudus? 

Sihtrühm: Sest vastupidises järjekorras, siis on läbima n korda n, mis on-- ANDI PENG: Jah, täpselt. Nii sama asi nagu mull omamoodi. Kui see nimekiri on järjekorras, et sa oled läheb on kõigepealt kontrollida üks kord. Ja siis iga lisaväärtust, sa oled läheb on võrdlemisel iga väärtus, eks? Ja nii kokku, sa lähed tegema n pass korda teise n läbida, mis on n ruudus. Aga parim juhtum? Jah. 

Sihtrühm: n miinus 1, sest Esimene neist on juba ruudus. 

ANDI PENG: Nii lähedal. Vastus on tegelikult n. Kuna samal ajal esimene on sorteeritud, ei pruugi see actually-- see me lihtsalt lucked tegemiseks, et näiteks, et 2 juhtus olema väikseim number. Aga see ei ole alati nii. Kui 2 on juba järjestatud alguses aga sa vaatad ja seal on 1 siin, 1 läheb juhtuma see. Ja see läheb lõpuks up on lõin niikuinii. 

Nii et parimal juhul, see on tegelikult lihtsalt saab olema n. Kui teil on 1, 2, 3, 4, 5, 6, 7, 8, sa oled läbiks et kogu nimekirja kord vaadata, kas kõik on korras. Kas kõik selge jooksmine korda valiku ka? Ma tean, et ma lähen läbi Nende tõesti kiire. Aga tean, et kui sa tead üldmõisteid, siis peaks olema hea. OKEI. Nii et ma lihtsalt annan teile poisid äkki, nagu, minut rääkida oma naabritega mida on vaid mõned peamisi erinevusi nende tüüpide vahel kehvasti. Me läheme üle, et varsti. Sihtrühm: Oh, OK. ANDI PENG: Jah. OKEI. Cool, olgem taasalustama klassina. OKEI. Nii et see oli omamoodi avatud küsimus selles mõttes, et seal on palju vastuseid neile. Ja me läheme üle mõned neist lühidalt. Ma lihtsalt tahtsin sulle poisid mõelda, mida eristab kõigi kolme sorti. Ja ma kuulsin ka, suur question-- mida ei Merge omamoodi teha? Hea küsimus, sest see on mida me hõlmava kõrval. 

Nii liita omamoodi on üks omamoodi, mis toimib väga erinevalt teistest kehvasti. Nagu te poisid saavad see-- Taavet seda teha demo kus ta oli kõik lahe müra näha, kuidas ühendada Sorteeri jooksis, nagu, lõpmatult kiiremini kui teised kaks liiki? OKEI. Nii et sellepärast ühendamine Sorteeri rakendab et lõhe ja vallutada mõiste, et me oleme rääkisime palju loengus. Selles mõttes, et meile meeldib töötada targemaks, ei raskem, kui jagate ja vallutada probleeme, ja murda neid maha ja siis pane need kokku, head asjad alati juhtuma. 

Nii nii, et ühendada Sorteeri sisuliselt töötab on, et see jagab sorteerimata massiivi poole. Ja siis see ju kaks poolt massiivid. Ja see lihtsalt sorteerib need kaks poolt. See lihtsalt hoiab jagades pooleks, in pool, poole, kuni kõik on järjestatud ja siis rekursiivselt paneb see kõik koos. 

Nii et tõesti abstraktne. Nii et see on lihtsalt natuke pseudokoodi. Kas see mõtet kuidas see töötab? Nii ütleme lihtsalt teil on massiivi n elementi, eks? Kui n on väiksem kui 2, siis saad tagasi. Sest sa tead, et kui seal on Ainult üks asi, see tuleb sorteerida. Else, sorteerida vasakul pool, ja siis sorteerida õige poole, ja siis liita. 

Niisiis, kui see tundub tõesti lihtne, tegelikult mõelda seda on Selline keeruline. Sest sa oled nagu, Noh, see on omamoodi töötab ise. Õigus? See töötab ise. Nii selles mõttes, David puudutanud upon recursion klassis. Ja see mõiste me räägime rohkem. See, et asjaolu, et need kaks rida siin, tegelikult on lihtsalt programm ütlen seda käivitada ise erinevate sisend. Nii et pigem joosta ennast tervikuna n elementi, saab jaotada see sisse vasakul pool ja paremal pool ja seejärel käivitage see uuesti. 

Ja siis me vaatame seda visuaalselt, sest ma olen visuaalne õppija. See toimib paremini mulle. Nii me vaatame visuaalne näide. 

Oletame, et meil on hulgaliselt kuus elemente, 3, 5, 2, 6, 4, 1, mitte sorteerida. Olgu, seal on palju sellel lehel. Nii et kui te kutid saate vaadata Esimene samm siit, 3, 5, 2, 6, 4, 1, saate jagada see pooleks. Sul on 3, 5, 2, 6, 4, 1. Sa tead, et need aren't-- sa ei tea, kas nad järjestatud või mitte, nii hoiate murdes neil maha, poole, pooleks, pooleks, kuni lõpuks sul on ainult üks element. Ja üks element on alati järjestatud, eks? 

Nii et me teame, et 3, 5, 2, 4, 6, 1 ise, on järjestatud. Ja nüüd me ei pane neid uuesti kokku. Saame teada, et 3, 5. Panime need kokku. Me teame, et on sorteeritud. 2 on ikka alles. Me ei pane 4 ja 6 kokku. Me teame, et see on järjestatud, Niisiis panime kokku. Ja 1 on olemas. 

Ja siis sa lihtsalt vaadata Nende kahe poole siin. Sul on 3, 5, 2, 2, 3, 5. Sa võid võrrelda hakanud kõike. Sest sa tead, et see on järjestatud ja sa tead, et see on järjestatud. Siis sa ei pea isegi võrdle 5, sa lihtsalt võrrelda 3. Ja 2 on väiksem kui 3, nii sa tead, 2 peab minema lõpuni. 

Sama asi seal. 1. peab minema siit. Ja siis, kui sa lähed panna Nende kahe väärtuse kokku sa tead, et see sorteeritakse ja sa tead, et see on järjestatud. Nii siis 1 ja 2 1 on alla 2. See ütleb teile, et 1 peaks minema lõpuks see isegi ilma vaadates 3 või 5. Ja siis 4, saate lihtsalt vaadake, see läheb otse siin. Sa ei pea vaatama 5. Sama asi 6. Sa tead, et 6-- see lihtsalt ei tuleks käsitleda. 

Ja nii, et teed, sa oled lihtsalt säästa ennast palju samme, kui sa võrrelda. Sa ei pea võrrelda iga element vastu muid elemente. Sa lihtsalt võrreldakse ones et on vaja võrrelda seda vastu. Nii et selline abstraktne mõiste. Ära muretse, kui see ei ole üsna lööb sind veel. Aga üldiselt on see kuidas ühendamise omamoodi toimib. Küsimused, kiiret küsimust, enne kui ma liikuda? Jah. 

Sihtrühm: Nii et sa ütlesid, et te võtate 1 ja seejärel 4 ja 6 ja panna neid. Nii ei ole those-- ei sa neid vaadates eraldi elemendid, mitte kogu? ANDI PENG: Jah. Mis juhtub on see, et sa põhimõtteliselt loovad täiesti uue massiivi. Nii et sa tead, et siin on mul Kahe rea suurus 3, eks? Nii et sa tead, et minu sorteeritud massiiv peab olema kuus elementi. Nii et sa lihtsalt luua uus mälu. Nii et sa oled selline nagu on raiskav mälu, kuid mis ei ole oluline sest see on nii väike. Nii te vaatate 1 ja te vaatate 2. Ja sa tead, et 1 on alla 2. Nii et sa tead, et 1 peaks minema alguses Kõigil neil. 

Sa ei pea isegi vaadata 3 ja 5. Nii et sa tead 1 läheb seal. Siis sa põhimõtteliselt tükelda ära 1. See on nagu surnud meile. Siis me lihtsalt 2, 3, 5, ja siis 4 ja 6. Ja siis sa tead, et sa võrrelda 4 ja 2, oh, 2 peaks sinna minna. Nii et sa sulpsti 2 alla, siis selle maha raiuda. Siis sa lihtsalt pead 3 ja 5 4 ning 6. Ja sa lihtsalt hoida raiumine ära kuni paned neid array. 

Sihtrühm: Nii et sa oled lihtsalt alati võrreldes [kuuldamatu]? 

ANDI PENG: Täpselt. Nii selles mõttes, et sa oled lihtsalt võrrelda sisuliselt üks number võrreldes teiste number. Ja kuna sa tead et see on järjestatud, siis ei pea otsima läbi kõik numbrid. Sa pead lihtsalt vaadata esimene. Ja siis saate lihtsalt sulpsti neid maha, sest sa tead nad kuuluvad, kus nad peavad kuuluma. Jah. Hea küsimus. 

Ja kui siis keegi teist on natuke ambitsioonikas, vabalt vaadata seda koodi. See on tegelikult tegelik rakendamine kuidas me kirjutada ühendamine omamoodi. Ja näed, et see on väga lühike. Aga ideede see on päris keeruline. Nii et kui teil on tunne, nagu joonistus see välja oma kodutöö täna julgelt. 

OKEI. Ja Taavet läks ka üle selle loengu. Mis on parimal juhul runtimes, halvimal juhul runtimes, ja oodata runtimes of ühendamine omamoodi? Paar sekundit mõelda. See on päris raske, kuid selline intuitiivne kui sa mõtle selle peale. Hästi. 

Sihtrühm: Kas halvimal juhul n log n? ANDI PENG: Täpselt. Ja miks on see n log n. 

Sihtrühm: Kas mitte sellepärast, et ta muutub eksponentsiaalselt kiiremini, nii et see on nagu sõltuvus, mis selle asemel, et lihtsalt lihtsalt seda n ruuduline või midagi? ANDI PENG: Täpselt. Nii et põhjus, miks Runtime sellel on n log n on because-- mida sa teeme kõik need sammud? Sa oled lihtsalt raiumine selle pooleks, eks? Ja nii, kui me teeme sisse, kõik, mis ta teeb on jagades probleem pooleks, pooleks, pooleks, rohkem pooleks. Ja selles mõttes, saate liiki ning kõrvaldada lineaarne mudel et me olen kasutanud. Sest kui sa karbonaad asjad poole, see on samamoodi. See on lihtsalt matemaatiline viis seda väljendada. 

Ja siis lõpuks, lõpuks, sa oled lihtsalt tegemist ühe viimase läbida panna nad kõik selleks, eks? Ja kui sa lihtsalt pead vaadake üks asi, mis on n. Ja nii sa oled selline korrutades kaks kokku. Nii et see on nagu sul, et lõplik vaadake n siin koos log n siin. Ja kui sa korrutada neid, mis on n log n. 

Ja nii parima kui ka halvima Juhul ning oodata on kõik n log n. Samuti nagu teine ​​omamoodi. See on nagu valikut omamoodi selles mõttes, et see Ei ole oluline, milline on sinu nimekiri on, see lihtsalt läheb teha sama asja iga kord. OKEI. Nii nagu te poisid ei vaata, kuigi kehvasti, et oleme läinud through-- n ruuduline, see ei ole väga tõhus. Ja isegi see n log n on ei ole kõige tõhusam. Kui Te olete uudishimulik, seal on omamoodi mehhanismid mis on nii tõhus, et nad peaaegu põhiliselt tasased tööaega. 

Sul on mõned log n on. Sul on mõned log log n on. Me ei puuduta neid Selle klassi praegu. Aga kui te kutid on uudishimulik, julgelt Google, mis on kõige tõhusam sortimine mehhanismid. Ma ei tea, on mõned tõesti naljakas ones, like-- seal on mõned tõesti naljakas ones, et inimesed teevad. Ja sa ei tea, kuidas nad kunagi mõelnud, et. Nii google, kui teil on mõni vaba aja, milline on mõned naljakas viise et people-- samuti tõhus ways-- inimesed suutnud rakendada kehvasti. OKEI. Ja siin on lihtsalt mugav väike skeem. Ma tean, et te kõik, enne seda viktoriini 0, on oma toas ilmselt üritab meelde, et. Nii et on tore seal kutid. Lihtsalt ärge unustage loogika, et made-- miks need numbrid olid toimunud. Kui sa oled alati kadunud, lihtsalt kindel, et tead, mida kehvasti on. Ja sa võid joosta neid meelt aru saada, miks neid Vastused on need vastused. 

Hästi. Nii et me läheme liikuma kohta, lõpuks, et otsida. Sest kui need teile kes on lugenud pset, otsing ei ole ka osa Sel nädalal probleem seab. Teil palutakse rakendada kahte tüüpi otsinguid. Üks on lineaarne otsing ja üks on binaarne otsing. 

Nii lineaarne otsing on üsna lihtne. Sa tahad otsida element loetelu, et näha, kui sa saad selle. Sa pead lihtsalt korrata läbi. Ja kui see võrdub midagi, võite lihtsalt tagasi, eks? Aga see, kes me oleme kõige huvitatud räägi on binaarse otsing, õige, mis on Jaga ja valitse mehhanism, mis David oli näidates loeng. 

Mäleta telefoniraamatust näiteks et ta hoiab kasvatamisel, üks, et ta mingi võitlesid natuke seda viimase aasta jooksul kus sa jagada probleem pooleks, pooleks, pooleks, ikka ja jälle, kuni leiad, mida otsite? Ja sul Runtime selle samuti. Ja näed, et see on oluliselt efektiivsemaks kui mis tahes muud liiki otsing. 

Nii nii, et me oleks minna rakendamise binaarne otsing on, kui meil oleks massiivi, indeks 0 kuni 6, seitse elemente, saame vaadata keskel, right-- kahju, kui meie küsimusele first-- Kui tahame küsida küsimus, kas massiiv sisaldab elementi 7, Ilmselt on inimestele ning võttes Sellise väikese hulga, see on lihtne meile öelda jah. Aga kuidas rakendada binaarne otsingu oleks otsida keskel. 

Me teame, et indeks 3 keskel, sest me tean, seal on seitse elementi. Mis 7 jagatuna 2? Võite tükelda ära, et ekstra 1. Sul on 3 keskel. Nii on massiiv 3 võrdub 7? See ei ole õige? Aga me saame teha paar kontrolli. Kas massiivi 3 kuni 7 või on rida 3 on suurem kui 7? 

Ja me teame, et see on vähem kui 7. Nii et me teame, et oh, see peab saa olla vasakul poolel. Me teame, et see peab olema õiges poole, eks? Nii saame lihtsalt karbonaad off pool massiivi. Me isegi ei pea vaadata seda enam. Kuna me teame, et pool meie problem-- me teame, et vastus on paremal pool meie probleem. Nii et me lihtsalt vaadata, et nüüd. 

Nüüd vaatame keskel, mida on jäänud. See indeks 5. Me teha sama uuesti kontrollida ja me näeme, et see on väiksem. Nii me vaatame vasakule, et. Ja siis me näeme, et kontrollida. Kas array väärtus indeks 4 võrdub 7? See on. Nii saame tagasi tõsi, sest leidsime väärtus meie nimekirjas. Kas nii, nagu ma läksin läbi mis mõtet kõigile? OKEI. Ma annan sulle poisid äkki, nagu, kolm, neli minutit, et aru saada, kuidas pseudokoodi seda. 

Seega kujutada Ma palusin sul kirjutada funktsiooni nimetatakse otsingumootori (), et tagasi väärtus, tõeväärtuse, see oli õige või false-- nagu, tõsi, kui olete leidnud väärtus, vale, kui sa seda ei teinud. Ja siis olid möödunud aastal väärtus, mida otsisid arvesse väärtusi, mis on array-- oh, ma kindlasti panna et vales kohas. OKEI. Niikuinii, et peaks olema olnud paremal väärtusi. Ja siis int n on number elementide, mis massiivi. Kuidas minna püüdnud to pseudokoodi et probleem? Ma annan sulle sinusuguseid kolm minutit teha. Ei, ma arvan, et seal on ainult-- Jah, seal on üks õige siin. Sihtrühm: Kas ma? ANDI PENG: Jah, ma sain sulle. Kas see töö? OK, lahe. 

OKEI. Olgu poisid, me oleme läheb rein seda. OKEI. Nii eeldame meil see armas vähe massiivi n väärtuste ta. Ma ei tõmmata jooned. Aga kuidas me minna üritan kirjutada seda? Kas keegi taha mulle esimene rida? Kui soovite mulle anda esimene rida selles pseudokoodi. 

Sihtrühm: [kuuldamatu] Sihtrühm: Sa tahad itereerima through-- Sihtrühm: Lihtsalt üks silmus? Sihtrühm: --for. 

ANDI PENG: Nii see on natuke keeruline. Mõtle about-- soovid hoida töötab see loop ikka ja jälle, kuni millal? 

Sihtrühm: Kuni [kuuldamatu] võrdub selle väärtus. ANDI PENG: Täpselt. Nii saab tegelikult lihtsalt write-- saame isegi lihtsustada seda rohkem. Me võime lihtsalt teha samas loop, eks? Nii saab lihtsalt loop-- me teame, et see on samas. Aga just nüüd, ma lähen öelda "loop" - kaudu, mis? Loop until-- mis on lõppev haigus? Ma arvan, et ma kuulsin seda. Ma kuulsin kedagi ütlemas seda. 

Sihtrühm: Väärtused võrdub keskel. ANDI PENG: Ütle seda uuesti. Sihtrühm: Või, kuni väärtus, mida te otsite on võrdne keskväärtusena. 

ANDI PENG: Mis siis, kui see ei ole seal? Mis siis, kui väärtus, mida te otsite on tegelikult ei selles massiivi? Sihtrühm: Sa tagasi 1. 

ANDI PENG: Aga mida me tahame loop kuni kui meil on tingimus? Jah. 

Sihtrühm: Kuni seal on ainult üks väärtus? ANDI PENG: Võite loop until--, et sa tead, et sa oled läheb on max väärtus, eks? Ja sa tead, et sa lähed min oleks väärtus, eks? Kuna ka, et midagi Ma unustasin öelda enne, et midagi, mis on kriitiline Kahendotsingupuu on see, et teie massiiv on juba järjestatud. Sest seal on kuidagi teed see, kui nad lihtsalt juhuslik väärtusi. Sa ei tea, kui üks on suurem kui teine, eks? 

Nii et sa tead, et su max ja Sinu minutit siin, eks? Kui sa lähed tuleb reguleerida Teie max sinu minutit ja mid-- olgem lihtsalt eeldada oma Keskmine väärtus on siin-- sa lähed põhimõtteliselt loop kuni oma miinimum umbes sama, mis sinu max, õigus, või Kui teie maks ei ole sama, mis sinu min. Õigus? Sest kui see juhtub, siis tea, et oled lõpuks tabas sama väärtusega. Nii et sa tahad loop, kuni teie min on väiksem või võrdne-- oops, mitte väiksem või võrdne, Teine võimalus lihtsalt ringi max. 

Kas see on mõtet? Võtsin paar üritab saada seda õigust. Aga loop kuni oma max väärtus on sisuliselt peaaegu vähem võrdne või oma minimaalne, eks? See, kui sa tead, et olete ühtlustunud. Sihtrühm: Millal peaks oma maksimaalse väärtus olla väiksem kui minimaalne? ANDI PENG: Kui hoiate kohandades seda, mis on see, mida me olla teeme seda. Kas see on mõtet? Minimaalne ja maksimaalne on vaid täisarvud, et oleme ilmselt lähed tahan luua hoida peal, kus me otsime. Kuna massiivi olemas sõltumata sellest, mida me teeme. Nagu, me ei ole tegelikult füüsiliselt hakkimispiirkond massiivi, eks? Me lihtsalt reguleerida kus me otsime. Kas see on mõtet? 

Sihtrühm: Jah. 

ANDI PENG: OK. Nii et kui see on eelduseks meie loop, Mida me tahame sees see loop? Mida me saame teha tahame? Nii kohe, meil max ja min, õigus, ilmselt loodud siin kusagil. Me läheme ilmselt tahad leida kompromiss, eks? Kuidas me saame olla võimalik leida keskel? Mis mathematical-- Sihtrühm: Max pluss min jagatud 2. ANDI PENG: Täpselt. Kas see on mõtet? Ja te poisid aru, miks me ei ole lihtsalt use-- miks me seda tegime selle asemel teeme lihtsalt n jagatud 2? See on sellepärast, et n on väärtus et läheb samaks. Õigus? Aga kui me kohandame oma minimaalse ja maksimaalseid väärtusi, nad ei kavatse muuta. Ja tulemus, meie keskel hakkab muutuma liiga. Nii et miks me tahame seda teha siin. OKEI. 

Ja siis, et nüüd, oleme leidnud our-- yeah. 

Sihtrühm: Lihtsalt kiire question-- kui sa ütled min ja max, me eeldades, et see on juba järjestatud? 

ANDI PENG: Jah, see on tegelikult eelduseks Kahendotsingupuu, et sa pead teadma, see on järjestatud. Mistõttu omamoodi, sa kirjutad oma Probleem panen oma binaarne otsing. OKEI. Nüüd, kui me teame, kus meie keskpunktis on, mida sa tahad teha siin? 

Sihtrühm: Me tahame võrrelda et teine. ANDI PENG: Täpselt. Nii et sa lähed võrrelda keskpaigast kuni väärtuses, eks? Ja mida ütleb see meid, kui me võrdleme? Mida me tahame teha hiljem? 

Sihtrühm: Kui väärtus on suurem kui keskel, tahame lõigata ära. ANDI PENG: Täpselt. Nii et kui väärtus on suurem kui keskel, me oleme tahame seda muuta need minimaalne ja maxes, eks? Mida me tahame muuta? Nii et kui me teame, väärtus on kuskil siin, mida sa meil muuta? Me tahame muuta meie minimaalne olema keskel, eks? Ja siis teine, kui see on antud poole, mida me tahame muuta? 

Sihtrühm: Teie maksimaalne. ANDI PENG: Jah. Ja siis sa oled lihtsalt läheb hoida silmukoiminen, eks? Sest nüüd pärast ühte iteratsiooni läbi, sul on max siin. Ja siis saab arvutada ümber keskel. Ja siis saad võrrelda. Ja sa lähed edasi minema kuni mins ja maxes on sisuliselt lähenesid. Ja see, kui sa tead, et olete tabanud lõpuni. Ja kas olete leidnud või sa ei ole sel hetkel. 

Kas see mõtet kõigile? OKEI. See on päris oluline, sest sa pead kirjutada seda koodi täna. Aga kutid on päris hea tunnet, mida sa peaks tegema, mis on hea. OKEI. Nii on meil umbes seitse minutit aega osa. Nii et me ei kavatse rääkida Selle pset, et me teeme. Nii pset jaguneb kaheks pooleks. Esimene pool hõlmab rakendades leida kus sa kirjutad lineaarne otsing, et Kahendotsingupuu ja sorteerimisalgoritm. 

Nii on see esimene korda pset, kus me olla annab teile poisid, mida nimetatakse jaotus kood, mis on koodi et me oleme eelnevalt kirjutatud, kuid just lahkunud mõned tükid ära teil lõpetada kirjalikult. Nii kutid, kui te vaatate seda koodi, võite saada väga hirmul. Kui sa oled lihtsalt meeldib, ahh, ma ei tea, mis see teeb, Ma ei tea, nagu, mis tundub nii keeruline, ahh, lõõgastuda. See on OK. Loe spec. Spec selgitab teile täpselt Mis need kõik teevad. 

Näiteks generate.c on programm et tulevad oma pset. Sa tegelikult ei pea seda puudutada, kuid sa peaksid mõistma, mida ta teeb. Ja generate.c, kõik see teeb on kas teeniva juhuslikud arvud või saate anda talle seemne, nagu jätavad arv, mis kulub, ja see tekitab rohkem numbreid. Nii et konkreetne võimalus rakendada generate.c kus võite lihtsalt hunnik numbreid kus saab testida oma muid meetodeid. 

Nii et kui sa tahad, et Näiteks testida oma leid, sa tahaksid joosta generate.c, luua hunnik numbreid, ja siis käivitada oma abilised funktsiooni. Sinu abilised funktsioon on koht, kus sa oled tegelikult füüsiliselt kirjutada koodi. Ja mõelda abilised nii raamatukogu faili sa oled kirjalikult, et leida helistab. Ja nii sees helpers.c, saate teha otsides ja sorteerimine. 

Ja siis sa lähed sisuliselt lihtsalt panna need kõik kokku. Spec ütleb teile, kuidas panna, et kui anda käsureal. Ja saate testida, kas või ei oma ja otsimise töötavad. Cool. Kas keegi on juba alanud ja tekkinud probleeme või küsimusi nad on just nüüd seda? OKEI. 

Sihtrühm: Oota. Mul on küsimus. 

ANDI PENG: Jah. 

Sihtrühm: Nii hakkasin teed lineaarse otsingule helpers.c ja see ei tööta päris. Aga hiljem sain teada, et me lihtsalt pea kustutama ja tegema Kahendotsingupuu. Nii on see oluline, kui see ei tööta? 

ANDI PENG: Lühike vastus on ei. Aga kuna me oleme Mitte-- Sihtrühm: Aga keegi ei tegelikult kontrollida. ANDI PENG: Oleme kunagi näeme, et. Aga sa ilmselt tahad teha Kindlasti otsingut töötab. Sest kui teie lineaarne otsing ei tööta, siis tõenäoliselt on teie binaarne Otsing ei kavatse töötada nii hästi. Kuna teil on sarnane loogikat neis mõlemas. Ja ei, see ei ole tegelikult küsimus. Nii et ainsad, saate sisse lülitada aastal on omamoodi ja binaarne otsing. Jah. 

Ja ka palju lapsi oli püüab koostada helpers.c. Sa tegelikult ei lubatud seda teha, sest helpers.c ei ole põhifunktsiooni. Ja et sa peaksid ainult olla tegelikult koostamine luua ja leida, sest leiavad kõned helpers.c ja funktsioone see. Nii et teeb silumine valu tagumik. Aga see, mida me peame tegema. Sihtrühm: Teed kõik, eks? ANDI PENG: Sa võid kõik hästi, jah. OKEI. Nii ongi selle järgi, mida pset küsib teile kõigile teha. Kui teil on küsimusi, tunnen tasuta küsi Pärast punkti. Ma tulen siia, nagu 20 minutit. 

Ja jah, siis pset on tõesti ei ole nii hull. Te peaks olema OK. Need, järgige juhiseid. Kind of on tunne, loogiliselt, mida tuleks juhtub ja siis saad trahvi. Ära ole liiga hirmul. Seal on palju koodi juba kirjutanud seal. Ära ole liiga hirmul, kui sa seda ei tee aru, mida see kõik tähendab. Kui see on palju, see on täiesti korras. Ja tulevad tööaega. Me aitame teil võtta pilk. 

Sihtrühm: Mis extra funktsioone, me vaatame neid üles? 

ANDI PENG: Jah, need on kood. Mängus on 15 poole see on juba kirjutatud teile. Nii et need funktsioonid on Juba koodi. Yep. Hästi. Noh, palju õnne. See on vastik päev. Loodetavasti kutid ei tunne liiga halba viibib sees ja kodeerimine.