[TÓNLIST spila] 

ANDI Peng: Velkomin í viku 3 af lið. Takk, strákar, fyrir allt að koma þessari fyrri byrjunartíma dag. Við höfum fengið gott, lítið náinn hópur í dag. Svo vonandi munum við fá til ljúka, kannski, snemma, svolítið snemma í dag. Svo fljótt, bara nokkrar afmælisdagur dagskrá í dag. Áður en við byrjum, við erum að fara að fara bara yfir nokkrar stuttar skipulagningar málefni, pset spurningar, debrief, svoleiðis. Og þá munum við kafa rétt í. Við munum nota aflúsara heitir GDB til byrja debunking kóða okkar, sem David útskýrði í fyrirlestri um daginn. Við munum fara yfir fjórum tegundum af konar. Við munum fara yfir þau ansi hratt þar sem þeir eru mjög ákafur. En veit að allar skyggnur og Kóðinn er alltaf á netinu. Svo ekki hika við, að sýn þinni til fara til baka og taka a líta á það. 

Við munum fara í gegnum asymptotic merki, sem er bara fínt leið að segja "runtimes," þar sem við höfum stóra O, sem David útskýrði í fyrirlestri. Og við höfum einnig Omega, sem er lægri bundinn afturkreistingur. Og við munum tala aðeins meira í-dýpt um hvernig þeir vinna. Og loks, munum við fara yfir tvöfaldur leit, vegna þess að mikið af ykkur sem hafa nú þegar leit á psets þínum sennilega vita að það er spurning sem er í pset þinn. Svo þú munt alla vera hamingjusamur að við ná þessu í dag. 

Og loks, á þínum kafla viðbrögð, ég reyndar á vinstri um 15 mínútur í enda að fara bara yfir flutningsgetu pset3, einhverjar spurningar, kannski smá leiðsögn, ef þú vilt, áður en við byrjum forritun. Svo skulum reyna að komast í gegnum efni ansi fljótt. Og þá getum við eyða einhverjum tíma taka fleiri spurningar fyrir pset. OK. 

Fljótt, svo bara nokkrar Tilkynningar Áður en við byrjum í dag. Í fyrsta lagi, velkomið að gera það í gegnum tvo psets þínum. Ég skoðaði á your-- já, við skulum fá umferð lófaklapp fyrir það eitt. Reyndar var ég í raun, mjög hrifinn. Ég farið fyrsta pset fyrir ykkur Síðustu viku og þið gerðu ótrúlegt. 

Style var á lið auk nokkurra athugasemda. Gakktu úr skugga um að þú ert alltaf athugasemdir kóðann þinn. En psets þínir voru á lið. Og halda henni upp. Og það er gott fyrir flokkara til sjá að þú krakkar eru að setja í eins mikið átak í stíl og hönnun í kóðanum þínum að við viljum að þú að sjá. Þannig að ég ætla liggur meðfram þakklæti mitt fyrir the hvíla af the Tas. 

Þó að það séu Nokkrum debrief spurningar Ég vil bara að fara yfir það myndi gera bæði líf mitt og mikið af öðrum TAS "lifir svolítið auðveldara. Í fyrsta lagi, ég hef tekið eftir þessu framhjá week-- hvernig margir af þú hafa verið í gangi check50 á númerið þitt áður en þú sendir? OK. Svo allir ættu að vera að gera check50, because-- a secret-- við í raun hlaupa check50 sem hluta af réttmæti okkar forskriftir fyrir prófanir númerið þitt. Þannig að ef númerið þitt er galli check50, að öllum líkindum, það er líklega að fara að ekki stöðva okkar eins og heilbrigður. Stundum þú krakkar hafa rétt svör. Eins og í gráðugur, sum þú hefur rétt númer, þú prentar bara út smá auka efni. Og að auka efni reyndar ekki að athuga, vegna þess að tölvan er ekki raunverulega vita hvað það er að leita að. Og svo það verður bara að keyra í gegnum, sjá að framleiðsla þinn styður ekki passa það sem við búast svarið að vera, og merkja það er rangt. 

Og ég veit að gerðist í sum tilvik þínum í þessari viku. Svo ég fór aftur og höndunum endurmetnar kóða allra. Í framtíðinni þó, vinsamlegast, vinsamlegast tryggja að þú ert að keyra athuga 50 á kóðann þinn. Vegna þess að það er góður af a sársauki fyrir TA að þurfa að fara til baka og höndunum regrade hvert einasta pset fyrir hvert einn, lítið ungfrú dæmi. Svo gerði ég ekki taka burt allir stig. Ég held að ég tók af kannski einn eða tveir fyrir hönnun. Í framtíðinni þó, ef þú ert galli check50, stig verða tekin burt fyrir misskilning. 

Ennfremur eru psets vegna föstudögum á hádegi. Ég held að það er sjö mínútna seint náð tímabil sem við gefum þér. Per Harvard tíma, þá eru þeir leyft að vera sjö mínútum of seint að öllu. Svo hér í Yale, munum við fylgja sem eins og heilbrigður. En ansi mikið á 12:07, ef pset er ekki í, það er að fara að vera merkt sem seint. Og svo á meðan það er merkt eins seint, TA-- ég enn að fara að vera yfirferð psets þína. Svo þú munt enn sjá einkunn birtast. Hins vegar veit að á í lok misseris, allt seint psets verður bara að vera sjálfkrafa núllstilltur af tölvunni. 

Við gerum þetta fyrir tveimur ástæðum. Einn, stundum fáum við afsakaði, eins afsakanir deildarforseta, síðar að ég veit ekki um enn. Þannig að við eins og til að tryggja að við erum að flokka allt bara í tilfelli, eins og ég er vantar afsökun Dean er. Og í öðru lagi, að halda í huga, þú getur samt taka einn pset að hefur fullt stig umfang. Og svo við eins og að einkunn öll psets þínum bara til að tryggja að svigrúm er þar og þú ert að reyna þá. Svo jafnvel ef það er of seint, þú munt enn fá kredit fyrir umfang stig, held ég. 

Svo boðskapur af the saga er, gera viss psets eru í þann tíma. Og ef þeir eru ekki í þann tíma, veit að það er ekki mikill. Já, áður en ég flyt á, er einhver með einhverjar spurningar varðandi pset viðbrögð? Já. 

Áhorfendur: Vissir þú að segja að við getur sleppt eitt af psets? 

ANDI Peng: Já. Svo er það níu psets heild á meðan á önn. Og ef þú hefur svigrúm points-- svo svigrúm er bara, ansi mikið, þú ert að reyna að vandamál, þú ert að setja í tíma, ert þú að sýna að þú hafir sýndi þú hefur lesið sérstakur. Það er ansi mikið svigrúm. Og ef þú ert að uppfylla umfang stig, við getur sleppt lægsta einn af fullt umfang. Svo er það í þína þágu til ljúka og reyna allar pset. 

Jafnvel upload-- ef ekkert þá vinna, hlaða þeim öllum. Og þá munum við vonandi geta gefa þér nokkra af þeim stig til baka. Cool. Aðrar spurningar? Great. 

Í öðru lagi, skrifstofa hours-- nokkrar Flýtileiðir athugasemdir um skrifstofutíma. Svo fyrst, koma snemma í vikunni. Enginn er alltaf í Viðtalstími á mánudögum. Christabel kom til Viðtalstími í gærkvöldi. Já, Christabel. Og hvað gerði við höfum á skrifstofu klst í gærkvöldi, Christabel? 

Áhorfendur: Við höfðum ís. 

ANDI Peng: Svo er það rétt, við höfðum ís á skrifstofutíma í gærkvöldi. Þó að ég get ekki lofað þér að við verðum ís á skrifstofutíma í hverri viku, það sem ég get lofað þér er að það verður verulega betra nemandi að TA hlutfall. Eins legit, það er eins og þremur til einn. En, á móti hafa Fimmtudagur, þú hefur fengið um 150 raunverulega áherslu börn og engan ís. Og það er bara ekki gefandi fyrir neinn. Svo Boðskapur sögunnar er, koma snemma að skrifstofutíma og góðum hlutum mun gerast. 

Einnig koma undirbúin til að spyrja spurninga. Þú veist? Óháð því hvað Tas, ég held, hafa verið að segja, við höfum verið að fá nokkra nemendur sem koma inn á fimmtudaginn í, eins og, 10:50 hafa ekki lesið sérstakur vera eins hjálpa mér, hjálpa mér. Því miður á þeim tímapunkti, það er ekki mikið sem við getum gert til að hjálpa þér. Svo vinsamlegast koma snemma í vikunni. Komdu snemma til skrifstofutíma. Koma undirbúin til að spyrja spurninga. Gakktu úr skugga um að þú, eins og nemandi, eru þar þú þarft að vera þannig að TAS geta leiða þig, sem er það sem viðtalstímar Ætti að vera úthlutað til. 

Í öðru lagi, þannig að ég veit prófessorar eins og til að koma okkur á óvart með prófunum. Ég átti prófessor slíkar eins, Yo, við the vegur, muna að miðannarverkefnið þú þarft næsta mánudag. Já, ég vissi ekki um að midterm. Þannig að ég ætla að vera að TA sem minnir þig allt sem quiz 0-- því, þú veist, við erum CS. Nú þegar við höfum gert fylki, þú færð hvers vegna það er quiz 0, ekki Quiz 1, ha? OK. Oh, ég fékk nokkrar chuckles á því einu. OK. 

Svo quiz 0 verður 14 október ef þú ert í Monday-miðvikudagur kafla og 15. október ef þú ert í Tuesday-Fimmtudagur kafla. Þetta á ekki við um þau ykkar í Harvard who-- Ég held að þú munt vera öll taka Skyndipróf þínum á 14.. 

Svo já, í næstu viku, ef David, í fyrirlestri, fer, já, svo um að quiz í næstu viku, þið öll mun ekki vera hneykslaður vegna þú komst við lið og þú veist að þinn quiz 0 er í tvær vikur. Og við munum hafa endurskoðun fundur og allt. Svo engar áhyggjur að vera hrædd um það. Einhverjar spurningar before-- einhverjar spurningar á öllum um skipulagningar málefni, flokkun, viðtalstímar, köflum? Já. 

Áhorfendur: Svo quiz er að fara að vera á fyrirlestri? 

ANDI Peng: Já. Svo spurningakeppni, held ég, er 60 mínútur veittir í þessu tímabili að þú munt bara að taka í fyrirlestrarsal. Svo þú þarft ekki að koma í á, eins og af handahófi 7:00 PM. Það er allt gott. Já. Cool. 

Allt í lagi. Þannig að við erum að fara að kynna hugmyndina að þér í þessari viku, að Davíð hefur nú þegar góður af snert á í fyrirlestri í síðustu viku. Það heitir GDB. Og hversu margir af þú, en í að sjálfsögðu að skrifa psets þína, hafa tekið eftir stór hnappur sem segir "Debug" efst á IDE þinn? OK. Svo nú munum við í raun að fá að unearth leyndardómur hvað það hnappur raun gerir. Og ég tryggt að þú, það er fallegur, fallegur hlutur. 

Svo allt þar til nú, held ég það er verið tvennt nemendur hafa verið oftast gera þegar kembiforrit psets. Einn, bæta þeir annaðhvort í printf () - svo á nokkurra línur, þeir bæta í printf () - ó, hvað er þessi breyta? Oh, hvað er þessi breyta now-- og þú sérð konar framvindu af kóðanum þínum eins og það liggur. Eða second aðferð krakkarnir gera er sem þeir skrifa bara allt hlutur og þá fara svona í lokin. Vonandi virkar það. Ég tryggja þér, GDB er betra en báðum þessum aðferðum. Já. Þannig að þetta verður nýr besti vinur þinn. Vegna þess að það er a fallegur hlutur sem sjónrænt sýna bæði hvað númerið þitt er að gera á tilteknum stað og hvað allt þitt breytur eru vopnaður, eins og það gildi þeirra eru, á þeim tilteknum stað. Og á þennan hátt, getur þú í raun setja Rofstaðir í kóðann þinn. Þú getur keyrt í gegnum línu fyrir línu. Og GDB verður bara að hafa fyrir þú, birt fyrir þig, hvað allt breytur þínar eru, hvað þeir eru að gera, hvað er að gerast í kóðanum. Og á þann hátt, að það er svo miklu auðveldara að sjá hvað er að gerast í stað þess að printf-ing eða skrifa niður yfirlýsingar. 

Þannig að við munum gera dæmi um þetta síðar. Svo virðist þetta dálítið ágrip. Engar áhyggjur, við munum gera dæmi. Og svo í raun, þau þrjú stærstu mest notaður aðgerðir sem þú þarft í gdb eru Next, stíga yfir, og stíga inn hnappa. Ég ætla að fara yfir það, í raun, núna. 

Svo getur þú krakkar allt sjá að eða ætti ég að stækka smá? Í bak, getur þú séð það? Ætti ég stækka? Bara svolítið? OK, flott. Það sem við förum. OK. 

Þannig að ég hef hér, minn framkvæmd fyrir gráðugur. Og á meðan mikið af ykkur skrifaði gráðugur í while lykkju form-- að er fullkomlega ásættanlegt leið til að gera it-- aðra leið til að gera það er að einfaldlega skipta í mátað. Því þá er hægt að hafa þinn gildi og þá hafa afganginn þinn. Og þá getur þú bara bæta það allt saman. Er röksemdafærsla sem ég er að gera hér skynsamleg fyrir alla, áður en við byrjum? Eiginlega? Cool. Great. Það er ansi kynþokkafullur stykki af kóða, myndi ég segja. Eins og ég sagði, David, í fyrirlestur, eftir smá stund, þú munt alla byrja að sjá kóða sem eitthvað sem er fallegt. Og stundum þegar þú sérð fallegt númer, það er svo dásamleg tilfinning. 

Svo þó, meðan þetta númer er mjög falleg, er það ekki vinna almennilega. Svo skulum hlaupa check50 á þetta. Athugaðu 50 20-- OOP. 2? Er það pset2? Já. Oh, pset1. OK. Svo við hlaupum check50. 

Og eins og þú krakkar geta sjá hér, það er galli nokkra tilvikum. Og fyrir sumir af þú, í Auðvitað á að gera vandamál setur þína, þú ert eins og, Ah, hvers vegna er það ekki að virka. Hvers vegna er það að vinna fyrir sumir gildi en ekki fyrir aðra? Jæja, GDB er að fara að hjálpa þér að reikna út hvers vegna þessir inntak voru ekki að virka. 

OK. Svo skulum sjá, einn af eftirlit ég var galli í check50 var inntak gildi 0.41. Svo rétt svar sem þú ættir að vera að fá er 4. En í staðinn það sem ég er að prenta út er 3-N, þar sem er ekki rétt. Svo skulum hlaupa bara þetta með höndunum, bara ganga úr skugga um að check50 er að vinna. Gerum ./greedy. Oops, ég verð að gera gráðugur. Það sem við förum. Nú ./greedy. 

Hversu mikið er skuldaði? Gerum 0,41. Og Já, sjáum við hér að það er outputting 3 þegar rétt svar, í raun ætti að vera 4. Svo skulum slá GDB og sjá hvernig við getur farið um að ákveða þetta vandamál. 

Svo fyrsta skrefið í alltaf kembiforrit kóða er að setja breakpoint, eða benda á sem þú vilt tölvuna eða aflúsara að byrja að horfa á. Svo ef þú ert ekki í raun vita hvað vandamálið er, yfirleitt, dæmigerður hlutur sem við viljum gera er að setja breakpoint okkar á main. Svo ef þú krakkar geta séð þetta rauður hnappur þarna, Já, það var mér að setja a breakpoint fyrir the aðalæð virka. Ég smelli sem. 

Og þá get ég farið upp í Kemba hnappinn minn. Ég lenti þessi hnappur. Leyfðu mér að súmma út aftur ef ég get. Það sem við förum. Þannig að við höfum, hér, a pallborð á hægri. Fyrirgefðu, krakkar í bak, þú geta í raun ekki séð mjög vel. En í raun, allt þessi réttur spjaldið er að gera er að halda utan um bæði lögð áhersla lína, sem er lína af kóða að tölvan er í gangi, eins og allar breytur þínar niður hér. 

Svo þú hefur fengið sent, mynt, n, allt sagt mismunandi hluti á þessu stigi. Engar áhyggjur, vegna þess að við höfum í raun ekki frumstilla þá til hvaða breytur enn. Svo í tölvunni, þinn tölva er bara að sjá, ó, 32767 var síðast notaður virka þess minni pláss í tölvunni minni. Og svo er það þar sent nú er. En engin að þegar þú keyrir kóðann, það ætti að verða forsniðin. 

Svo skulum við fara í gegnum, línu lína, hvað er að gerast hér. OK. Svo hér eru þrír hnappar sem ég útskýrði bara. Þú ert að spila, eða Run virka, hnappinn, hefur þú stíga yfir hnappinn, og þú ert líka Skref í hnappinn. Og í raun, allir þrír af þá fara bara í gegnum kóðann þinn og gera mismunandi hluti. 

Svo yfirleitt, þegar þú ert kembiforrit, við viljum ekki bara högg spila, því Spila mun bara hlaupa númerið þitt til að í lok þess. Og þá munt þú í raun ekki vita hvað vandamálið er nema þú setja margar rofstaði. Ef þú stillir margar Rofstaðir, það verður bara sjálfkrafa hlaupa frá einum breakpoint, til annars, til the næstur. En í þessu tilfelli erum við höfum bara að ein, vegna þess að við langar að vinna okkur frá toppi niður í botn. Þannig að við erum að fara að hunsa þessi hnappur núna vegna þessarar áætlunar. 

Þannig að stíga yfir virka bara skref á hverjum einasta lína og segir þér hvað tölvan er að gera. The Skref í aðgerð fer í raun virka það er á línu af kóða. Svo til dæmis, eins og printf (), sem er fall, ekki satt? Ef ég vildi að líkamlega skref í printf () virka, Ég myndi reyndar fara í stykki af Póstnúmer þar printf () var skrifað og sjá hvað er að gerast þar. 

En yfirleitt, gerum við ráð fyrir kóðinn sem við gefum þér virkar. Við gerum ráð fyrir að printf () er að vinna. Við gerum ráð fyrir að GetInt () er að vinna. Þannig að það er engin þörf á að stíga inn í þeim störfum. En ef það er aðgerðir sem þú skrifar sjálfur sem þú vilt að athuga hvað er að gerast, þú vilt að stíga inn í þessi virka. 

Svo núna erum við bara að fara að stíga yfir þessu stykki af kóða. Svo skulum sjá. Oh, prenta, "ó Hai, hvernig miklar breytingar er skuldaði? " Við sama. Við vitum að er að vinna, svo við stíga yfir það. 

Svo n, sem er fljóta okkar sem við höfum initialized-- eða declared-- upp á toppinn, við erum nú jafna sem að GetFloat (). Svo skulum stíga yfir það. Og við sjáum í því botn hér, the program er vekur mig til inntak gildi. Svo skulum inntak gildi sem við viljum til að prófa hér, sem er 0,41. Great. 

Svo nú n- gera þú krakkar sjá Hér á bottom-- það er stored-- vegna þess að við hefur ekki ávalar enn, það er geymd í þessum eins risastór fljóta sem er ,4099999996, sem er nógu nálægt til okkar tilgangi, núna, að 0.41. Og þá munum við sjá síðar, eins og við áfram stepping yfir áætlun, eftir hér, n hefur orðið hringlaga og sent hefur orðið 41. Great. Þannig að við vitum að vinna námundun okkar. Við vitum að við höfum réttan fjölda sent, þannig að við vitum að það er í raun ekki vandamálið. 

Svo við höldum áfram stepping á í þessari áætlun. Við förum hér. Og svo eftir þessari línu af kóða, við ætti að vita hversu margir fjórðu við höfum. Við stíga yfir. Og þú sérð að við, í raun, að hafa einn fjórðungur af því að við höfum dregið 25 frá upphafsgildi okkar 41. Og við höfum 16 vinstri sent okkar. 

Þurfa allir að skilja hvernig forritið er stepping gegnum og hvers vegna sent hefur nú orðið 16 og hvers vegna, nú, mynt hefur orðið 1? Er allir eftir að rökfræði? Cool. Svo eins og með þessum tímapunkti, vinna forritsins, ekki satt? Við vitum að það er að gera nákvæmlega það sem við viljum það til. Og við gerðum í raun ekki að prenta út, ó, hvað er sent á þessum tímapunkti, hvað er mynt á þessum tímapunkti. 

Við höldum áfram að fara í gegnum kerfið. Stíga yfir. Cool. Við förum yfir dimes. Great. Við sjáum að það er tekið burt $ 0,10 fyrir a dime. Og nú höfum við tvær mynt. Það er rétt. 

Við förum yfir smáaurarnir og við sjáum sem við höfum fengið afgangs sent. Hmm, það er undarlegt. Upp hér á dagskrá, ég átti hafa dregið smáaurarnir mína. Kannski var ég bara ekki gera þessi lína rétt. Og því miður, getur þú séð hér, vegna þess að við vitum að við erum stepping í gegnum línur 32 og 33, það er þar sem áætlun okkar illa hafði breytur hlaupa. Svo við getum líta og sjá, ó, Ég er að draga sent hér, en ég er í raun ekki bæta við peningi gildi minn. Ég ætla að bæta við sent. Og ég vil ekki að bæta við sent, ég vil bæta við mynt. Þannig að ef við breyta því að mynt, við höfum fengið starfsáætlun. Ég get keyrt check50. Þú getur bara að hætta í GDB hægri hér og þá hlaupa check50 aftur. Ég gæti bara gert þetta. Ég verð að gera gráðugur. 0,41. Og hér er það prentun út rétt svar. 

Svo eins og þú krakkar geta sjá, GDB er mjög öflugt tæki þegar við höfum svo mikið númer að fara á og svo margir breytur að það er erfitt fyrir okkur, sem manna, að halda utan um. The tölva í gdb aflúsara, hefur getu til að halda utan um allt. Ég veit, í Visionaire, strákar líklega gæti hafa högg sumir markhópa galla vegna þess að þú varst að keyra út af mörk array þinn. Í dæminu um keisarans, sem er nákvæmlega það sem ég hef innleitt hér. 

Svo ég gleymdi að athuga hvað myndi gerast ef ég ekki hafa tvær viðföng. Ég bara vissi ekki að setja í þá skefjum. Og svo ef ég hlaupa Debug-- ég setti rofstaður mín að rétt þar. Ég keyrt Debug. 

OK. Já. Svo í raun, GDB átti að hafa sagt mér það var skiptingu kenna það. Ég veit ekki hvað var í gangi þarna, en þegar ég hljóp það, það var að vinna. Þegar þú keyrir línur af kóða gegnum og GDB gæti bara skyndilega hætta á þig, fara upp og skoða hvað rauða villa er. Það mun segja þér, hey, þú hafði skiptingu kenna, sem þýðir að þú reyndir að opna pláss í array sem eru ekki til staðar. Já. 

Svo í næsta vandamál setja í þessari viku, þú krakkar mun líklega hafa a einhver fjöldi af breytur fljótandi í kring. Þú ert ekki að fara að vera viss um hvað þeir meina á ákveðnum stað. Svo GDB mun virkilega hjálpa þér í vangaveltur hvað þeir eru allir jafngildir og vera fær um að sjá að sjónrænt. Er einhver rugla um hvernig einhverju sem var að vinna? Cool. Allt í lagi. Svo eftir það, við erum að fara að kafa rétt inn eru fjórar mismunandi tegundir konar fyrir þessa viku. Hversu margir af þú, fyrst af öllu, áður en við byrjum, hafa lesið alla sérstakur fyrir pset3? OK. Ég er stoltur af ykkur. Það er eins og helmingur af bekknum, sem er mun meiri en í síðasta sinn. 

Svo er það mikill, vegna þess að þegar við tölum um innihald í lecture-- eða hryggur, í section-- Mér finnst að tengja mikið af því aftur til hvað pset er og hvernig þú vilt að framkvæma það í pset þinn. Svo ef þú kemur með lesa sérstakur, verður það vera mun auðveldara fyrir þig að skilja hvað ég er að tala um þegar ég segi, ó hey, þetta gæti verið mjög góður staður til að framkvæma þessa tegund. Svo þeir sem hafa lesið Sérstakur veit að sem hluti af pset þinn, þú ert að fara að þurfa að skrifa tegund tagi. Þannig að þetta getur verið mjög gagnlegt fyrir mikið af þér í dag. 

Þannig að við munum byrjun burt við, í raun, the einfaldur tegund af tegund, val tegund. The dæmigerður reiknirit fyrir hvernig við myndum fara um þetta is-- David fór í gegnum þetta allt í fyrirlestur, svo ég ætla að fara hratt eftir here-- er í raun, þú hafa fjölbreytta gildi. Og þá þú finnur Minnsta Óflokkaður gildi og þú skipta þessi gildi með fyrsta Óflokkaður gildi. Og þá er að halda bara að endurtaka með the hvíla af listanum þínum. 

Og hér er sjón skýring um hvernig það myndi vinna. Svo til dæmis, ef við vorum að byrja með fjölda fimm þætti, vísitölu 0 til 4, með 3, 5, 2, 6, og 4 gildi sett í array-- svo núna, við erum bara að fara að gera ráð að þeir eru allir Óflokkaður vegna þess að við höfum ekki prófað annað. 

Svo hvernig úrval konar myndi vinna er að það myndi fyrst hlaupa í gegnum heild af óflokkaðs fylkisins. Það myndi ná fram lægsta gildi. Í þessu tilfelli, 3, rétt nú, er minnsti. Það fær til 5. Nei, 5 er ekki meiri than-- eða leitt, er ekki minna than-- 3. Svo er enn 3 lágmarks gildi. Og þá færðu 2. Tölvan sér, ó, 2 er minna en 3. 2 verður nú að vera lágmarks gildi. Og svo 2 skiptasamninga með því fyrsta gildi. 

Svo eftir einni yfirferð, við sjáum örugglega að 2 og 3 eru skipti. Og við erum bara að fara að halda áfram að gera þetta aftur með the hvíla af the array. Þannig að við erum að fara að bara hlaupa í gegnum síðustu fjórar Vísitölur fylkisins. Við munum sjá að 3 er næsta lágmarks gildi. Þannig að við erum að fara að skipta því með 4. Og þá erum við bara að fara að halda gangi í gegnum þar til að lokum, þú fá að raðaða array sem 2, 3, 4, 5, og 6 eru allir flokkuð. Þurfa allir að skilja rökfræði um hvernig val konar virkar? 

Þú verður bara einhvers konar af lágmarksgildi. Þú ert að halda utan um hvað sem er. Og þegar þú finnur það, skipta þér það með fyrsta gildi í array-- eða, ekki í fyrsta value-- næsta stak fylkisins. Cool. 

Svo eins og þið konar sá frá stuttri innsýn, við erum að fara að sauðakóðanum þetta út. Svo ef þið á bak vilt mynda hóp, allir í töflu getur myndað smá félagi, ég ætla að gefa ykkur eins þrjár mínútur að bara tala um röksemdafærsla, á ensku, um hvernig við gætum vera fær um að framkvæma sauðakóðanum að skrifa val konar. Og það er nammi. Vinsamlegast komið upp og fá nammi. Ef þú ert í bak og þú vilt nammi, get ég kasta nammi á þig. Reyndar gera you-- kaldur. Ó fyrirgefðu. OK. 

Þannig að ef við viljum, eins og flokki, skrifa sauðakóðanum fyrir hvernig við gætum nálgast þetta vandamál, bara ekki hika. Ég ætla bara að fara í kring og í því skyni, að spyrja hópa fyrir næstu línu hvað við ættum að gera. Svo ef þú krakkar vilja til að byrja burt, hvað er það fyrsta sem að gera þegar þú ert að reyna að innleiða leið til að leysa þetta forrit að vali raða lista? Við skulum bara gera ráð vér hafa array, allt í lagi? 

Áhorfendur: Þú vilt að búa til sumir konar [inaudible] að þú ert gangi í gegnum allt array þinn. 

ANDI Peng: Hægri. Svo þú ert að fara að vilja til að árétta í gegnum alla rúm, ekki satt? Svo, frábært. Ef þú krakkar vilja til að gefa mér sem næsta line-- já, í bakinu. 

Áhorfendur: Stöðva þá allt fyrir minnstu. 

ANDI Peng: Það sem við förum. Þannig að við viljum fara í gegnum og athugaðu sjá hvað er lægsta gildið, ekki satt? Ég ætla að skammstafa það að "mín". Hvað þú krakkar vilja til að gera eftir þú hefur fundið lágmarks gildi? 

Áhorfendur: [inaudible] ANDI Peng: Svo þú ert að fara til að vilja skipta um það með fyrsta því fylki, ekki satt? Það er byrjunin, ég ætla að segja. Allt í lagi. Svo nú að þú hafir skipti fyrst einn, hvað þú vilt gera eftir það? Svo nú vitum við að þetta hér verður að vera minnsti gildi, ekki satt? Síðan sem þú ert með fleiri hvíld fylkisins sem er Óflokkaður. Það sem þú vilt að gera hér, ef þú krakkar vilja til að gefa mér næstu línu? Áhorfendur: Svo þá þú vilt að árétta í gegnum restina af fylkisins. ANDI Peng: Já. Og svo hvað er iterating gegnum konar skyn að við munum líklega þurfa? Hvaða tegund of-- 

Áhorfendur: Oh, til viðbótar breyta? ANDI Peng: Sennilega annar fyrir lykkju, ekki satt? Þannig að við erum líklega að fara að vilja að iterate through-- mikill. Og þá þú ert að fara að fara aftur og sennilega athuga lágmarki aftur, ekki satt? Og þú ert að fara að halda að endurtaka þetta, því lykkjur bara að fara að halda í gangi, ekki satt? 

Svo eins og þú krakkar geta sjá, við bara almennt sauðakóðanum um hvernig við viljum þetta forrit til að líta. Þetta kunnugt hér, hvað við þarf yfirleitt að skrifa í númerið okkar ef við viljum árétta gegnum array, hvaða tegund af uppbyggingu? Ég held Christabel þegar sagt þetta áður. 

Áhorfendur: A til hliðar. 

ANDI Peng: A fyrir lykkju? Nákvæmlega. Svo er þetta líklega að fara að vera til hliðar. Hvað er ávísun hér að fara að kynna? Venjulega, ef þú vilt að athuga ef eitthvað er eitthvað else-- 

Áhorfendur: Ef. 

ANDI Peng: An ef, ekki satt? Og þá skipti hér, við munum fara yfir seinna, því Davíð fór í gegnum það í fyrirlestri eins og heilbrigður. Og þá seinni árétta implies-- 

Áhorfendur: Annar fyrir lykkju. 

ANDI Peng: --another fyrir lykkju, nákvæmlega. Þannig að ef við erum að leita á þetta rétt, við er hægt að sjá að við erum líklega að fara að þurfa a hreiður fyrir lykkju skilyrt yfirlýsingu í það og þá er í raun stykki af kóða fara að skipta gildin. Þannig að ég hef bara almennt skrifað a sauðakóðanum kóða hér. Og þá erum við í raun að fara að líkamlega, sem tegund, reyna að innleiða þetta í dag. Við skulum fara aftur inn í þennan IDE. 

Uh-ó. Hvers vegna er það not-- það sem það er. OK. Því miður, láta mig reyna að stækka aðeins meira. Það sem við förum. Allt sem ég er að gera hér er að ég hef búið forrit sem heitir "Val / sort.c." Ég hef búið á fjölbreytta níu gildi, 4, 8, 2, 1, 6, 9, 7, 5, 3. Eins og er, eins og þú getur sjá, þeir eru óraðaða. n er að fara að vera númer sem segir þér hversu mikið af gildum þú þarft fylktu þinn. Í þessu tilviki, hafa níu gildi. Og ég hef bara fyrir lykkju hér sem prentar út óflokkuðu fylkisins. 

Og í lokin, ég hef líka fengið fyrir lykkja sem bara prentar það út aftur. Svo fræðilega, ef þetta forrit er að vinna rétt, í lok, þú ættir að sjá prentað fyrir lykkju þar sem 1, 2, 3, 4, 5, 6, 7, 8, 9 eru rétt svo. 

Þannig að við höfum fengið sauðakóðanum okkar hér. Er einhver að vilja to-- Ég er bara að fara að fara að biðja um volunteers-- segðu mér nákvæmlega hvað ég á að slá ef við viljum að í fyrsta lagi bara árétta í gegnum í byrjun þessa array? Hvað er lína af kóða er ég líklega að fara að þurfa hér? 

Áhorfendur: [inaudible] 

ANDI Peng: Já, finnst frjáls to-- Því miður, þú þurfa ekki að standa tilfinningu up-- frjáls til að hækka rödd þína aðeins. 

Áhorfendur: Fyrir int i jafngildir 0-- 

ANDI Peng: Já, gott. 

Áhorfendur: i er minna en array lengd. 

ANDI Peng: Svo hafa í huga hér, vegna þess að við hafa ekki virka sem segir okkur að lengd af fjölda, Við höfum nú þegar gildi sem geymir það. Ekki satt? Annar hlutur til viðurværi í mind-- í fylki níu gildi, hvað eru vísitölur? Við skulum bara segja þetta array var 0 til 3. Þú sérð að síðasta Vísitala er í raun 3. Það er ekki 4, jafnvel þó að það er fjögur gildi í fylkinu. 

Svo hér, verðum við að vera mjög varkár af hvaða ástandi okkar fyrir lengd er að fara til vera. 

Áhorfendur: Væri ekki n mínus 1? ANDI Peng: Það er að fara n mínus 1, nákvæmlega. Er að skynsamleg, hvers vegna það er n mínus 1, allir? Það er vegna þess að fylki eru núll-verðtryggð. Þeir byrja á 0 og hlaupa upp til n mínus 1. Já, það er dálítið erfiður. OK. Og svo-- Áhorfendur: Isnt'1 að þegar gætt af þó, bara með því að ekki að segja "minna en eða jafn "og bara að segja" minna en? " 

ANDI Peng: Það er mjög góð spurning. Svo, já. En einnig, á þann hátt að við erum framkvæmd stöðva rétt, þú þarft að bera saman tvö gildi. Svo þú vilt í raun að yfirgefa "til" tóm. Því ef þú bera saman þetta, þú ert ekki að fara hafa neitt eftir það til að bera saman, ekki satt? Já. Svo ég ++. Við skulum bæta sviga okkar í. Úpps. Great. Þannig að við höfum upphaf ytri lykkju okkar. Svo nú erum við sennilega vilja til búa til breytu fyrir því að halda utan um minnstu gildi, ekki satt? Er einhver vilja til að gefa mér sem lína af kóða sem myndi gera það? Hvað þurfum við að ef við erum að fara að vilja geyma eitthvað? 

Hægri. Kannski betra nafn fyrir að myndi be-- "afleysingamanneskja" algerlega works-- kannski meira viðeigandi nefnd væri, ef við viljum minnstu value-- 

Áhorfendur: Min. ANDI Peng: mín, það sem við förum. mín væri gott. Og svo hér, hvað gerum við langar að frumstilla hana til? Þetta er dálítið erfiður. Vegna þess að núna á að upphaf þessu fylki, þú hefur ekki horft á neitt, ekki satt? Svo hvað, sjálfkrafa, ef við erum bara á ég jafngildir 0, hvað viljum við frumstilla Fyrsta lágmarks gildi okkar til? Áhorfendur: i. ANDI Peng: i, einmitt. Christabel, af hverju við viljum að frumstilla hana til i? 

Áhorfendur: Vegna þess, vel, við erum að byrja með 0. Svo vegna þess að við höfum ekkert að bera saman það að, lágmarks mun á endanum vera 0. 

ANDI Peng: Einmitt. Svo er hún einmitt rétt. Þar sem við höfum ekki í raun horfði á neitt ennþá, við vitum ekki hvað lágmark gildi okkar er. Við viljum bara frumstilla hana til i, sem nú, er hérna. Og við höldum áfram að færa niður þetta fylki, við munum sjá að, með hverjum viðbótar framhjá, ég þrepum. Og svo á þeim tímapunkti, Ég er líklega að fara að vilja vera lágmark, vegna þess að það er að fara að vera hvað sem er upphaf óflokkaðs fylkisins. Cool. 

Svo nú viljum við að bæta fyrir lykkju hér það er fara að iterate gegnum Óflokkaður, eða restin af þessu fylki. Er einhver vilja til að gefa mér lína af kóða sem myndi gera það? Hint-- hvað við þurfum hérna? Hvað er að fara að fara í þetta fyrir lykkju? Já. Áhorfendur: Svo við myndum vilja að hafa mismunandi heiltala, vegna þess að við erum að keyra í gegnum the hvíla fylkisins í stað i, svo kannski j. 

ANDI Peng: Já, J hljómar vel við mig. Jafnt? 

Áhorfendur: Svo væri i plús 1, vegna þess að þú ert að byrja á næsta gildi. Og síðan til end-- svo aftur, j er minna en n mínus 1, og þá j ++. ANDI Peng: Great. 

Og þá í hér, við erum að fara til að vilja að athuga hvort ástand okkar er fullnægt, ekki satt? Þar sem þú vilt breyta lágmarks gildi ef það er í raun minni en það þú ert að bera saman það til, ekki satt? Svo hvað erum við að fara til að vilja hér? Athugaðu að sjá. Hvaða tegund af yfirlýsingu við erum að fara líklega TI vilt nota ef við vilja til að athuga eitthvað? 

Áhorfendur: An ef yfirlýsingu. 

ANDI Peng: An ef staðhæfing. Svo if-- og hvað er að fara að vera ástand sem við viljum inni if yfirlýsingu okkar? 

Áhorfendur: Ef verðmæti j er minna en verðmæti i-- 

ANDI Peng: Einmitt. Svo if-- svo þetta array er kallað "array". Great. Svo ef array-- hvað var það? Segja þetta aftur. 

Áhorfendur: Ef array-J er minni en array-i, þá myndum við breyta min. Svo mín væri j. 

ANDI Peng: Er að skynsamleg? OK. Og nú hérna, reyndar við vilja til að framkvæma skipti, ekki satt? Svo muna, í fyrirlestri, sem David, þegar hann var að reyna að skipta the-- það var it-- appelsínusafa og milk-- 

Áhorfendur: Það var brúttó. 

ANDI Peng: Já, það var eins konar brúttó. En það var nokkuð góð Hugmyndin sýna tíma. Svo hugsa um gildum hér. Þú hefur fengið fjölda af mín, fylki af i, eða hvað við vorum að reyna að skipta hér. Og þú sennilega getur ekki hella þeim í hver öðrum á sama tíma, ekki satt? Svo hvað erum við að fara að þurfa að búa hér í því skyni að skipta um gildi rétt? 

Áhorfendur: Tímabundið breyta. 

ANDI Peng: Tímabundið breyta. Svo skulum gera Int afleysingamanneskja. Sjá, þetta myndi vera betri tími to-- whoa, hvað var það? OK. Þannig að þetta hefði verið betra kominn tími til að nefna breyta "afleysingamanneskja." Svo skulum gera Int afleysingamanneskja. Hvað erum við að fara að setja afleysingamanneskja jafnt hér? Áhorfendur: Min? ANDI Peng: Það er dálítið erfiður. Það í raun skiptir ekki máli í lokin. Það skiptir ekki máli hvað röð þú velur að skipta í svo lengi sem þú ert að gera viss um að þú ert halda utan um hvað þú ert að skipta. 

Áhorfendur: Það gæti verið array-i. 

ANDI Peng: Já, við skulum gera array-i. Og þá er það næsta lína af kóða við viljum hafa hér? Áhorfendur: array-i jafn array-j. ANDI Peng: Og loks? Áhorfendur: array j jafnt array-i. Áhorfendur: Eða array-j jafngildir array-temp-- eða afleysingamanneskja. 

ANDI Peng: OK. Svo skulum hlaupa þetta og sjá ef það er að fara að vinna. Hvar er þetta að gerast? Oh, það er vandamál. Sjá, á línu 40, við erum reyna að nota array-j? En þar er J aðeins til í? 

Áhorfendur: Í for lykkju. ANDI Peng: Hægri. Svo hvað erum við að fara að þurfa að gera? 

Áhorfendur: Skilgreina það úti the-- Áhorfendur: Já, held ég að þú hefur að nota annað hvort yfirlýsingu, ekki satt? Svo eins, ef minimum-- allt í lagi, láta mig hugsa. 

ANDI Peng: Krakkar, reyna að kíkja Skulum sjá, hvað er eitthvað sem við getum gert hér? 

Áhorfendur: OK. Svo ef lágmarks ekki jafn j-- svo ef lágmarks er enn i-- þá myndum við ekki að skipta. 

ANDI Peng: Er að jafna ég? Hvað viltu segja hér? 

Áhorfendur: Eða já, ef Lágmarks ekki jafn i, já. ANDI Peng: OK. Jæja sem leysa, eins konar, vandamál okkar. En það er ekki enn leysa Vandamálið hvað gerist ef j-- síðan j er ekki til utan um það, hvað þú við viljum gera við það? Lýsa það utan? Við skulum reyna að keyra þetta. Uh-ó. Tegund okkar er ekki að virka. 

Eins og þú geta sjá, Byrjunar okkar array hafði þá gildi. Og síðan ætti að hafa verið í 1, 2, 3, 4, 5, 6, 7, 8, 9. Það er ekki að virka. Ahh. Hvað gerum við? Áhorfendur: Debug. ANDI Peng: Allt í lagi, við getum reynt það. Við getum kemba. Súmma út a hluti. Skulum setja mörk okkar. Við skulum fara like-- lagi. 

Svo vegna þess að við vitum nú þegar að þessar línur, 15 gegnum 22, eru working-- því allt sem ég er að gera er bara iterating gegnum og printing-- Ég get farið á undan og sleppa því. Við skulum byrja á línu 25. OOP, láttu mig fá losa af það. 

Áhorfendur: Svo rofstaður er þar sem kembiforrit byrjar? ANDI Peng: Eða hættir. Áhorfendur: Eða hættir. ANDI Peng: Já. Þú getur sett margar Rofstaðir og það getur bara hoppað úr einu í annað. En í þessu tilfelli erum við vitum ekki þar sem villa er að gerast. Þannig að við viljum bara að byrja frá toppi og niður. Jebb. OK. 

Þannig að fyrirsögnin hér, getum við stíga í. Þú getur séð hérna, við höfum fengið fjölda. Þeir eru gildi sem eru í fylki. Sérðu það, hvernig vísitalan 0, það svarar til value-- ó, Ég ætla að reyna að stækka. Því miður, það er mjög erfitt að see-- á array vísitölu 0 við höfum gildi 4 og þá svo framvegis og svo framvegis. Við höfum staðværar breytur okkar. Núna er ég jafn 0, sem við viljum það til að vera. 

Og svo skulum halda stepping gegnum. Lágmark okkar er jafnt og 0, sem við viljum líka það að vera. Og þá erum við að slá inn annað okkar fyrir lykkja, ef array-J er minni en array-I, sem það var ekki. Svo sástu hvernig að skipstjóri yfir það? 

Áhorfendur: Svo ætti ef Lágmarks, allt that-- ætti ekki að vera inni fyrst fyrir lykkju? ANDI Peng: Nei, vegna þess að þú vilt samt að prófa. Þú vilt gera samanburð á hverjum tími, jafnvel eftir að þú keyrir í gegnum það. Þú ert ekki bara að gera það á fyrstu umferð í gegnum. Þú vilt gera það með hvert viðbótar framhjá aftur. Svo þú vilt að athuga í ástand þitt inni. Þannig að við erum bara að fara að halda í gangi í gegnum hér. Ég skal gefa ykkur vísbendingu. Það hefur að gera með þá staðreynd að þegar þú ert að skoða skilyrt þinn, þú ert ekki að haka fyrir rétta vísitölu. Svo núna þú ert að skoða fyrir array Vísitala j er minna en array Vísitala i. En hvað ert þú að gera upp á upphaf for lykkju? Ert þú ekki að setja j jafnt i? 

Já, svo við getum í raun hætta aflúsara hér. Svo skulum taka a líta á sauðakóðanum. For-- við erum að fara að byrja á ég jafngildir 0. Við erum að fara að fara upp að n mínus 1. Við skulum athuga, gerði við hafa þann rétt? Já, það var rétt. 

Svo þá inni hér, við erum fara að búa til lægsta gildi og setja það jafn i. Gerði við það? Já, gerði það. Nú í okkar innri fyrir lykkju, við erum fara að gera j jafngildir ég að n mínus 1. Gerði við það? Reyndar, við fengum það. 

Svo þó, hvað erum við að bera saman hér? 

Áhorfendur: j auk 1. ANDI Peng: Einmitt. Og þá þú ert að fara að vilja til að setja Lágmarks þinn jafnt j + 1 eins og heilbrigður. Svo ég fór í gegnum það mjög fljótt. Gera þú krakkar skilja hvers vegna það er, j auk 1? OK. 

Svo í array þinn, í í fyrstu umferð í gegnum, þinn fyrir lykkju, fyrir int Ég jafngildir 0, við skulum bara ráð fyrir að þetta hafi ekki verið breytt enn. Við höfum fjölda, alveg, aðeins fjórum óflokkaðar þættir, ekki satt? Þannig að við viljum að frumstilla ég er jafn 0. Og ég er að fara að bara hlaupa í gegnum þessa lykkju. Og svo í fyrstu umferð, við erum að fara að frumstilla breytu sem heitir "mín" sem einnig jafngildir i, vegna þess að við höfum ekki lágmarks gildi. Svo er það nú jöfn 0 eins og heilbrigður. Og þá erum við að fara að fara í gegnum. Og við viljum að árétta aftur. Nú þegar við höfum fundið það amk okkar er, við viljum árétta gegnum aftur til að sjá hvort það er að bera saman, ekki satt? Svo j hér, er að fara til að jafna I, sem er 0. Og þá ef array, j auk i, sem er sá sem er næst yfir, sem minna en hvað núverandi lágmarki þinn gildi er, þú vilt skipta. 

Svo við skulum bara segja að við höfum fékk, eins og, 2, 5, 1, 8. Núna, ég er jafn 0 og J er jafnt og 0. Og það er lágmarks gildi okkar. Ef array-j auk i-- svo ef einn það er eftir einn við erum að horfa á er meiri en sá áður en það, það er að fara að verða að lágmarki. 

Svo hér sjáum við að 5 er ekki minna en það. Svo það er að fara að ekki að vera 5. Við sjáum að 1 er minna en 2, ekki satt? Svo nú vitum við að lágmarki okkar er að fara að vera vísitölu á 0, 1, 2. Já? Og svo þegar þú færð niður hér, þú getur skipti rétt gildi. 

Svo þegar þið voru bara að hafa j áður, þú varst ekki að horfa á einn eftir það. Þú varst að horfa á sama gildi, sem er hvers vegna það var bara ekki að gera neitt. Er að skynsamleg að allir, hvers vegna við þurftum að auk 1 þar? OK. Nú skulum hlaupa bara í gegnum það að gera viss um að restin af kóða er rétt. Hvers vegna er þetta að gerast? Ah, er það mín hérna. Við vorum að bera saman rangt gildi. Ó nei. 

Ó já, hérna við vorum skipta á röng gildi eins og heilbrigður. Þar sem við vorum að horfa á i og j. Þeir eru þeir sem við vorum stöðva. Við viljum í raun að skipta á lágmarki, núverandi lágmarki, með hvað sem menn úti er. Og eins og þú krakkar geta séð niður hér höfum við flokkað array. Það þurfti bara að gera með sú staðreynd að þegar við vorum að haka við gildi við vorum að bera saman, við vorum ekki að leita á réttum gildum. Við vorum að horfa á sama einn hér, í raun ekki að skipta um það. Þú þarft að líta á einn við hliðina að því og þá er hægt að skipta. Svo er það sem var eins konar þrjótur kóðann okkar áður. Og það sem ég gerði hér er allt aflúsara hefði getað gert fyrir þig Ég gerði bara það á borð, vegna þess að það er auðveldara að sjá frekar en að reyna til að súmma inn á aflúsara. Er að skynsamleg að allir? Cool. 

Allt í lagi. Við getum fært um að tala um asymptotic merki, sem er bara fínt leið til að segja að runtimes af öllum þessum tegundum. Þannig að ég veit Davíð, í fyrirlestri, snert á runtimes. Og hann fór í gegnum allt formúlu um hvernig á að reikna runtimes. Engar áhyggjur af því. Ef þú ert virkilega forvitinn á hvernig það virkar, ekki hika við að tala við mig eftir kafla. Við getum gengið í gegnum formúlur saman. En allt sem þú krakkar hafa virkilega vita er að n veldi yfir 2 er það sama og n veldi. Vegna flesta, veldisvísir, vex mest. Og svo fyrir tilgangi okkar, allt sem við þykir vænt um er að risastór tala sem er vaxandi. 

Svo er það besta mál afturkreistingur af val tagi? Ef þú ert að fara að hafa að iterate gegnum lista og þá iterate gegnum restin af þeim lista, hversu oft eru Ætlarðu að sennilega, í versta case-- í því besta tilfelli, sorry-- keyra í gegnum? Kannski er betri spurning að spyrja, hvað er versta afturkreistingur af val tagi. Áhorfendur: n veldi. ANDI Peng: Það er n veldi, ekki satt. Svo auðveld leið til að hugsa um þetta er eins, hvenær þú ert með tvær hreiður fyrir lykkjur, það er að fara að vera n veldi. Því ekki aðeins ertu keyra í gegnum aftur, þú þarft að fara til baka kring og hlaupa í gegnum það aftur inni til á hverjum gildi. Svo í því tilfelli, þú ert að keyra n sinnum n veldi, sem is-- miður, n sinnum n, sem jafngildir n veldi. 

Og raða er líka svolítið einstök í þeim skilningi að það skiptir ekki máli ef þessir gildi eru þegar til. Það er samt að fara að keyra í gegnum engu að síður. Við skulum bara segja að þetta var 1, 2, 3, 4. Óháð því hvort það væri í röð, enn það hefði hljóp í gegnum og enn skoðaði lágmarks gildi. Það hefði gert sama fjölda athugana hvert einasta skipti, jafnvel þótt það ekki í raun snerta neitt. 

Svo í því tilviki, besta og versta runtimes eru í raun jafngildir. Svo ráð afturkreistingur af val tagi, sem við tilnefna með tákninu af þeta, þeta, í þessu tilfelli, myndi einnig vera n veldi. Allir þrír af þessum yrði n veldi. Er allir á hreinu hvers vegna afturkreistingur er n veldi? 

Allt í lagi. Þannig að ég ætla bara að fara að fljótt hlaupa gegnum the hvíla af the konar. The reiknirit fyrir kúla sort-- muna, þetta var sá fyrsti Davíð fór yfir í fyrirlestri. Í meginatriðum, þú stíga í gegnum lista og þú swap-- þig bara bera saman tvö í einu. Og ef maður er meiri, en þú bara skipta á þeim. Svo ef þetta eru meiri, myndir þú skipta. Ég hef fengið opinbera hérna. 

Þannig að við skulum bara segja að þú hefðir 8, 6, 4, 2. Þú vilt bera saman 8 og 6. Þú vilt þurfa að skipta á þeim. Þú myndir bera saman 8 og 4. Þú vilt þurfa að skipta á þeim. Ef þú þarft að skipta um 8 og 2, breyta þeim eins og heilbrigður. Svo í svona tilfinningu, getur þú séð, spilað út á löngum tíma, hvernig gildi konar kúla til endar, sem er hvers vegna við köllum það kúla tegund. 

Við viljum bara hlaupa í gegnum aftur á Annað framhjá okkar, og þriðja framhjá okkar, og fjórða umferð okkar. Í meginatriðum, kúla raða bara keyrir þar til þú ekki gera neinar fleiri skiptasamninga. Svo í þeim skilningi, þetta er bara almenn sauðakóðanum fyrir það. Engar áhyggjur, þetta verður allt að vera á netinu. Við þurfum ekki að raunverulega fara yfir þetta. 

Við frumstilla bara teljara breyta sem byrjar á 0. Og við iterate gegnum allt array. Og ef eitt gildi is-- ef þetta gildi er meiri en þessi gildi, þú ert að fara að skipta á þeim. Og þá þú ert bara fara að halda áfram. Og þú ert að fara að telja. Og þú ert bara að fara að halda að gera þetta á meðan teljarinn er meiri en 0, sem þýðir að hvert skipti sem þú þarft að skipta, þú veist að þú vilt fara aftur og athuga aftur. Þú vilt halda stöðva fyrr en þú veist að þú þarft ekki að skipta aftur. 

Svo hvað eru bestu og verstu Málið runtimes fyrir kúla tegund? Og hint-- þetta er í raun mismunandi frá val tagi í þeim skilningi að þessi tvö svör eru ekki það sama. Hugsaðu um hvað myndi gerast í mál ef það var þegar raðað. Og hugsa um hvað myndi gerast ef það var um er að ræða þar sem það var ekki raðað. Og þú getur konar keyrt gegnum hvers vegna það er að gerast. Ég skal gefa ykkur, eins og, 30 sekúndur til að hugsa um það. 

OK. Hefur einhver hafa a giska á hvað versta afturkreistingur af kúla tagi? Já. 

Áhorfendur: Væri, eins og, n sinnum n mínus 1 eða eitthvað svoleiðis? Eins hvert skipti sem það keyrir, það er bara eins og einn skipti minna að hvað sem það var. 

ANDI Peng: Já, svo þú ert alveg rétt. Og þetta er mál sem þinn Svarið var í raun flóknari en sá sem við þurfum að gefa. Svo það er að fara að run-- ég að fara að eyða öllu þessu hér. Er allir góður? Get ég eytt þessu? OK. Þú ert að fara að keyra í gegnum n sinnum í fyrsta skipti, ekki satt? Og þeir eru að fara að keyra í gegnum n mínus 1 í annað sinn, ekki satt? Og þá þú ert að fara að halda fara, n minn 2, et cetera. David gerði þetta í fyrirlestri, þar sem, ef þú bætt upp alla þá gildi, þú færð eitthvað sem er like-- yeah-- yfir 2, sem í raun bara dregur niður á móti n veldi. Þú ert að fara að fá undarlegt brot þar. Og svo bara vita að N veldi alltaf gengur framar hluta. Og svo í þessu tilviki, það versta afturkreistingur yrði n veldi. Ef það var í lækkandi röð, hugsa, þú að gera skipti hvert einasta skipti. 

Hvað væri hugsanlega, Best Case afturkreistingur? Við skulum bara segja, ef listinn var þegar í því skyni, hvað myndi afturkreistingur vera? 

Áhorfendur: n. ANDI Peng: Það er n, nákvæmlega. Og hvers vegna er það n? Áhorfendur: Þar sem þú bara að kíkja á hverjum einu sinni. ANDI Peng: Einmitt. Svo í besta mögulega afturkreistingur, ef þessi listi var þegar sorted-- segjum 1, 2, 3, 4-- þú myndi bara fara í gegnum, þú vildi athuga, þú vildi sjá, ó, þeir pönnu út. Ég vissi ekki að skipta. Ég er búinn. Svo í því tilfelli, það er bara n eða fjölda skrefum þú bara þurfti að athuga í fyrsta listanum. 

Og eftir, högg við nú innsetning flokka, þar reiknirit er í raun að skipta það í raðaða og óflokkuðu hluta. Og síðan einn af öðrum, en óflokkaðar gildin eru sett í viðeigandi þeirra stöður í upphafi listanum. 

Svo til dæmis, við höfum lista af 3, 5, 2, 6, 4 aftur. Við vitum að það er nú Óflokkaður vegna þess að við höfum bara byrjaði að horfa á það. Við lítum og við vitum að Fyrsta gildið er raðað, ekki satt? Ef þú ert bara að leita á fjölda stærð eitt, þú veist að það er flokkað. 

Svo þá vitum við að Hinar fjórar eru Óflokkaður. Við förum í gegnum og við sjáum það gildi. Við skulum fara aftur. Sjá að verðmæti 5? Við taka a líta á það. Við berum það saman í 3. Við vitum að það er meiri en 3, þannig að við vitum að það er flokkað. Þannig að við vitum nú að fyrstu tveir eru flokkuð og síðustu þrjú eru það ekki. 

Við taka a líta á 2. Við athugum það fyrst með 5. Er það minna en 5? Það er ekki. Þannig að við verðum að halda að leita niður. Síðan sem þú athugað 2 af 3. Það er minna en? Nei Svo þú veist 2 á að setja inn að framan og 3 og 5 bæði að vera ýtt út. Gerðu þetta aftur með 6 og 4. Og við höldum bara að skoða í raun, þar sem við athuga bara, athuga, athuga. Og þar sem það er í hægri staða, við konar bara setja það í rétta stöðu, sem er þar sem nafn það kom frá. 

Svo er það bara reiknirit, sauðakóðanum í sjálfu sér, eins konar, um hvernig við myndum innleiða innsetning konar. Sauðakóðanum er hér. Það er allt á netinu. Engar áhyggjur ef þið eru reyna að afrita þetta niður. Svo enn og aftur, sama question-- hvað væri best og verstu runtimes fyrir innsetningu tagi? Það er mjög svipað og í síðustu spurningu. Ég skal gefa ykkur, eins og, 30 sekúndur til að hugsa um þetta eins og heilbrigður. 

OK Hefur einhver vilja til að gefa mér það versta afturkreistingur? Já. 

Áhorfendur: n veldi. 

ANDI Peng: Það er n veldi. Og hvers vegna er það veldi n? 

Áhorfendur: Vegna þess að í í öfugri röð, þú þarft að fara í gegnum n sinnum n, sem is-- ANDI Peng: Já, einmitt. Svo sama og í kúla tagi. Ef þessi listi er í röð, þú ert fara að hafa til að athuga fyrst þegar. Og þá með hverjum Umframvirði, þú ert fara að hafa til að stöðva það gegn hvert einasta gildi, ekki satt? Og svo alveg, þú ert að fara að gera N pass sinnum annar n framhjá, sem er n veldi. Hvað um besta tilfelli? Já. 

Áhorfendur: n mínus 1, vegna þess að fyrsti er þegar veldi. 

ANDI Peng: Svo nærri. Svarið er í raun n. Því á meðan sá fyrsti er raðað, getur það ekki actually-- það við heppni bara út í sem dæmi, að 2 varð að vera minnsti fjöldi. En það mun ekki alltaf vera raunin. Ef 2 er þegar raðað í upphafi en þú útlit og það er 1 hér, sem 1 er að fara að högg það. Og það er að fara að enda upp höggdeyfir engu að síður. 

Svo í besta falli, það er í raun bara að fara að vera n. Ef þú ert 1, 2, 3, 4, 5, 6, 7, 8, ert að fara að keyra í gegnum að allt lista einu sinni að athuga hvort allt er í lagi. Er allir á hreinu gangi sinnum við val eins og heilbrigður? Ég veit að ég er að fara í gegnum þetta mjög hratt. En bara veit að ef þú veist almenn hugtök, ættir þú að vera góður. OK. Svo ég ætla bara að gefa ykkur kannski, eins og, mínútu til að tala við nágranna þína á hvað eru bara sumir af the aðalæð mismunur milli þessa tegund af toga. Við munum fara yfir það fljótlega. Áhorfendur: Oh, OK. ANDI Peng: Já. OK. Cool, við skulum reconvene í bekknum. OK. Svo var þetta góður af opinn í báða enda spurning í skilningi að það er hellingur af svörum við þeim. Og við munum fara yfir nokkrar af þeim stuttlega. Ég vildi bara að fá ykkur hugsa um hvað mismunandi Allar þrjár gerðir af toga. Og ég heyrði einnig, mikill question-- hvað þýðir mergesort gera? Frábær spurning, því það er það sem við erum nær næst. 

Svo Mergesort er einn svona sem virka mjög mismunandi frá öðrum tegundum. Eins og þú krakkar geta see-- gerði Davíð að kynningu þar sem hann hafði alla kaldur hávaði sjá hvernig sameinast tegund hljóp, eins og, óendanlega hraðar en í hinum tveimur gerðum? OK. Svo er það vegna þess sameinast tegund útfærir sem aðskilja og sigra hugtak sem við höfum talaði um mikið í fyrirlestri. Í þeim skilningi að við viljum að vinna betri, ekki herða, þegar þú skipta og sigra vandamál, og brjóta þau niður, og þá setja þá saman, góðir hlutir gerast alltaf. 

Svo á leiðinni að sameina Raða í raun virkar er að það skiptir An Óflokkaður array í tvennt. Og þá er það fékk tvo helminga af fylki. Og það skiptir bara þá tvo helminga. Hún heldur bara að deila í tvennt, í helmingur í helmingi uns allt er flokkað og þá endurkvæmur setur það allt saman. 

Svo er það í raun ágrip. Svo er þetta bara hluti af sauðakóðanum. Er að skynsamleg í hvernig það er að keyra? Svo við skulum bara segja að þú ert með array af n þætti, ekki satt? Ef n er minna en 2, getur þú farið aftur. Því þú veist að ef það er aðeins einn hlutur, verður það að vera flokkaður. Annars, þú raða vinstri helming, og þá raða rétt helminginn, og þá sameinast. 

Svo á meðan það lítur mjög auðvelt, í raun og veru, að hugsa um það er konar erfitt. Þar sem þú ert eins og, Jæja, það er góður af gangi á sig. Ekki satt? Það er í gangi á sig. Svo í þeim skilningi, David snert á endurkvæmni í bekknum. Og það er hugtak við munum tala um meira. Það er að þessu, þessar tvær línur hér, reyndar er bara program segja það að keyra sig með mismunandi inntak. Svo frekar en að keyra sig með heild á n þáttum, þú getur brjóta það niður í vinstri helminginn og hægri helminginn og þá að keyra hana aftur. 

Og þá munum við líta á það sjónrænt, því ég er sjónrænn nemandi. Það virkar betur fyrir mig. Þannig að við munum líta á sjón dæmi hér. 

Segjum að við höfum fylki, sex þættir, 3, 5, 2, 6, 4, 1, ekki raðað. Allt í lagi, það er mikið á þessari síðu. Svo ef þú krakkar geta líta á Fyrsta skrefið hér, 3, 5, 2, 6, 4, 1, þú getur skipt henni í tvennt. Þú hefur 3, 5, 2, 6, 4, 1. Þú veist að þetta aren't-- þig veit ekki hvort þeir eru raðað eða ekki, svo þú haldir að brjóta þá niður, í tvennt, í tvennt, í tvennt, þar til að lokum, þú hefur aðeins einn þáttur. Og einn þáttur er alltaf raðað, ekki satt? 

Við vitum því að 3, 5, 2, 4, 6, 1, með sjálfum sér, eru flokkuð. Og nú getum við setja þá aftur saman. Þannig að við vitum að 3, 5. Við setja þá saman. Við vitum að það er flokkað. 2 er enn þar. Við getum sett 4 og 6 saman. Við vitum að það er raðað, svo við settum það saman. Og 1 er. 

Og þá þú lítur bara á þessir tveir helmingar hérna. Þú hefur 3, 5, 2, 2, 3, 5. Þú getur bara að bera saman farin af öllu. Því þú veist að þetta er flokkað og þú veist að það er flokkað. Svo þá getur þú ekki einu sinni að bera 5, að bera bara 3. Og 2 er minna en 3, svo þú veist 2 að fara á endanum. 

Sami hlutur þarna. The 1 verður að fara hér. Og svo þegar þú ferð að setja þessir tveir gildi saman, þú veist að þetta er flokkað og þú veist að það er flokkað. Svo þá 1 og 2, er 1 er minna en 2. Það segir þér að 1 ætti að fara á lok þessa án þess þó að horfa á 3 eða 5. Og 4 þá getur þú bara stöðva, það fer rétt hér. Þú þarft ekki að líta á 5. Sami hlutur með 6. Þú veist að 6-- það bara þarf ekki að vera sá. 

Og svo á þann hátt, að þú ert bara að safna sjálfur a einhver fjöldi af stíga þegar þú ert að bera saman. Þú þarft ekki að bera saman hvert þáttur gegn öðrum þáttum. Að bera bara á móti þeim sem sem þú þarft að bera það gegn. Svo er það eins konar abstrakt hugtak. Engar áhyggjur ef það er ekki alveg hitting þér rétt enn. En almennt, þetta er hvernig Mergesort virkar. Spurningar, fljótur spurningar, áður en ég fara? Já. 

Áhorfendur: Svo þú segir að þú takir í 1, og þá 4, og 6 og setja þá í. Svo eru those-- ekki eru ekki þú horfa á þá sem aðskilda þætti, ekki sem heild? ANDI Peng: Já. Svo hvað er að gerast er að þú í rauninni eru að búa til nýtt array. Svo þú veist að hér, ég hef tvær fylki af stærð 3, ekki satt? Svo þú veist að Raðað array minn þarf að hafa sex þætti. Svo þú býrð bara a Ný magn af minni. Svo þú ert svona eins og vera eyðslusamur af minni, en það skiptir ekki máli því það er svo lítið. Svo þú horfir á 1 og þú horfir á 2. Og þú veist að 1 er minna en 2. Svo þú veist að 1 ætti að fara í upphaf allra þeirra. 

Þú þarft ekki einu sinni að líta á 3 og 5. Svo þú veist 1 fer þangað. Síðan sem þú höggva í grundvallaratriðum af 1. Það er, eins og dauður okkur. Þá höfum við bara 2, 3, 5, og þá 4 og 6. Og þá veistu að þú bera þau saman 4 og 2, ó, 2 ætti að fara í það. Svo þú plop á 2 niður, og þú höggva það burt. Svo þá er bara að 3 og 5 í 4 og 6. Og þú heldur bara chopping það burt fyrr en þú setur þá í array. 

Áhorfendur: Svo þú ert bara alltaf bera [inaudible]? 

ANDI Peng: Einmitt. Svo í þeim skilningi, að þú ert bara að bera saman, í raun, eitt númer á móti annað númer. Og vegna þess að þú veist að það er raðað, þú þurfa ekki að horfa í gegnum allar tölur. Þú verður bara að líta á það fyrsta. Og þá getur þú bara plop þá niður, vegna þess að þú veist þeir tilheyra þar sem þeir þurfa að tilheyra. Já. Góð spurning. 

Og ef einhver ykkar eru dálítið metnaðarfull, ekki hika við að líta á þetta númer. Þetta er í raun líkamlega framkvæmd um hvernig við myndum skrifa mergesort. Og þú geta sjá, það er mjög stutt. En hugmyndir að baki það eru ansi flókið. Svo ef þér finnst eins og að teikna þetta út í heimavinna í kvöld þína, ekki hika við að. 

OK. Og Davíð fór líka yfir þetta í fyrirlestri. Hvað eru bestu málið runtimes, á versta runtimes, og væntanlegan runtimes af mergesort? Tveimur sekúndum að hugsa. Þetta er frekar erfitt, en eins konar innsæi ef þér finnst um það. Allt í lagi. 

Áhorfendur: Er versta n log n? ANDI Peng: Einmitt. Og hvers vegna er það log n n. 

Áhorfendur: Er það ekki vegna þess að það verður veldishraða hraðar, svo það er eins og virkni sem í stað þess að bara einfaldlega að vera n kvaðrat eða eitthvað? ANDI Peng: Einmitt. Svo er ástæðan fyrir því afturkreistingur á þetta er n log n er because-- hvað ert þú gera í öllum þessum skrefum? Þú ert bara að höggva hann í tvennt, ekki satt? Og svo þegar við erum að gera í log, allt sem það er að gera er að deila vandamál í tvennt, í tvennt, í tvennt, í fleiri helminga. Og í þeim skilningi, getur þú góður af útrýma línulega líkan sem við höfum verið að nota. Vegna þess að þegar þú höggva hlutir í tvennt, það er skráning. Það er bara stærðfræði leið fulltrúi hana. 

Og svo að lokum, í lok, þú ert bara að gera eitt síðasta liggja í gegnum að setja þá alla í röð, ekki satt? Og svo ef þú verður bara að athuga eitt, það er n. Og svo þú ert góður af margfalda tvö saman. Svo það er eins og þú hafir fengið það sem kemur síðas athuga n hérna með log n upp hér. Og ef þú margfaldar þá, sem er n log n. 

Og svo það besta tilfelli og versta tilfelli og gert er ráð fyrir allt n log n. Það er líka eins og annars konar. Það er eins og val konar í þeim skilningi að það skiptir ekki máli hvað þinn Listinn er, það er bara að fara að gera það sama í hvert einasta skipti. OK. Svo eins og þú krakkar geta sjá, jafnvel þótt þær tegundir sem við höfum farið through-- n veldi, það er ekki mjög duglegur. Og jafnvel þessi n log n er ekki duglegur. Ef þið eru forvitinn, það er tegund kerfi sem eru svo duglegur að þeir eru nánast nánast í afturkreistingur. 

Þú hefur got sumir log n 's. Þú hefur got sumir log log n 's. Við ekki snerta á þeim í þessum flokki núna. En ef þú krakkar eru forvitnir, ekki hika við að google, hvað er hagkvæmustu flokkun kerfi. Ég veit það ekki, það eru sumir raunverulega fyndið sjálfur, like-- það er einhver raunverulega fyndið þau sem fólk gerir. Og þú furða hvernig þeir alltaf hugsað um það. Svo google, ef þið hafið einhverjar vara tími, á, hvað eru nokkur fyndin leiðir sem people-- sem og duglegur ways-- fólk hafa verið fær um að framkvæma konar. OK. Og hér er bara handlaginn lítill graf. Ég veit allt um þig, fyrir þann spurningakeppni 0, verður í herberginu þínu líklega að reyna að leggja á minnið það. Svo er það gott þarna fyrir ykkur. Bara ekki gleyma rökfræði sem made-- hvers vegna þær tölur voru fram. Ef þú ert alltaf tapað, bara gera viss um að þú veist hvað konar eru. Og þú getur keyrt í gegnum þá í huga þínum að reikna út hvers vegna þeir Svörin eru þau svör. 

Allt í lagi. Þannig að við erum að fara að flytja á, að lokum, að leita. Því eins og þau ykkar sem hafa lesið pset, rannsakandi er einnig hluti af þessa viku vandamál setur. Þú verður beðin að framkvæma tvær tegundir af leit. Eitt er línuleg leit og einn er a tvöfaldur leit. 

Svo er nokkuð auðvelt að línuleg leit. Þú vilt bara að leita frumefni af lista til að sjá hvort þú færð það. Þú verður bara að árétta gegnum. Og ef það er jafnt eitthvað, þú getur bara farið með hana, ekki satt? En sá sem við erum mest áhuga á að tala um er tvöfaldur leita, hægri, sem er skipta og sigra kerfi sem David var að sýna í fyrirlestri. 

Mundu símaskránni dæmi að hann heldur að koma upp, sá sem hann svona barist dálítið á þessu síðasta ári, þar sem þú skipta vandamál í tvennt, í tvennt, í tvennt, aftur og aftur, þar til þú finnur það sem þú ert að leita að? Og þú hefur fengið að afturkreistingur af því sem vel. Og þú geta sjá, það er verulega skilvirkari en nokkur önnur tegund af leit. 

Svo leið að við myndum fara um innleiða tvöfaldur leit er, ef við hefðum fylki, Vísitalan 0 til 6, en sjö, getum við litið í miðju, right-- Því miður, ef spurningunni okkar first-- ef við viljum að spyrja um, er array innihalda þáttur 7, augljóslega, vera menn, og hafa svo lítið array, það er auðvelt fyrir okkur að segja já. En leiðin til að innleiða tvöfaldur Leita væri að líta í miðjunni. 

Við vitum að vísitalan 3 er miðju, vegna þess að við veit að það eru sjö atriði. Hvað 7 deilt með 2? Þú getur skorið burt sem auka 1. Þú hafir fengið 3 í miðjunni. Svo er array af 3 jafnt og 7? Það er ekki, ekki satt? En við getum gert nokkrar athuganir. Er array af 3 minna en 7 eða er array af 3 meiri en 7? 

Og við vitum að það er minna en 7. Þannig að við vitum að, ó, verður það ekki vera í vinstri helming. Við vitum að það verður að vera í hægri hluta, ekki satt? Svo við getum bara höggva af helming fylkisins. Við gerum ekki einu sinni að líta á það lengur. Þar sem við vitum að helmingur problem-- okkar við vitum að svarið er í hægri helminginn af vandamálinu okkar. Svo við lítum bara á það núna. 

Svo nú erum við að líta á miðja hvað er vinstri. Vísitalan 5. Við gerum það sama stöðva aftur og við sjáum að það er minni. Svo við lítum vinstra megin við það. Og þá sjáum við að stöðva. Er fylki gildi á Vísitala 4 jafnt og 7? Það er. Svo við getum skila satt, vegna þess að við fundum gildi í listanum okkar. Er eins og ég fór í gegnum að skynsamleg að allir? OK. Ég skal gefa ykkur kannski, eins og, þrjár, fjórar mínútur til að reikna út hvernig á að sauðakóðanum þetta í. 

Svo ímynda ég bað þig að skrifa virka kölluð Leita () sem skilaði gildi, a Boolean gildi, sem var satt eða false-- eins, satt ef þú fundið gildi, falskur ef þú gerðir það ekki. Og þá þú varst samþykkt í gildi sem þú voru að leita að í gildi, sem er array-- ó, setti ég örugglega sem á röngum stað. OK. Allavega, það ætti að hafa verið að hægri gildum. Og þá er INT n fjöldi staka í því fylki. Hvernig myndir þú fara um að reyna sauðakóðanum þessi vandamál í? Ég skal gefa ykkur eins þrjár mínútur til að gera það. Nei, ég held að það er only-- já, það er eitt rétt upp hér. Áhorfendur: Get ég? ANDI Peng: Já, ég fékk þig. Er það vinna? OK, flott. 

OK. Jaeja krakkar, við erum að fara að hemja það í. OK. Svo gerum við höfum fengið þessa yndislegu lítið array með n gildum í það. Ég vissi ekki að draga línurnar. En hvernig myndum við fara um reyna að skrifa þetta? Er einhver vilja til að gefa mér fyrstu línu? Ef þú vilt gefa mér að Fyrsta lína af þessu sauðakóðanum. 

Áhorfendur: [inaudible] Áhorfendur: Þú vilt vilt að árétta through-- Áhorfendur: Bara annar fyrir lykkju? Áhorfendur: --for. 

ANDI Peng: Svo er þetta dálítið erfiður. Hugsaðu about-- þú vilt að halda í gangi þessa lykkju aftur og aftur þangað til hvenær? 

Áhorfendur: Til [inaudible] gildi er jöfn að verðmæti. ANDI Peng: Einmitt. Svo þú getur í raun bara write-- við getum jafnvel einfalda það meira. Við getum bara gert while lykkju, ekki satt? Svo þú getur bara hafa loop-- við vitum að það er á meðan. En núna ætla ég að að segja "lykkju" - í gegnum það? Loop until-- hvað er okkar endar ástand? Ég held að ég heyrði það. Ég heyrði einhvern segja það. 

Áhorfendur: Gildi jafngildir miðjuna. ANDI Peng: Segja það aftur. Áhorfendur: Eða, þar til gildi sem þú ert að leita fyrir er jafnt miðju gildi. 

ANDI Peng: Hvað ef það er ekki þar? Hvað ef gildið sem þú ert að leita fyrir er í raun ekki í þessu fylki? Áhorfendur: Þú skila 1. 

ANDI Peng: En hvað viljum við lykkja til ef við höfum ástand? Já. 

Áhorfendur: Til að það er aðeins eitt gildi? ANDI Peng: Þú getur lykkja until-- svo þú veist að þú ert fara að hafa max gildi, ekki satt? Og þú veist að þú ert að fara hafa min gildi, ekki satt? Vegna einnig, það er eitthvað Ég gleymdi að segja áður, sem eitthvað sem er gagnrýni um tvöfaldur leit er að array er þegar raðað. Vegna þess að það er engin leið til að gera þetta ef þeir eru bara handahófi gildi. Þú veist ekki hvort maður er stærri en hinn, ekki satt? 

Svo þú veist að max og mín eru hér, ekki satt? Ef þú ert að fara að stilla max þinn í mín þínum og mid-- við skulum gera ráð bara þinn miðjan gildi er rétt here-- þú ert að fara að í grundvallaratriðum lykkja þar til lágmarks er um það sama og max þinni, ekki satt, eða ef max er ekki það sama og mín þinn. Ekki satt? Vegna þess að þegar það gerist, þú veist að þú hefur loksins högg á sama gildi. Svo þú vilt að lykkju þar til mín þitt er minna en eða jafnt to-- oops, ekki minna en eða jafnt og, önnur leið around-- max er. 

Var það skynsamleg? Ég tók nokkrar tilraunir til að fá það rétt. En lykkja þar max value þinn er í raun nánast minna en eða jafnt og lágmarki þinni, ekki satt? Það er þegar þú veist sem þú hefur stefna. Áhorfendur: Þegar myndi hámark þitt gildi er minna en lágmarkið? ANDI Peng: Ef þú halda stilla það, sem er það sem við erum að fara að vera að gera í þessu. Er að skynsamleg? Lágmarks- og max eru bara heiltölur sem við erum líklega fara til að vilja búa til að halda lag þar sem við erum að leita. Þar sem array til staðar án tillits til þess hvað við erum að gera. Eins erum við í raun ekki líkamlega chopping burt array, ekki satt? Við erum bara að stilla þar sem við erum að leita. Er að skynsamleg? 

Áhorfendur: Já. 

ANDI Peng: OK. Þannig að ef það er skilyrði fyrir lykkju okkar, hvað við viljum inni þessa lykkju? Hvað erum við að fara að hafa áhuga á að gera? Svo núna, þá erum við a max og mín, hægri, líklega búin hér einhvers staðar. Við erum að fara að sennilega vilja að finna miðju, rétt? Hvernig eigum við að fara að vera fær um að finna miðju? Hvað er mathematical-- Áhorfendur: Max plús mín deilt með 2. ANDI Peng: Einmitt. Er að skynsamleg? Og gera þú krakkar sjá hvers vegna við ekki bara use-- hvers vegna við gerðum þetta í stað þess að gera bara n deilt með 2? Það er vegna þess að n er gildi það er að fara að vera sú sama. Ekki satt? En eins og við að stilla lágmarks okkar og hámarksgildi, þeir eru að fara að breytast. Og þar af leiðandi, miðja okkar er að fara að breytast líka. Svo er það hvers vegna við viljum að gera þetta hérna. OK. 

Og þá, nú sem við höfum fundið our-- já. 

Áhorfendur: Just a fljótur question-- þegar þú segir mín og max, við erum að því gefnu að það er þegar raðað? 

ANDI Peng: Já, það er í raun forsenda tvöfaldur leit, sem þú þarft að vita að það er flokkað. Hver er ástæðan fyrir tegund, skrifa þú í þinn Heimadæmi fyrir tvöfaldur leitina. OK. Svo nú er að við vitum hvar miðpunkt okkar er, hvað viltu gera hér? 

Áhorfendur: Við viljum að bera saman að til þess að hinn. ANDI Peng: Einmitt. Svo þú ert að fara að bera saman meðal til verðmæti, ekki satt? Og hvað segir það okkur þegar við berum saman? Hvað viljum við gera á eftir? 

Áhorfendur: Ef gildið er stærra en um miðjan, viljum við að skera það burt. ANDI Peng: Einmitt. Svo ef gildið er stærra en um miðjan erum við fara til að vilja breyta þeim lágmarki og Maxes, ekki satt? Hvað viljum við að breyta? Þannig að ef við vitum gildi er einhvers staðar hér, hvað þér við að breyta? Við viljum breyta okkar lágmark að vera miðjan, ekki satt? Og þá annað, ef það er í þessu helmingur, hvað viljum við breyta? 

Áhorfendur: hámark þitt. ANDI Peng: Já. Og þá þú ert bara að fara að halda lykkja, ekki satt? Vegna þess að nú, eftir einn endurtekning í gegnum, hefur þú fengið max hér. Og þá er hægt að endurreikna miðjan. Og þá er hægt að bera saman. Og þú ert að fara að halda áfram þar til mín og maxes hafa í raun stefna. Og það er þegar þú veist að þú hefur högg fyrir endann á henni. Og annað hvort þú hefur fundið það eða þú hefur ekki á þeim tímapunkti. 

Er þetta skynsamleg að allir? OK. Þetta er mjög mikilvægt, því þú munt hafa að skrifa þetta í kóða kvöld þínum. En þú krakkar hafa a laglegur góður vit á því hvað þú ættir að vera að gera, sem er gott. OK. Þannig að við höfum fengið um sjö mínútur eftir kafla. Þannig að við erum að fara að tala um þetta pset að við munum vera að gera. Svo pset er skipt í tvo helminga. Á fyrri helmingi felur framkvæmd a find þar sem þú skrifa línulega leit, a Tvíundarleit og flokkun reiknirit. 

Svo er þetta fyrsta tími í pset hvar við munum vera að gefa ykkur það sem er kallað dreifingu kóða, sem er númer sem við höfum fyrirfram skrifað, en bara skilið eftir nokkur stykki af fyrir þig að klára að skrifa. Svo ykkur, þegar þú horfir á þetta kóða, þú might fá virkilega hrædd. Ef þú ert bara eins og, Ahh, I veit ekki hvað það er að gera, Ég veit ekki, eins og það virðist svo flókið, Ahh, slaka á. Það er allt í lagi. Lesa sérstakur. Sérstakur mun útskýra fyrir þér nákvæmlega hvað öll þessi forrit eru að gera. 

Til dæmis, generate.c er forrit sem mun koma með pset þinn. Þú gera ekki raunverulega hafa að snerta það, en þú ættir að skilja hvað það er að gera. Og generate.c, allt það er að gera er annaðhvort að búa slembitölur eða þú getur gefið það fræ, eins og fyrirfram ákveðnum fjölda sem það tekur, og hefur meiri tölur. Svo er einhver sérstök leið til að innleiða generate.c sem þú getur bara gert fullt af tölum fyrir þig að prófa aðrar aðferðir þínar. 

Svo ef þú vildir, að dæmi, prófa finna þinn, þú vilt að keyra generate.c, búa til fullt af tölum, og þá hlaupa aðstoðarmenn virka. Framreiðslu virka er þar sem þú ert í raun líkamlega skrifa kóðann. Og hugsa um framreiðslu sem bókasafn skrá þú ert að skrifa, sem finna er að hringja. Og svo innan helpers.c, þú munt gera að leita og flokka. 

Og þá þú ert að fara að í raun bara setja þá alla saman. Sérstakur mun segja þér hvernig á að setja það á the stjórn lína. Og þú munt vera fær um að prófa hvort ekki svoleiðis og leita starfa. Cool. Hefur einhver þegar hafið og komið upp vandamál eða spurningar þeir hafa núna með þetta? OK. 

Áhorfendur: Bíddu. Ég hef spurningu. 

ANDI Peng: Já. 

Áhorfendur: Svo ég byrjaði að gera línulegt leita í helpers.c og það var ekki í raun að vinna. En þá seinna, fann ég út við bara að eyða því og gera tvöfaldur leit. Svo skiptir það máli ef það virkar ekki? 

ANDI Peng: Stutta svarið er nei. En þar sem við erum not-- Áhorfendur: En enginn er reyndar haka. ANDI Peng: Við erum aldrei fara að sjá það. En þú vilt sennilega að gera viss leitina er að vinna. Vegna þess að ef línulegt þitt Leita virkar ekki, þá líkur eru tvöfaldur þitt leit er ekki að fara að vinna eins og heilbrigður. Þar sem þú hefur svipuð rökfræði í þeim báðum. Og nei, það skiptir ekki máli. Þannig að aðeins þær sem þú munt snúa í eru tegund og tvöfaldur leit. Já. 

Og einnig, a einhver fjöldi af krökkum voru reyna að safna saman helpers.c. Þú ert í raun ekki leyft að gera það, vegna þess að helpers.c hefur ekki aðalæð virka. Og svo þú ættir aðeins verið í raun gerð mynda og finna, því finna símtöl helpers.c og aðgerðir innan þess. Svo gerir kembiforrit a sársauki í rassinn. En það er það sem við þurfum að gera. Áhorfendur: Þú gerir bara allt, ekki satt? ANDI Peng: Þú getur bara gera allt eins vel, já. OK. Svo er það það í skilmálar af því sem pset er að spyrja ykkur að gera. Ef þú hefur einhverjar spurningar, ekki hika að spyrja mig eftir kafla. Ég kem hér, eins og 20 mínútur. 

Og já, pset er í raun ekki svo slæmt. Þú krakkar ættu að vera í lagi. Þetta, bara fylgja leiðbeiningunum. Konar hafa tilfinningu, þá er rökrétt, hvað ætti að vera að gerast og þú munt vera fínn. Ekki vera of hrædd. There er a einhver fjöldi af kóða þegar skrifað það. Ekki vera of hrædd ef þú ert ekki skilja hvað allt þetta þýðir. Ef það er mikið, það er alveg í lagi. Og koma til skrifstofutíma. Við hjálpum þér að kíkja. 

Áhorfendur: Með viðbótinni aðgerðir, eigum vér að vænta þá upp? 

ANDI Peng: Já, eru þeir í kóðanum. Í leiknum á 15. Tæpur helmingur það er nú þegar skrifað fyrir þig. Svo þau virka eru þegar í kóðanum. Jebb. Allt í lagi. Jæja, það besta af heppni. Það er ógeðslegt dag. Svo vonandi þú krakkar finnst ekki of slæmt um að dvelja inni og forritun.