SPIKA 1: Hey kila mtu! Karibu tena kwa sehemu. Nimefurahi kuona hivyo wengi wenu wote hapa, na kila mtu ambaye ni kuangalia online. Hivyo, kama kawaida kuwakaribisha nyuma. Natumaini kwamba wote walikuwa lovely mwishoni mwa wiki, kamili ya mapumziko, relaxation. Ilikuwa nzuri nje jana. Hivyo, Natumaini walifurahia nje. Hivyo kwanza ya wanandoa wa matangazo. Grading. Hivyo, wengi wa unapaswa kuwa na kujipatia email kutoka kwangu kuhusu Scratch yako pset, vilevile grading kwa pset 1. Hivyo, wanandoa tu mambo. Kuwa na uhakika wa kutumia check50 katika style50. Hizi ni maana ya kuwa rasilimali kwa ajili ya guys, kuhakikisha kwamba wewe ni kupata pointi kama wengi kama unaweza bila bila kupoteza kwao. Hivyo, mambo kama style ni muhimu sana. Sisi ni kwenda kuchukua mbali kwa ajili yake. Baadhi ya unaweza kuwa tayari niliona kwamba kutoka pset yako. Na check50 ni tu njia rahisi kweli kuhakikisha kwamba sisi ni kweli kurudi nini mahitaji ya kurudishwa kwa mtumiaji, na kwamba kila kitu s kufanya kazi vizuri. Kumbuka pili, kuhakikisha yako kuweka mambo folder sahihi. Inafanya maisha yangu tu kidogo zaidi vigumu kama wewe upload pset 2 katika pset 1 kwa sababu wakati mimi kushusha mambo, hawana kushusha usahihi. Na Mimi najua ni wonky kidogo katika mfumo wa kupata kutumika, lakini tu kuwa super makini, kama tu kwa ajili yangu, hivyo kwamba wakati wewe ni kupata barua pepe katika kama 2:00 na mimi nina grading. Kama si kusababisha nina kuangalia pande zote kwa pset yako. Baridi. Najua ni mapema, lakini mimi kabisa got kuchukuliwa mbali ulinzi na insha hiyo kutokana Ijumaa hii, kwamba maprofesa wangu walikuwa tu kama, oh yeah. Kumbuka, una insha kutokana siku ya Ijumaa. Hivyo, najua hakuna mtu anapenda kufikiri juu ya midterms, lakini jaribio lako la kwanza ni juu ya Oktoba 15, ambayo Oktoba kuanzia wiki hii. Hivyo, inaweza kuwa mapema kuliko ilivyotarajiwa ni yote. Hivyo kwamba wewe si kutupwa mbali ulinzi wakati Mimi kutaja sehemu ya pili ya wiki kuwa oh, Jaribio wiki ijayo yako, nilifikiri Ningependa kukupa kidogo zaidi ya vichwa hadi sasa. Hivyo, tatizo lako kuweka, namba tatu. Jinsi watu kusoma spec nje ya udadisi? OK. Sisi got michache. Aina ya chini kutoka mwisho wiki lakini hiyo ni sawa. Najua ilikuwa nzuri nje. Hivyo kuvunja nje. Dhahiri baada ya kupata kufanyika leo kusoma spec yako angalau kujaribu kama kushusha usambazaji kificho na kukimbia kama awali kwanza Jambo kwamba wao kuuliza wewe. Kwa sababu sisi ni kutumia usambazaji kificho na maktaba kwamba tumekuwa tu imekuwa using-- --It tu mara ya pili tumefanya pset hii, mambo mambo yanaweza kutokea na appliance yako, na unataka kupata kwamba nje sasa dhidi ya baadaye. Kwa sababu kama ni Alhamisi usiku au ni Jumatano usiku na kwa sababu baadhi ya appliance yako tu haina unataka kukimbia na maktaba au na usambazaji kanuni, kwamba njia unaweza hata kuanza kufanya coding. Sababu huwezi kuangalia kuona kama ni kazi. Yako si gonna kuwa na uwezo ili kuona kama inaandaa. Unataka kuchukua huduma ya wale mapema katika wiki, wakati bado unaweza email yangu au moja ya TFS mengine, na tunaweza kupata wale fasta. Kwa sababu wale ni masuala kwamba ni kwenda kuacha wewe kutoka kufanya maendeleo yoyote halisi. Si kama mdudu moja, kwamba unaweza tu aina ya ruka juu. Kama wewe ni kuwa masuala na yako appliance au usambazaji kificho, kweli unataka kupata kwamba kuchukuliwa huduma ya mapema kuliko baadaye. Hivyo hata kama wewe si gonna kweli kuanza coding, download usambazaji kanuni, kusoma spec, kuhakikisha kila kitu s kufanya kazi huko. OK? Kama unaweza tu kufanya hivyo, mimi ahadi ya maisha yako itakuwa rahisi. Na hivyo pengine wewe kwenda kufanya hivyo sasa hivi haki? OK. Hivyo, maswali yoyote huko? Yoyote ya mambo vifaa? Kila mtu mzuri? OK. Icyitonderwa kwa wale wa wewe katika chumba na online. Mimi nina kwenda kujaribu kubadili kati ya PowerPoint katika appliance kwa sababu sisi ni kwenda kuwa kufanya baadhi ya coding leo na mahitaji ya wengi wa watumiaji Pendekezo uchaguzi mimi alimtuma nje wiki iliyopita. Hivyo, sisi kufanya baadhi ya coding. Hivyo, kama wewe guys pia wanataka kwa moto hadi vifaa yako, na unapaswa kuwa got email kutoka kwangu, na sampuli faili. Tafadhali jisikie huru kufanya hivyo. Hivyo, sisi ni kwenda kuzungumza kuhusu GDB, ambayo ni HatiJava. Ni kwenda kukusaidia aina ya takwimu nje ambapo mambo ni kwenda vibaya katika kanuni yako. Ni kweli tu njia kwa ajili ya wewe hatua kupitia kanuni yako kama kinatokea, na kuwa na uwezo wa magazeti nje vigezo au kuona nini hasa kinachotokea chini ya kofia mistari mpango wako kukimbia tu, ni kama faulting, na wewe ni kama, hakuna wazo nini kilichotokea tu hapa. Sijui nini line alishindwa katika. Sijui ambapo potoka. Hivyo, GDB ni kwenda kukusaidia na kwamba. Pia, kama wewe kuamua kuendelea ndiyo, na kuchukua 61, itakuwa kweli, kweli kuwa yako rafiki bora, sababu naweza kukuambia kwa sababu mimi nina kwenda kupitia darasa hilo. Sisi ni kwenda kuangalia binary tafuta, ambayo kama wewe guys kukumbuka kubwa kitabu cha simu mfano tamasha kutoka darasa. Tutaweza kuwa utekelezaji huo, na kutembea kwa njia ya kuwa kidogo zaidi, na kisha tunakwenda kupitia wanne aina mbalimbali, ambayo ni Bubble, Uteuzi, Insertion, na kuunganisha. Baridi. Hivyo, GDB kama nilivyoeleza, ni HatiJava. Na haya ni aina ya kubwa mambo, kazi kubwa au amri kwamba matumizi ya ndani ya GDB, na mimi kutembea wewe kupitia demo yake katika pili. Hivyo, hii si tu kwenda kukaa abstract. Mimi itabidi kujaribu na kufanya hivyo kama halisi kama inawezekana kwa wewe guys. Hivyo, kuvunja. Utakuwa ama kuwa mapumziko kama, baadhi ya idadi, ambayo inawakilisha line katika mpango wako, au unaweza jina kazi. Hivyo, kama wewe kusema kuvunja kuu, itakuwa kuacha katika kuu, na basi wewe kutembea kwa njia ya kazi hiyo. Kadhalika, kama una baadhi ya nje kazi kama Swap au Cube, kwamba sisi inaonekana katika wiki iliyopita. Kama umesema kuvunja mmoja wa wale, wakati wowote mpango wako hits kwamba, utakuwa kusubiri kwa wewe kuwaambia nini cha kufanya. Kabla itakuwa tu nitafanya hivyo inaweza kweli hatua ndani ya kazi na kuona nini kinaendelea. Hivyo, Next, tu skips juu ya mstari wa pili, huenda juu ya utendaji. Hatua. Haya yote ni abstract kidogo. Hivyo, mimi nina kwenda tu kukimbia kwa njia yao, lakini utaona yao katika matumizi ya pili. Hatua katika kazi. Hivyo kama mimi alikuwa akisema, kama na Swap, ingekuwa kuruhusu kweli kama wewe ni kama kimwili wanazidi ndani, unaweza fujo na vigezo wale, magazeti nini wao, kuona nini kinaendelea. Orodha ya mapenzi halisi tu magazeti nje kificho jirani. Hivyo, kama wewe aina ya kusahau ambapo wewe ni katika mpango wako, au wewe wanashangaa nini kinaendelea karibu yake, hii tu magazeti nje sehemu ya kama mistari mitano au sita kuzunguka. Hivyo, unaweza kupata oriented kuhusu ambapo wewe ni. Magazeti baadhi ya kutofautiana. Hivyo, kama una muhimu kama katika Kaisari, kwamba tutaangalia. Unaweza kusema this muhimu katika hatua yoyote. Ni nitakuambia nini thamani ni hivyo kwamba, labda mahali fulani njiani, you overwrote muhimu yako. Unaweza kweli kuwaambia kwamba kwa sababu unaweza kweli kuchunguza thamani hiyo. Katika wenyeji, tu prints nje vigezo lako. Hivyo, wakati wowote wewe ni ndani ya kitanzi, na wewe tu wanataka kuona kama, oh. Mimi yangu ni nini? Ni thamani hii muhimu nini kwamba mimi initialize hapa? Ujumbe katika hatua hii ni nini? Itakuwa tu magazeti yote ya wale, ili hawana mmoja mmoja kusema, this I. this Ujumbe. Magazeti muhimu. Na kisha kuonyesha. Nini kwamba hana ni kama wewe hatua kupitia mpango, utakuwa tu kuhakikisha kwamba ni Inaonekana baadhi ya kutofautiana fulani katika kila hatua. Ili also-- --it ni aina ya mkato ambapo huna kuendelea kama, oh. Magazeti muhimu au this I. Ni tu moja kwa moja kufanya hivyo kwa ajili yenu. Hivyo, pamoja na kwamba, tunakwenda kuona jinsi hii unaendelea. Mimi nina kwenda kujaribu na kubadili juu ya appliance yangu. Kuona kama naweza kufanya hivyo. Wote. Sisi ni kwenda tu kwa kioo yake. Kuna kitu mambo juu ya mbali yangu anyways. OK. Hii inahitaji kuwa hii moja. Ni hivyo vidogo. Hebu angalia kama tunaweza kufanya hivyo. OK. Alice ni wazi wanajitahidi hapa kidogo tu, lakini tutaweza kupata katika momento. OK. Sisi ni kwenda tu kuongeza hii. OK. Unaweza kila mtu aina ya kuona kwamba? Labda kidogo? Najua ni kidogo kidogo. Huwezi kabisa kufikiri jinsi ya kufanya hii kubwa. Kama mtu anajua. Je, mtu yeyote kujua jinsi ya kufanya hivyo kubwa? OK. Tunakwenda unaendelea nayo. Haijalishi anyways kwa sababu ni tu hiyo ni kificho kwamba wewe guys lazima kuwa. Nini muhimu zaidi ni terminal hapa. Na sisi hapa nini ni ndogo sana? Vipimo. Oh. Kweli Ike. Jinsi ya hii? Nje ya hapo. Ni kwamba bora kwa kila mtu? OK ,. Baridi. Unajua wakati uko katika CS matatizo darasa kiufundi ni aina ya sehemu ya the-- Hivyo, hebu wazi huu. OK. Hivyo, haki hapa katika sehemu, ambayo tulikuwa hapa. Caesar ni faili la kutekelezwa. Hivyo mimi alifanya hivyo. Hivyo, jambo moja kwa kutambua na GDB ni kwamba ni kazi tu juu ya executable faili. Hivyo, huwezi kuendesha kwenye DOTSY. Una kweli kufanya kuhakikisha kwamba kanuni yako inaandaa, na kwamba kweli anaweza kukimbia. Hivyo, kuhakikisha kwamba kama hana kukusanya, kupata kukusanya, ili uweze aina ya kukimbia kwa njia hiyo. Hivyo, kuanza GDB, wote kufanya, Gloria aina GDB, na kisha tu faili kwamba unataka. Mimi daima misspell Kaisari. Lakini unataka kuhakikisha tangu ni executable, ti ya dot flash ili ina maana wewe kwenda kuendesha CSI wewe kwenda kutekeleza hii files ama kwa HatiJava. OK. Hivyo, huna kwamba, unaweza kupata aina hii ya gibberish. Ni tu mambo yote kuhusu HatiJava. Wewe si kweli kuwa kwa wasiwasi kuhusu hilo hivi sasa. Na kama unaweza kuona, tuna hii parens wazi, Pato la Taifa, parens karibu, na aina tu ya inaonekana kama mstari amri yetu, haki? Hivyo, nini tunataka do-- --So, Jambo la kwanza ni tunataka kuchagua mahali kuivunja. Hivyo, kuna mdudu moja katika mpango huu Kaisari kwamba mimi kuanzisha, kwamba tunakwenda kupata nje. Ni nini haina ni inachukua pembejeo Barfoo katika mechi zote, na kwa sababu baadhi ya haina mabadiliko ya A. Ni tu majani peke yake, Je kila kitu kingine sahihi, lakini barua ya pili A bado unchanged. Hivyo, sisi ni kwenda kujaribu na takwimu kwa nini kuwa ni. Hivyo, jambo la kwanza kawaida wanataka kufanya wakati wowote kuanza GDB ni takwimu nje ambapo kuivunja. Hivyo Kaisari ni mpango pretty mfupi. Sisi tu kuwa na kazi moja, haki? Ilikuwa ni kazi yetu katika Kaisari nini? Kuna kazi moja tu, Kuu haki ni? Kuu ni kazi kwa ajili ya programu yako yote. Kama hakuwa na Kuu, mimi ili kuwa na wasiwasi kidogo sasa hivi, lakini Natumaini wote walikuwa Kuu huko. Hivyo, nini tunaweza kufanya sisi ni wanaweza kuvunja tu Kuu, tu kama hiyo. Hivyo, anasema, OK. Sisi kuweka moja wetu breakpoint huko. Hivyo, sasa jambo kukumbuka ni Caesar inachukua amri moja hoja line haki na hatujafanya kwamba popote bado. Hivyo, nini kufanya ni wakati wewe kweli kwenda kukimbia mpango, mpango wowote kwamba wewe ni mbio katika GDB kwamba mahitaji ya mstari amri hoja, wewe kwenda pembejeo wakati wewe kwanza kuanza mbio hiyo. Hivyo, katika kesi hii, sisi kufanya Kukimbia na ufunguo wa tatu. Na itakuwa kweli kuanza. Hivyo, kama unaweza kuona hapa, tuna Kama RC si sawa na 2. Hivyo kama wewe guys wote wana kwamba faili kwamba mimi alimtuma nje up utaona kwamba hiyo ni kama mstari wa kwanza kazi yetu kuu, haki? Ni kuangalia kuona kama tuna idadi sahihi ya hoja. Hivyo, kama wewe wanashangaa kama RC ni sahihi, unaweza kufanya kitu kama this RC. RC ni mbili, ambayo ni kile sisi inatarajiwa, haki? Hivyo, tunaweza kwenda Next, na kuendelea kupitia. Hivyo, tuna baadhi ya muhimu huko. Na tunaweza magazeti nje ufunguo wetu kuhakikisha kwamba ni sahihi. Kuvutia. Si kabisa kile sisi inatarajiwa. Hivyo, jambo moja kwa kutambua na GDB pia, ni kwamba si kweli mpaka hit Next, kwamba line ya kuwa wewe tu aliona ni kweli kunyongwa. Hivyo, katika kesi hii muhimu haijawahi kupewa bado. Hivyo, muhimu ni baadhi ya thamani ya takataka kwamba unaweza kuona chini huko. Hasi $ 120-- --It ya bilioni moja na kitu mambo isiyo ya kawaida haki? Ni si muhimu kwamba sisi ilivyotarajiwa. Lakini kama sisi hit Next, na kisha sisi kujaribu na this muhimu, ni ya tatu. Kila mtu kuona kwamba? Hivyo, kama wewe kupata kitu kwamba wewe ni kama, kusubiri. Hii ni kabisa makosa, na mimi sijui jinsi hili lingetokea kwa sababu yote nataka kufanya ni kuwapa posta, kutofautiana, kujaribu kupiga Next, jaribu uchapishaji tena, na kuona kama kwamba kazi. Kwa sababu ni kwenda tu kutekeleza na kweli hawawajui kitu baada ya wewe kugonga Next. Mantiki kwa kila mtu? Uh huh? SPIKA 2: Wakati random namba haina maana gani? SPIKA 1: Ni tu random. Ni tu takataka. Ni tu kitu ambacho yako kompyuta Watapiga hawawajui. Baridi. Hivyo, sasa tunaweza kusonga kupitia, na hivyo sasa tuna hii Nakala GetString wazi. Hivyo, napenda tu kuanzisha nini kitatokea wakati sisi kugonga Ifwatayo hapa. GDB yetu aina ya kutoweka, haki? Hii ni kwa sababu GetString sasa utekelezaji, haki? Hivyo, wakati tuliona Nakala wazi ni sawa na GetString, parens wazi na parens, na sisi hit Next, ambayo ina kweli kunyongwa sasa. Hivyo, ni kusubiri kwa sisi pembejeo kitu. Hivyo, sisi ni kwenda pembejeo chakula yetu ambayo ni nini ni kushindwa kama niliwaambia na kwamba tu anasema kwamba ni kumaliza utekelezaji, kwamba kufungwa bracket ina maana ni exiting nje ya kitanzi. Hivyo, tunaweza kugonga Next, na sasa, kama mimi nina uhakika wewe ni wote ukoo na Kaisari, hii ni, nini mstari huu kwenda kufanya. Ni kwa Int mimi ni sawa na 0, N sawa Strlen, Nakala wazi, na kisha Mimi ni chini ya n, mimi, pamoja, pamoja. Ni kitanzi hii kwenda kufanya nini? Kufungua ujumbe wako. Baridi. Hivyo, hebu kuanza kufanya hivyo. Hivyo, lazima hali hii mechi, kwa moja wetu wa kwanza? Kama ni B, ni Nakala wazi I. Sisi Unaweza kupata taarifa kuhusu wenyeji wetu. Kwa hiyo, mimi ni sifuri, na kama sita, ambayo tunatarajia, na muhimu yetu ni tatu. Wote kwamba kufanya maana, haki? Wale idadi ni wote nini hasa wanapaswa kuwa. Hivyo, hum? SPIKA 3: Nina namba random kwa ajili ya mgodi. SPIKA 1: Naam, tunaweza check-- --we unaweza kuzungumza juu ya kwamba katika pili. Lakini unapaswa kuwa kupata hii. Hivyo, kama tuna mtaji B kwa moja wetu wa kwanza, hali hii lazima kukamata, haki? Hivyo, kama sisi hit Next, tunaona kwamba hii Kama kweli executes. Kwa sababu kama wewe ni kufuatia pamoja katika kanuni yako, mstari huu hapa, ambapo Nakala wazi mimi ni kubadilishwa kwa hesabu hii, executes tu kama Kama hali ni haki sahihi? GDB ni kwenda tu kuonyesha mambo ambayo ni kweli utekelezaji. Hivyo kama hali hii Kama si alikutana, ni tu kwenda ruka kwa mstari wa pili. OK? Hivyo, tuna hiyo. Bracket hii ina maana ni imefungwa nje ya kitanzi sasa. Hivyo, ni kwenda kuanza tena. Tu kama hiyo. Hivyo, kwamba tunaweza kupata maelezo kuhusu wenyeji wetu hapa, na tunaona kwamba yetu ya kwanza barua imebadilika, haki? Ni sasa E, kama ni lazima. Hivyo, tunaweza kuendelea. Na sisi kuwa na kuangalia hii. Na kuangalia hii lazima kazi, haki? Ni A. Ni lazima iliyopita barua tatu mbele. Lakini kama taarifa, sisi kupata kitu tofauti. Hivyo katika kesi hii hapa, ni hawakupata yake, na hivyo mstari huu kunyongwa, ambayo iliyopita B. wetu Lakini, katika kesi hii hapa, tuna kwamba tu skipped yake, na akaenda [? L Siff. ?] Hivyo kitu kinaendelea huko. Nini anayewambia ni kwamba, Tunajua kwamba ni lazima kupata hapa, lakini siyo. Je, mtu yeyote kuona nini wetu Tatizo ni kwamba katika mstari? Ni jambo dakika sana. Na pia unaweza kuangalia code yako. Ni pia line-- kusahau kile line ni katika there-- lakini ni katika [inaudible]. Ndiyo? SPIKA 4: Ni juu ya kubwa kuliko ukurasa kama wewe kusoma katika kitabu. SPIKA 1: Hasa. Hivyo, HatiJava hakuweza kuwaambia kwamba, lakini HatiJava inaweza kupata wewe chini ya mstari unajua si kazi. Na wakati mwingine, wakati hasa baadaye katika muhula, wakati wewe ni kushughulika na mia, a mia chache mistari ya kificho, na wewe sijui ambapo ni kushindwa, hii ni njia kuu ya kufanya hivyo. Hivyo, sisi kupatikana mdudu yetu. Unaweza kurekebisha katika faili yako, na kisha unaweza kukimbia tena, na kila kitu ingekuwa kazi kikamilifu. Na jambo kubwa ni hii inaweza kuonekana kama, sawa. Yeah. Baridi. Alijua wewe ni kuangalia kwa. Hivyo, wewe alijua nini cha kufanya. GDB inaweza kuwa super kusaidia kwa sababu wewe unaweza magazeti nje ya mambo hayo yote kuwa wewe bila. Ni muhimu zaidi kuliko printf. Jinsi wengi matumizi kama printf kauli kufikiri ambapo mdudu alikuwa, haki? Hivyo, pamoja na hayo, huna kushika kwenda nyuma, na kama kutoa maoni katika Printf, au kutoa maoni nje, na kufikiri nini unapaswa kuwa uchapishaji. Hii kweli tu utapata hatua kupitia, magazeti nje mambo kama wewe kwenda kupitia, hivyo, unaweza kuchunguza jinsi wao kubadilika katika muda halisi, kama mpango wako ni mbio. Na haina kuchukua kidogo kidogo ya kupata kutumika. Napenda sana kupendekeza tu aina kuwa kidogo kuchanganyikiwa na ni kwa hivi sasa. Kama wewe kutumia muda wa saa zaidi ya wiki ijayo kujifunza jinsi ya kutumia GDB, wewe kuokoa mwenyewe hivyo muda mwingi baadaye. Na halisi. sisi tunasema hii kwa watu kila mwaka, na Nakumbuka wakati mimi alichukua darasa, mimi nilikuwa kama, mimi itakuwa vizuri. Hakuna Pset 6 alikuja juu na mimi nilikuwa kama, mimi nina gonna kujifunza jinsi ya kutumia GDB kwa sababu mimi si kujua nini kinaendelea hapa. Hivyo kama wewe kuchukua muda ili kutumia kwenye programu ndogo kwamba wewe ni kwenda kuwa na kazi, kama kazi kupitia kitu kama Visionare, kama hii. Au kama unataka mazoezi ya ziada, mimi nina uhakika Mimi naweza kuja na mipango Buggy, kwa wewe Debug kama Ningependa. Lakini kama wewe tu kuchukua muda kupata kutumika yake, tu kucheza karibu na hayo, itakuwa kweli kuwatumikia ninyi pia. Na ni kweli moja ya mambo ambayo wewe tu kuwa na kujaribu, na kupata mikono yako chafu na, kabla ya kweli kuelewa. Mimi kwa kweli kuelewa tu mara moja Mimi nilikuwa na Debug mambo na hayo, na ni kiasi nicer kuwa na wazo la jinsi ya Debug mapema kuliko baadaye. OK. Baridi. Najua kwamba aina ya kama Bila shaka ajali katika GDB, na mimi dhahiri kazi ya kupata haya kwa kuangalia kubwa wakati ujao. Baridi. Hivyo, kama sisi kurudi nyuma kwa PowerPoint wetu. Ni hii kwenda kufanya kazi? Awh. Ndiyo. OK. Hivyo, kama wewe milele haja yoyote ya wale tena, kuna orodha. Hivyo binary Search, ambayo kila mtu anakumbuka tamasha kubwa la David ripping vitabu simu katika nusu. Mimi si kweli kupata vitabu simu tena, kwa sababu kama ambapo wewe kupata vitabu simu siku hizi? Mimi kwa kweli sijui. Search Binary. Je, mtu yeyote kumbuka jinsi binary Search matendo? Mtu yeyote wakati wote? Yeah? SPIKA 5: Unajua wakati ukiangalia ambayo nusu itakuwa katika, Kulingana na kwamba, na kujikwamua nusu nyingine. SPIKA 1 Hasa. Hivyo, Binary Search, ni aina ya a-- --we kama simu yake kugawanya na kushinda. Hivyo, nini utasikia kufanya ni utasikia kuangalia katikati, na utaona kama ni mechi nini wewe kutafuta. Na kama hana, basi wewe kujaribu kufikiri, ni kwenda kuwa kushoto nusu au nusu ya haki. Hivyo, hii inaweza kuwa kama wewe ni kuangalia katika kitu ambacho alphabetized, unaweza kuona, oh. Je Allison kuja kabla ya M? Ndiyo. Hivyo, tunakwenda kuangalia nusu ya kwanza. Au inaweza kuwa kama na namba. Chochote ambacho unaweza kulinganisha, inaweza kutatuliwa. Unaweza kutumia search binary juu. Hivyo, mtu yeyote kumbuka hii graph au nini hii ni? Ni asymptotic Utata. Hivyo, graph hii tu inaeleza muda gani inachukua wewe kutatua tatizo kama kuongeza idadi ya mambo kwamba wewe ni kutumia. Hivyo, tuna N, ambayo ni ya muda linear. Kama N juu ya mbili, ambayo ni kidogo bora, bado inakua super haraka. Na kisha sisi Ingia, ambayo ni kile sisi kufikiria Binary Search. Kama sisi taarifa kama tatizo lako anapata sana na kubwa, inachukua muda kutatua hilo haina kweli kuongeza kwamba mengi. Ni kama kulinganishwa hapa katika mwanzo. Wewe ni kama, sawa. Chochote hapa haina kweli jambo ambalo moja sisi kutumia, lakini kupata kufanyika kwa milioni, bilioni. Wewe ni kujaribu kupata some-- --you're kujaribu kupata sindano katika haystack. Nadhani unataka tatizo hili. Unataka utata huu, si linear kwa sababu kwa wote kujua wako gonna kuwa kutafuta njia ya kila mtu binafsi sindano, jambo la nyasi, kujaribu kuangalia kwa sindano yako. Na kwamba si pia furaha kwa maoni yangu. Mimi kama kufunga. Mimi kama ufanisi. Na kama hardworking wanafunzi you guys ni, unajua kazi nadhifu, si vigumu aina jambo, jinsi wanaweza kufanya up algorithms haya. Hivyo, sisi ni kwenda kutembea kupitia mfano tu haraka. Nadhani wewe guys wanapaswa kuwa mkono juu ya binary Search, lakini katika kesi ya mtu ni kidogo fuzzy, wanataka kuimarisha yake, sisi ni kwenda tu kupitia mfano hapa. Hivyo, sisi ni kuangalia kwa kama safu ina saba. Hivyo, jambo la kwanza sisi kufanya ni kuangalia katika katikati, haki? Na pia wewe ni kwenda kuwa coding Binary Search katika tu ya pili. Hivyo, ni kwenda kuwa na furaha. Hivyo sisi kuangalia katika katikati arrays kidogo 3. Je 3 sawa 7? Hana. Ni sita. Hivyo, ni chini ya au zaidi ya saba? Chini ya. Ndiyo. Nzuri kazi guys. Najisikia kama mimi lazima kuwa pipi kwa sababu mimi wanataka kutupa nje katika yadi. Ni kile Mimi kwenda kufanya wiki ijayo. Itakuwa kuwalinda watu mkali. Hivyo, sisi kutupa mbali kwamba nusu ya kwanza, haki? ilikuwa chini ya. Tunajua kwamba kila kitu juu ya kwamba upande wa kushoto ni kwenda kuwa chini ya kile sisi ni kweli kuangalia kwa. Hivyo, hakuna haja ya makini na hilo. Tu kusahau kuhusu hilo. Hivyo, sasa sisi kuangalia upande wetu wa kulia, na sisi kuangalia katikati zaidi ya hapo, na sasa ni tisa. Hivyo, 9 is-- --Everyone? Zaidi kuliko yale sisi ni kutafuta, haki? Hivyo, sisi ni kwenda kutupa mbali kila kitu na haki. Kama hiyo. Sasa, sisi ni wa kushoto na ni moja. Hivyo sisi kuangalia, hii ni moja nini sisi ni kuangalia kwa? ni. Sisi kupatikana nini sisi alitaka. Hivyo sisi ni kosa. Bilinear Search. Na kama taarifa, sisi alikuwa pembejeo saba huko. Ni alichukua sisi tu kama mara tatu, lakini kama wewe ni kufanya kama bilioni, you guys kujua jinsi hatua nyingi ingekuwa kuchukua kama tulikuwa mambo bilioni nne? Guesses yoyote? Ni 32. Hatua 32 kupata kitu katika bilioni nne kipengele safu kwa sababu ya mamlaka ya mbili. Hivyo mbili ni 32, ni bilioni nne. Hivyo pretty mambo jinsi bado uko ndani ya kama idadi haki ndogo ya hatua kupata kitu katika mambo bilioni nne. Kadhalika kwamba kumbuka, tuko kwenda kanuni hii hivyo guys unaweza kweli aina ya kuona jinsi hii matendo. Haki wote, hivyo wewe guys unaweza kanuni. Mimi nina kwenda basi wewe guys kuzungumza kwa muda kidogo. Kupata kujua watu karibu na wewe, ambayo ni kile mtu alitaka kutoka sehemu ya mwisho. Hivyo kupata kujua watu karibu na wewe. Kuzungumza kwa muda kidogo. Na mimi wote wanataka kutoka kwenu guys sasa hivi ni tu kujaribu kujenga muhtasari wa pseudocode. OK? Whoa. Yote nataka kutoka guys ni uko tu kwenda kujaza katika kesi hii wakati. Hivyo mimi kuweka haya juu na mipaka ya chini ambayo kuwakilisha mwanzo na mwisho wa safu yetu. Na wewe ni kwenda kweli kitanzi kupitia na kufikiri nini sisi ni kufanya ndani ya hii kitanzi wakati. Hivyo kama unaweza kufikiri out-- nina ladha there-- nini ni kesi kwamba sisi hapa? Hivyo kama unataka kufikiri kesi, sisi pseudocode wale na kisha tutaweza kweli kanuni ya yao. Na ni kwenda kuwa, mimi kufikiri, hopefully utakuwa kuwa rahisi kidogo kuliko wewe kutarajia. Sababu si kificho kwamba kiasi, kweli, ambayo ni kweli baridi. Mm-hm? STUDENT: [inaudible]? Mwalimu: Ndiyo. Kulikuwa na kitu kupata katikati. STUDENT: Hivyo tunaweza kutumia hiyo. OK. Mwalimu: Perfect. Hivyo kwamba ni jambo la kwanza tunahitaji kufanya. Hivyo kupata katikati. Kubwa. Hivyo una wazo la jinsi sisi anaweza kweli kupata katikati na kanuni? STUDENT: Yeah. n juu ya 2? Mwalimu: Hivyo n juu ya 2. Hivyo jambo moja kukumbuka ni kwamba yako juu na chini ya mipaka kubadilika. Sisi kuendelea constricting sehemu safu sisi ni kuangalia kwa. Hivyo n juu ya 2 itakuwa kazi tu kwa jambo la kwanza sisi kufanya. Hivyo kuchukua juu na chini katika akaunti, jinsi gani sisi kupata kwamba kipengele katikati? Sababu tunataka katikati kati ya juu na chini, haki? Mm-hm? STUDENT: [inaudible]. Mwalimu: Hivyo tuna baadhi ya katikati. Na utakuwa juu pamoja na chini zaidi ya 2. Kutisha. Kuna sisi kwenda. Moja line ya chini. You guys ni juu ya njia yako. Hivyo sasa kwamba tuna yetu katikati, je tunataka kufanya? Tu kwa ujumla. Huna ya kificho yake. Ndiyo. STUDENT: [inaudible]? Mwalimu: Hivyo ni pamoja na kwa sababu wewe ni kutafuta wastani kati ya mbili wao. Hivyo kama wewe kufikiria yao kama aina la kuongeza katika kutoka pande, kufikiri juu yake kama wewe mbinu katikati, unataka kama hiyo. Hivyo kama wewe walikuwa kwenye upande wa katikati, na sisi kama 5 na 7. Wakati kuongeza yao pamoja nanyi kupata 12, kugawanya na 2, ni 6. Wakati mwingine ni vigumu kueleza kwa nini kwamba kazi, lakini kama wewe kazi kwa njia ya mfano mwingine, itakusaidia kufikiri kama ni lazima kuwa pamoja au bala. Ndiyo. STUDENT: [inaudible] hasa katikati kama alikuwa na kesi ambapo kuna mengi ya namba ndogo na kama namba moja kubwa? Mwalimu: Hivyo wote unahitaji ni katikati ya safu. Hivyo kama wewe alikuwa rundo la idadi ndogo na kisha moja ya simu kweli kubwa mwishoni, haijalishi. Mambo ambayo yote ni kwamba wao ni yamepangwa, wewe tu unataka kuangalia katikati ya safu kwa sababu bado uko slicing tatizo yako katika nusu. Baridi. Hivyo sasa kwamba tuna katikati, je, sisi kufanya ijayo? STUDENT: Linganisha. Mwalimu: kulinganisha. Hivyo kulinganisha katikati kwa value_wanted. Baridi. Hivyo unaweza kuona hapa tuna thamani hii tunataka hapa. Kumbuka hii ni safu. Hivyo katikati inahusu index. Hivyo tunataka kufanya maadili ya katikati. Usisahau kama unataka kulinganisha, mbili sawa. Kufanya moja sawa wewe ni tu kwenda reassign yake, na kisha, bila shaka, ni itakuwa thamani unataka. Hivyo si kufanya hivyo. Hivyo sisi ni kwenda kuona kama maadili katikati ni sawa na thamani tunataka. Usisahau braces yako. Dropbox lazima kwenda mbali. Hivyo tunafanya nini katika kesi hii? Kama ni nini tunataka kurudi? Sisi ni kujaribu kusema. STUDENT: Magazeti mbali. Mwalimu: Naam, sisi hawataki magazeti mbali. Hivyo hii ni bool hapa, hivyo sisi unataka kurudi kweli au uongo. Sisi ni kusema, ni idadi hii [? RRA? ?] Hivyo kama ni, sisi tu kurudi kweli. Kama naweza Spell ya kweli. STUDENT: Kwa nini si wewe kurudi sifuri? Mwalimu: Hivyo unaweza kurudi zero kama alitaka. Lakini katika kesi hii kwa sababu kazi yetu anarudi bool, tunahitaji kurudi ama kweli au uongo. STUDENT: Wakati uko akisema kujieleza bulin, unaweza kuweka sawa na uongo? Kama kama mimi nataka kusema, kama hali hii si alikutana, kama ni ya juu ni sawa na ya uongo. Je, ni kuelewa kama wewe tu kuweka uongo kwa upande mwingine? Mwalimu: Yeah. Hivyo kweli kama wewe ni milele kufanya kitu kama ni ya juu au ni ya chini, kwamba anarudi kweli au uongo na ni kweli style mbaya kwa kusema sawa sawa kweli au sawa sawa uongo. Unataka kutumia kwamba matokeo kama yenyewe kama hundi yako. Si nini nilitaka. Hiyo ni nini nilitaka. Hivyo katika kesi ya wewe ni kuuliza kuhusu kitu kama kuokoa hii katika c. Hivyo kama tuna int kuu (utupu) na kitu kama hiki. Na una kama ni ya juu baadhi ya pembejeo na wewe ni kuuliza kama unaweza kufanya kitu kama hii? Haki? STUDENT: Mimi alikuwa anajaribu kufanya hivyo [inaudible]. Kwa sababu kama it's-- Mwalimu: Haki. Hivyo unataka hii kuwa ni uongo, haki? STUDENT: Yeah. Mwalimu: Hivyo katika kesi hii wanataka kutekeleza kama si kweli. Hivyo jambo zuri kufanya kuna hii. Hivyo kumbuka Moderators hatua inaashiria mambo? Ni anasema [inaudible] maana yake si. Hivyo kama sisi kuangalia tu sehemu hii hapa, wewe d kusema kwamba kutathmini kwa uongo kama unataka kwa. Si ya uongo ni kweli ambayo ina maana hii ingekuwa nitafanya. Je, hiyo mantiki? STUDENT: Yeah. Mwalimu: Ajabu. OK. Hivyo tunaweza tu kurudi kweli katika kesi hii. Hivyo sasa tuna wengine wawili kesi katika kesi hii. Je, ni yetu kesi nyingine mbili? Hebu tu kufanya hivyo kwa njia hii. Basi hebu kuanza na mwingine kama maadili katika katikati ni chini ya thamani tunataka. Hivyo thamani yetu katikati ni chini kuliko thamani ya kwamba sisi ni kuangalia kwa. Hivyo ambayo amefungwa kufanya wewe Nadhani tunataka update? Juu au chini? Juu? Hivyo ambayo upande wa safu sisi ni kwenda kuwa na kuangalia? STUDENT: chini. Mwalimu: Sisi ni sisi kwenda kuwa na kuangalia upande wa kushoto. Hivyo mwingine kama thamani kidogo kidogo. Hivyo thamani yako katikati hapa ni chini ya nini tunataka. Hivyo tunataka kuchukua upande wa safu yetu ya haki. Hivyo sisi ni kwenda update chini amefungwa yetu. Hivyo tutaweza reassign chini yetu. Na unafikiri nini chini lazima? STUDENT: thamani ya kati? Mwalimu: Hivyo value-- katikati STUDENT: Plus 1. Mwalimu: --plus 1. Yeyote anaweza kuniambia kwa nini tuna kuwa pamoja na 1? STUDENT: [? Hakuna thamani?] ni zaidi sawa na hayo. Mwalimu: Haki. Kwa sababu sisi tayari kujua kwamba thamani yetu katikati ni si sawa na na tunataka kuwatenga ni kutoka utafutaji wote baadae. Kama kusahau kwamba pamoja na 1, hii itakuwa kama kitanzi kwa muda usiojulikana. Na utasikia tu kuwa hawakupata katika usio kitanzi na kisha utasikia segfault na mambo kwenda mbaya. Hivyo siku zote kuhakikisha kwamba wewe si ikiwa ni pamoja na thamani ya kwamba wewe tu inaonekana katika. Hivyo sisi kuchukua huduma ya kwamba pamoja na pamoja na 1. Hivyo sasa tuna hali yetu iliyopita ambayo mimi daima kwa ajili ya usalama unaweza kuangalia hapa, mwingine kama thamani katika katikati ni mkubwa kuliko thamani tunataka. Hiyo ina maana kwamba tunataka mkono wa kushoto nusu. Hivyo ambayo moja ni sisi kwenda update? Juu. Na ni hii moja kwenda sawa nini? Katikati minus 1 kwa sababu, Bila shaka, tunataka kuhakikisha kwamba sisi siyo kuangalia kwamba thamani katikati tena. Na kisha sisi kuwa nayo. Hiyo ni. Hayo ni yote binary tafuta ni. Ni si mbaya, haki? Ni kama mistari 10 ya kificho na nafasi nyeupe. Hivyo sana nguvu, muhimu sana, utakuwa kutumia hiyo katika moja ya psets yako ya baadaye. Hii labda si moja, lakini baadaye. Hivyo kujifunza. Kupenda. Ni kutibu wewe vizuri. Hivyo haina mtu yeyote kuwa yoyote maswali juu ya kutafuta binary? Ndiyo. STUDENT: Je, ni jambo kama n yako ni hata au isiyo ya kawaida? Mwalimu: Hakuna Sababu sisi kuwatupia katikati kama int, itakuwa tu butu yake. Hivyo itakuwa kukaa integer na itakuwa hatimaye aina kupitia kila kitu. Hivyo huna kuwa na wasiwasi juu ya hilo. Kila mtu mzuri? Kutisha. Baridi. Hivyo, wewe guys got hii. Slideshow. Hivyo kama sisi walikuwa wanazungumza juu, najua Daudi zilizotajwa utata runtimes. Hivyo katika kesi bora, ni tu moja, ambayo sisi kuwaita wakati mara kwa mara. Yeyote anaweza kuniambia kwa nini hiyo inaweza kuwa ni? Ni aina gani ya mazingira ingekuwa kwamba leda? Mm-hm. STUDENT: [inaudible] first-- Mwalimu: Hivyo katikati kuwa kipengele kwanza kwamba sisi kuja, haki? Hivyo aidha safu ya moja au chochote sisi ni kuangalia kwa tu hutokea kwa kuwa Smack dab katikati. Hivyo hiyo ni kesi yetu bora. Kupata katika matatizo halisi, pengine si kwenda kufikia [inaudible] kwamba mara nyingi. Nini kuhusu kesi yetu mbaya? Wetu kesi mbaya zaidi ni logi n. Na kwamba ina nini na nzima mamlaka ya jambo mbili kwamba mimi aliyesema kuhusu. Hivyo katika kesi mbaya itakuwa na maana kwamba alikuwa na kuwakata safu chini mpaka ilikuwa kipengele cha moja. Hivyo tulikuwa na kuwakata chini katika nusu mara nyingi kama sisi pengine inaweza. Hiyo ni kwa nini ni gogo n kwa sababu wewe tu kuweka kugawa kwa mbili. Hivyo mawazo, mambo haja ya kujua kama wewe ni milele kwenda kutumia search binary. Mambo yako lazima kutatuliwa. Wana kutatuliwa kwa sababu hiyo ndiyo njia pekee ya unaweza kujua kama wewe ni uwezo kutupa nje nusu ya hiyo. Kama alikuwa mfuko huu jumbled ya idadi na wewe kusema, OK, mimi nina kwenda kuangalia katikati idadi na idadi mimi nina kuangalia kwa ni chini ya kwamba, mimi nina kwenda tu kwa kiholela kutupa nje nusu moja. Bila kujua kama yako namba katika nusu nyingine. Orodha yako ina kutatuliwa. Kama vile, hii inaweza kuwa kwenda mbele kidogo, lakini unahitaji kupata random. Unahitaji kuwa na uwezo wa tu kwenda kuwa kipengele katikati. Kama una traverse kupitia kitu au inachukua wewe hatua za ziada kupata kwamba kipengele katikati, siyo kuingia n tena kwa sababu wewe ni kuongeza kazi zaidi ndani yake. Na hii itafanya kidogo maana zaidi katika wiki mbili, lakini mimi tu aina ya alitaka utangulizi, kukupa guys wazo la nini kuja. Lakini hayo ni mbili mawazo muhimu kwamba unahitaji kwa orodha binary. Kuhakikisha ni vyema. Hiyo ni moja kubwa kwa nyie hivi sasa. Na juu ya kwamba tunaweza kwenda katika mapumziko ya aina yetu. Hivyo vinne sorts-- Bubble, insertion, uteuzi, na kuunganisha. Wao ni kila aina ya baridi. Kama wewe guys kuamua kuchukua CS 124, itabidi kujifunza kuhusu kila aina ya aina. Na kama wewe ni shabiki XKCD, kuna ni kweli baridi Comic kuhusu kama aina kweli ufanisi, ambayo mimi sana kupendekeza wewe kwenda kuangalia. Mmoja wao ni kama hofu ya aina, ambayo ni kama, oh no, kurudi random safu. Shutdown mfumo. Kuondoka. Hivyo ucheshi geeky daima ni nzuri. Hivyo haina mtu yeyote kumbuka aina ya kama wazo tu kwa ujumla ya jinsi Bubble aina ya kazi. Unakumbuka? STUDENT: Yeah. Mwalimu: Nenda kwa ajili yake. STUDENT: Hivyo wewe ni kwenda kwa njia na kama ni kubwa zaidi, basi byta mbili. Mwalimu: Mm-hm. Hasa. Hivyo tu iterate kupitia. Kuangalia namba mbili. Kama moja kabla ni kubwa ya moja baadaye, wewe tu wabadilishane yao ili katika njia hii yote ya idadi kubwa Bubble hadi kufikia mwisho wa orodha na namba zote za chini ya Bubble chini. Je, kuonyesha guys baridi sauti athari kuchagua video? Ni aina ya baridi. Hivyo kama Robert alisema tu, algorithm kwamba wewe tu hatua kupitia orodha, swapping maadili karibu kama wao siyo katika utaratibu. Na kisha tu kuendelea kurudia mpaka huna kufanya swaps yoyote. Hivyo si mbaya, haki? Hivyo sisi tu mfano wa haraka hapa. Hivyo hii ni kwenda kutatua nao katika wakipanda ili. Hivyo wakati sisi kwenda kwa njia ya kwanza muda, sisi kuangalia njia ya nane na sita ni wazi si ili, sisi wabadilishane yao. Hivyo kuangalia moja ijayo. Nane na nne si kwa utaratibu. Wabadilishane yao. Na kisha nane na mbili, wabadilishane yao. Kuna sisi kwenda. Hivyo baada ya kupita yako ya kwanza, kujua kwamba idadi kubwa yako ni kwenda kuwa njia yote saa ya juu kwa sababu ni tu itakuwa daima kubwa kuliko kila kitu kingine na ni kwenda tu kwa Bubble up njia yote ya mwisho huko. Gani kwamba inafanya hisia kila mtu? Baridi. Hivyo basi sisi kuangalia kupita yetu ya pili. Sita na nne, kubadili. Sita na mbili, kubadili. Na sasa tuna mambo kadhaa katika utaratibu. Hivyo kwa kila kupita kwamba sisi kufanya kupitia orodha yetu nzima, tunajua kwamba kama kwamba namba wengi mwishoni mapenzi yamekuwa yamepangwa. Hivyo sisi kufanya kupita ya tatu, ambayo ni wabadilishane moja. Na kisha juu ya nne zetu kupita, tuna sifuri inafaa. Na hivyo tunajua kwamba yetu safu imekuwa yamepangwa. Na kwamba ni kubwa Jambo na Bubble aina. Tunajua kwamba wakati sisi sifuri swaps, kwamba ina maana kwamba kila kitu ni ili kukamilisha. Ni aina ya jinsi sisi kuangalia. Hivyo sisi pia ni kwenda na kanuni Bubble aina ambayo pia ni kuwa mbaya. Hakuna wa hizi ni mbaya. Najua wanaweza kuonekana kidogo inatisha. Najua wakati mimi alichukua darasani, hata wakati mimi ilikuwa kufundisha darasa kwa mara ya kwanza mwaka jana, Mimi nilikuwa kama, jinsi gani mimi kufanya hivyo? Inafanya hisia katika nadharia, lakini jinsi gani sisi kwa kweli kufanya hili? Ambayo ni kwa nini mimi pia wanataka kutembea kupitia kificho na nyie hapa. Hivyo nina pseudocode kwa nyie wakati huu. Hivyo tu kuweka hii katika akili kama sisi ni juu ya mpito juu. Hivyo tuna baadhi ya kukabiliana na kwamba anaendelea kufuatilia swaps yetu, sababu tunahitaji kuhakikisha kwamba sisi ni kuangalia kwamba. Na sisi iterate safu nzima kama sisi tu alivyofanya kwa mfano huu. Kama kipengele kabla ni kubwa kuliko kipengele baada ambapo sisi ni saa, sisi wabadilishane yao na sisi nyongeza wetu kukabiliana kwa sababu haraka kama sisi byta, tunataka basi kukabiliana yetu kujua kwamba. Maswali yoyote huko? Kitu inaonekana funny zaidi ya hapa. STUDENT: Je kuweka kukabiliana na sifuri kila wakati kwenda kwa njia ya kitanzi? Je, si kuweka kwenda nyuma kwa sifuri kila wakati? Mwalimu: Si lazima. Hivyo kile kinachotokea ni sisi kwenda kwa njia ya hapa. Hivyo kufanya wakati, kumbuka, hii nitafanya mara moja bila kushindwa. Hivyo ni kwenda kuweka kukabiliana sawa na sifuri, basi ni kwenda iterate kupitia. Kama iterates kupitia, itakuwa update kukabiliana. Kama updates kukabiliana, wakati ni kosa, wakati ni kufikiwa mwisho wa safu, kama orodha yetu haijawahi sorted, kukabiliana itakuwa wamekuwa updated. Hivyo basi ni hundi ya hali na anasema, OK, ni kukabiliana mkubwa kuliko sifuri. Kama ni, kufanya hivyo tena. Unataka upya ili wakati kupitia, kukabiliana ni sawa na sifuri. Kama kwenda kupitia Iliyopangwa safu, hakuna mabadiliko, hii inashindwa, na wewe kurudi orodha Iliyopangwa. Je kwamba inafanya hisia? STUDENT: Ni huenda katika kidogo. Mwalimu: OK. Kama kuna yoyote nyingine swali kwamba anakuja juu. Ndiyo. STUDENT: Nini ingekuwa kazi kuwa kwa swapping mambo? Mwalimu: Hivyo tunaweza kweli kuandika kwamba kama sisi ni kwenda hivi sasa. Baridi. Kadhalika kwamba kumbuka, Alison ni kwenda kubadili nyuma kwa appliance. Ni kwenda kuwa na furaha. Na tuna nzuri wetu Bubble aina jambo hapa. Hivyo mimi tayari alifanya baiskeli kupitia safu. Tuna swaps yetu kwamba ni sawa na sifuri. Hivyo tunataka wabadilishane karibu mambo kama uko nje ya utaratibu. Hivyo jambo la kwanza tunahitaji je ni iterate kupitia safu yetu. Hivyo ni jinsi gani unadhani sisi nguvu iterate kupitia safu yetu? Sisi kwa ajili na i sawa 0. Tunataka i kuwa chini kuliko n minus 1 bala k. Na mimi itabidi kueleza kwamba katika pili. Hivyo hii ni optimization hapa ambapo, kumbuka jinsi mimi alisema baada ya kila kupita kupitia safu sisi kujua kwamba chochote ni on-- Hivyo baada ya kupitisha moja sisi kujua kwamba hii ni Iliyopangwa. Baada ya hupita mbili tunajua kwamba yote hii ni Iliyopangwa. Baada ya hupita tatu sisi kujua hiyo yamepangwa. Hivyo njia mimi nina iterating kupitia safu hapa, ni ni kuhakikisha tu kwenda kupitia kile sisi kujua ni zisizochambuliwa. OK? Hiyo tu optimization. Unaweza kuandika naively tu iterating kupitia kila kitu, ingekuwa tu kuchukua muda mrefu. Na hili kitanzi nne ni tu optimization nzuri kwa sababu tunajua kwamba kila baada ya kamili iteration kupitia safu hapa, kama kila kitanzi full hapa, tunajua kwamba moja zaidi ya mambo haya itakuwa kutatuliwa mwishoni. Hivyo hatuna wasiwasi kuhusu wale. Gani kwamba inafanya hisia kila mtu? Kwamba baridi kidogo hila? Hivyo katika kesi hiyo, kama sisi ni iterating kupitia, Tunajua kwamba tunataka kuangalia kama safu n na n pamoja na 1 ni kwa utaratibu. OK. Hivyo hapa ni pseudocode. Tunataka kuangalia kama safu n na N plus 1 ni kwa utaratibu. Hivyo nini kinaweza tuna huko? Ni kwenda kuwa baadhi masharti. Itakuwa kama. STUDENT: Kama safu n ni chini ya safu n pamoja na 1. Mwalimu: Mm-hm. Naam, chini ya au mkubwa kuliko. STUDENT: Kubwa kuliko. Basi tunataka wabadilishane yao. Hasa. Hivyo sasa sisi kupata katika nini utaratibu kwa ajili ya swapping yao? Hivyo sisi akaenda kwa njia ya ufupi huu, aina ya wabadilishane kazi wiki iliyopita. Je, mtu yeyote kumbuka jinsi kazi? Hivyo hatuwezi tu reassign yao, haki? Kwa sababu mmoja wao kupata waliopotea. Kama sisi alisema A ni sawa na B na kisha B ni sawa na A, kila ghafla wote wawili ni tu sawa na B. Hivyo kile sisi kufanya ni sisi kuwa na kutofautiana kwa muda kwamba kwenda kushikilia moja ya yetu wakati tuko katika mchakato wa swapping. Hivyo kile sisi ni sisi itabidi baadhi int temp ni sawa to-- unaweza hawawajui kwa namna yoyote moja unataka, tu kuhakikisha kuweka wimbo wa it-- hivyo katika kesi hii, mimi nina kwenda hawawajui kwa safu n pamoja na 1. Ili kwenda kushikilia chochote thamani ni katika kuzuia kwamba pili kwamba sisi ni kuangalia. Na kisha tunaweza kufanya ni tunaweza kwenda mbele na REASSIGN safu n pamoja na 1, kwa sababu tunajua kuwa na kwamba thamani ya kuhifadhiwa. Hii pia ni moja ya kubwa things-- sijui kama yoyote ya wewe alikuwa na masuala ambapo kama wewe kubadili mbili mstari wa kanuni ghafla mambo kazi. Ili ni muhimu sana katika CS. Ili kuhakikisha mchoro mambo ya nje kama inawezekana kama yale ni kweli yanatokea. Hivyo sasa tunakwenda reassign safu n pamoja na 1, kwa sababu tunajua kuwa na kwamba thamani ya kuhifadhiwa. Na tunaweza hawawajui kwamba safu n au katika kesi hii safu i. Vigezo wengi mno. OK. Hivyo sasa tumekuwa reassigned safu i plus 1 kwa sawa nini katika safu i. Na sasa tunaweza kurudi nyuma na hawawajui safu i na nini? Mtu yeyote? STUDENT: 10. Mwalimu: 10. Hasa. Na jambo moja iliyopita. Kama tuna swapped ni sasa, nini tunahitaji kufanya? Nini jambo moja hiyo ni kwenda kutuambia kama sisi milele kusitisha mpango huu? Nini inatuambia kwamba sisi kuwa na orodha Iliyopangwa? Kama hatuwezi kufanya swaps yoyote, haki? Kama swaps ni sawa na sifuri mwishoni mwa hii. Hivyo wakati wewe kufanya wabadilishane, kama sisi tu alifanya hapa, tunataka update swaps. Na najua kulikuwa swali mapema kuhusu gani unaweza kutumia zero au moja badala ya kweli au uongo. Na kwamba ni nini hii haina hapa. Hivyo hii anasema kama si swaps. Hivyo kama swaps ni sifuri, ambayo is-- mimi daima kupata ukweli wangu na falses yangu mchanganyiko up. Tunataka sisi kutathmini kwa kweli na siyo. Hivyo kama ni sifuri, basi ni uongo. Kama yanatofautiana kwa [? bang?] inakuwa kweli. Hivyo basi mstari huu executes. Ukweli na uongo na zeros na ndio kupata mambo. Tu kama wewe polepole kutembea njia hiyo itakuwa mantiki. Lakini kwamba ni nini hii kidogo kidogo ya kificho hapa gani. Hivyo hii hundi ya kuona Sisi tumefanya swaps yoyote. Hivyo kama ni kitu chochote badala sifuri, ni kwenda kuwa uongo na jambo zima ni kwenda kutekeleza tena. Baridi? STUDENT: Nini kuvunja kufanya? Mwalimu: Break tu mapumziko nje ya kitanzi. Hivyo katika kesi hii ingekuwa tu kama mwisho wa mpango na wewe ungekuwa tu kuwa na orodha yako Iliyopangwa. STUDENT: Amazing. Mwalimu: Samahani? STUDENT: Kwa sababu sisi awali kutumika imeandikwa 1 juu ya kuandikwa sifuri kuwasilisha kwamba kama ambayo kazi au la. Mwalimu: Yeah. Hivyo unaweza kurudi sifuri au 1. Katika kesi hiyo, kwa sababu sisi siyo kweli kufanya kitu chochote na kazi, sisi tu wanataka kuvunja. Sisi si kweli huduma kuhusu hilo. Brake ni nzuri kama pia ni kutumika kwa ajili ya kuvunja nje ya loops nne au hali ya kuwa wewe hawataki kuweka utekelezaji. Ni tu inachukua wewe nje ya yao. Ni kidogo ya nuance kitu. Najisikia kama kuna mengi ya mkononi utikisaji, kama itabidi kujifunza kuhusu hili hivi karibuni. Lakini itabidi kujifunza kuhusu hili hivi karibuni. Mimi ahadi. OK. Hivyo haina kila mtu kupata Bubble aina? Si mbaya sana. Iterate kupitia, wabadilishane mambo kutumia temp kutofautiana, na sisi ni kuweka wote huko? Baridi. Kutisha. OK. Nyuma PowerPoint. Maswali yoyote kwa ujumla kuhusu hizi hadi sasa? Baridi. Mm-hm. STUDENT: [inaudible] int kuu kawaida. Je, una kuwa na kwamba kwa hili? Mwalimu: Hivyo sisi walikuwa wanatafuta tu tu katika halisi kuchagua algorithm. Kama alikuwa ni ndani ya kama mpango kubwa, ingekuwa int kuu mahali fulani. Kulingana na pale kutumia algorithm hii, ingekuwa kuamua nini kuwa walirudi kwa hilo. Lakini kwa upande wetu, sisi ni madhubuti kuangalia jinsi hii haina kweli iterate kupitia safu. Hivyo hatuna wasiwasi kuhusu hilo. Hivyo sisi walikuwa wanazungumza kesi kuhusu bora na matukio kesi mbaya kwa ajili ya kutafuta binary. Hivyo ni muhimu pia kufanya kwamba kwa kila aina yetu. Hivyo nini unafikiri ni mbaya kesi Runtime ya Bubble aina? You guys kukumbuka? STUDENT: N minus 1. Mwalimu: N minus 1. Hivyo kwamba maana kuna n minus 1 kulinganisha. Hivyo jambo moja kutambua ni kwamba juu ya iteration kwanza, sisi kwenda kwa njia ya, sisi kulinganisha haya two-- hivyo hiyo ni 1. Hizi mbili, tatu, nne. Hivyo baada ya iteration moja sisi tayari kuwa na kulinganisha nne. Wakati Mimi kuzungumza juu Runtime na n. N inawakilisha idadi ya kulinganisha kama kazi ya vipengele wangapi tuna. OK? Hivyo sisi kwenda kwa njia ya, tuna nne. wakati ujao wewe kujua hatufanyi na utunzaji wa hii. Sisi kulinganisha hizi mbili, hizi mbili, hizi mbili, na kama hatukuwa na optimization kwamba na kitanzi nne kwamba mimi aliandika, ungekuwa kulinganisha katika hapa anyways. Hivyo ingekuwa kukimbia kwa njia ya safu na kufanya n kulinganisha n mara kwa mara, kwa sababu kila wakati sisi kukimbia kwa njia hiyo sisi aina ya jambo moja. Na kila wakati sisi kukimbia kwa njia ya safu, sisi kufanya n kulinganisha. Hivyo Runtime wetu kwa hili ni kweli n mraba, ambayo ni mbaya sana katika yetu kuingia mwisho kwa sababu kwamba ina maana kama sisi alikuwa na nne bilioni mambo, ni kwenda kuchukua sisi bilioni nne mraba badala ya 32. Hivyo si Runtime bora, lakini kwa baadhi ya mambo, unajua, kama wewe ni ndani ya mbalimbali fulani ya mambo Bubble aina hiyo inaweza kuwa faini ya kutumia. OK. Hivyo sasa ni nini bora kesi Runtime? STUDENT: sifuri? Au 1? Mwalimu: Hivyo 1 ingekuwa kuwa kulinganisha moja. Haki. STUDENT: N minus 1? Mwalimu: Hivyo, yeah. Hivyo n minus 1. Wakati wowote na dhana kama n bala 1, sisi huwa na kuacha tu ni mbali na sisi tu kusema n kwa sababu una kulinganisha kila these-- kila jozi. Hivyo itakuwa n minus 1, ambayo sisi tunatarajia kusema tu ni takriban n. Wakati wewe ni kushughulika na Runtime, kila kitu ni katika approximates. Muda mrefu kama exponent ni sahihi, wewe ni nzuri. Hiyo ni jinsi sisi kukabiliana nayo. Hivyo kwamba kesi bora ni n, ambayo ina maana kwamba orodha tayari Iliyopangwa, na wote sisi kufanya ni kukimbia kupitia na kuangalia kwamba ni vyema. Baridi. Wote haki. Hivyo kama unaweza kuona hapa, sisi tu kuwa na baadhi ya michoro zaidi. Hivyo n squared. Furaha. Mbaya zaidi kuliko n kama sisi kuona, na kiasi, mbaya zaidi kuliko logi 2n. Na kisha pia kupata katika gogo kumbukumbu. Na wewe kuchukua 124, unaweza kupata ndani kama gogo nyota, ambayo ni kama mambo. Hivyo kama wewe ni nia, Luke logi nyota. Ni aina ya furaha. Hivyo tuna hii chati kubwa. Tu vichwa juu, hii a ajabu chati kwa kuwa kwa katikati mrefu yako kwa sababu sisi muda mrefu kuuliza thins haya. Hivyo tu vichwa juu, na hii juu yako katikati mrefu juu ya kudanganya yako nzuri karatasi huko. Hivyo sisi tu inaonekana katika Bubble aina. Kesi mbaya, n mraba, kesi bora, n. Na sisi ni kwenda kuangalia wengine. Na kama unaweza kuona, tu moja kwamba kweli anafanya vizuri ni kuunganisha aina, ambayo tutaweza kupata katika nini. Hivyo sisi ni kwenda kwenda ijayo moja here-- uteuzi aina. Je, mtu yeyote kumbuka jinsi uteuzi aina ya kazi? Kwenda kwa hayo. STUDENT: Kimsingi kupitia Ili na kujenga orodha mpya. Na kama wewe ni kuweka mambo katika, kuziweka katika mahali pa haki katika orodha mpya. Mwalimu: Hivyo kwamba sauti zaidi kama insertion aina. Lakini wewe ni kweli karibu. Wao ni sawa sana. Hata mimi kupata yao kuchanganywa wakati mwingine. Kabla sehemu hii mimi nilikuwa kama, kusubiri. OK. Hivyo nini unataka kufanya ni uteuzi aina, njia unaweza kufikiria kuhusu hilo na njia Mimi kuhakikisha mimi si kujaribu kupata nao kuchanganywa, ni huenda kwa njia ya na ni kuchagua idadi ndogo na ni unaweka kwamba katika mwanzo wa orodha yako. Ni swaps ni pamoja na kwamba doa kwanza. Wao kweli kuwa mfano kwa ajili yangu. Kutisha. Hivyo njia tu kufikiri ya it-- uteuzi aina, kuchagua thamani ndogo. Na tunakwenda kukimbia kwa njia ya mfano nadhani itasaidia kwa sababu Nadhani kuonekana daima kusaidia. Hivyo sisi kuanza nje na kitu kwamba ni zisizochambuliwa kabisa. Red itakuwa zisizochambuliwa, kijani kutatuliwa. Itakuwa wote kufanya maana katika pili. Hivyo sisi kwenda kwa njia na sisi iterate kuanzia mwanzo hadi mwisho. Na sisi kusema, sawa, 2 ni idadi ndogo wetu. Hivyo sisi ni kwenda kuchukua 2 na tunakwenda kusogeza mbele ya safu yetu sababu ni idadi ndogo tuna. Hivyo kwamba ni nini hii ni kufanya hapa. Ni tu kwenda wabadilishane hizo mbili. Hivyo sasa tuna yamepangwa sehemu na sehemu zisizochambuliwa. Na nini vizuri kukumbuka kuhusu uteuzi aina ni sisi ni kuchagua tu kutoka sehemu zisizochambuliwa. sehemu sorted wewe tu kuondoka peke yake. Mm-hm? STUDENT: Jinsi gani kujua ni nini ndogo bila kulinganisha kila thamani nyingine katika safu. Mwalimu: Ni anafanya kulinganisha. Sisi kama skipped yake. Hii ni tu kwa ujumla kwa ujumla. Yeah. Wakati sisi kuandika kanuni nina kuhakikisha wewe utakuwa kuridhika zaidi. Lakini kuhifadhi hii kwanza kipengele kama ndogo. Kulinganisha na wewe kusema, sawa, ni ndogo? Ndiyo. Kuitunza. Hapa ni ndogo? Hakuna? Hii ni ndogo yako, reassign kwa thamani yako. Na wewe utakuwa na furaha sana wakati sisi kwenda kwa njia ya kificho. Hivyo sisi kwenda kwa njia ya, sisi byta, hivyo basi sisi kuangalia sehemu hii zisizochambuliwa. Hivyo sisi ni kwenda kuchagua tatu nje. Tunakwenda kuiweka juu ya saa mwisho wa sehemu yetu Iliyopangwa. Na sisi ni kwenda tu kuendelea kufanya kwamba, kufanya hivyo, na kufanya hivyo. Hivyo hii ni aina yetu ya pseudocode hapa. Tutaweza kanuni ya it up hapa katika pili. Lakini kitu tu kutembea kupitia katika ngazi ya juu. Wewe ni kwenda kutoka i sawa 0 kwa n minus 2. Hiyo ni optimization nyingine. Je, si wasiwasi sana kuhusu hilo. Hivyo kama wewe walikuwa wakisema. Kama Jacob alikuwa akisema, jinsi gani sisi kuweka wimbo wa nini cha chini yetu ni? Jinsi gani tunajua? Tuna kulinganisha kila kitu katika orodha yetu. Hivyo kiwango cha chini ni sawa na i. Ni kusema tu katika kesi hii ripoti ya thamani yetu ya chini. Hivyo basi ni kwenda iterate kupitia na huenda kutoka j sawa i pamoja na 1. Hivyo sisi tayari kujua kwamba hiyo ni kipengele yetu ya kwanza. Hatuna haja ya kulinganisha kwa yenyewe. Hivyo sisi kuanza kulinganisha na ijayo moja ambayo ni kwa nini ni i pamoja na 1 kwa n bala 1, ambayo ni mwisho wa safu huko. Na sisi alisema kama safu katika j ni chini ya safu min, basi sisi reassign ambapo fahirisi yetu chini ni. Na kama dakika si sawa na i, kama katika ambapo tulikuwa nyuma zaidi ya hapa. Hivyo kama wakati sisi kwanza alifanya hii moja. Katika kesi hiyo, ingekuwa kuanza saa sifuri, itakuwa kuishia kuwa mbili. Hivyo min haitokuwa sawa i katika mwisho. Kwamba lets sisi kujua kwamba tunahitaji wabadilishane yao. Najisikia kama mfano halisi itasaidia zaidi kuliko huu. Hivyo mimi itabidi Kanuni hii na wewe guys sasa hivi na nadhani utakuwa bora. Aina huwa na kazi njia katika ni mara nyingi zaidi tu kuona kwao. Hivyo nini tunataka kufanya ni sisi kwanza unataka ndogo kipengele katika nafasi yake katika safu. Nini hasa Jacob alikuwa akisema. Unahitaji kuhifadhi kwamba kwa namna fulani. Hivyo sisi ni kwenda kuanza hapa iterating juu ya safu. Tunakwenda kusema ni yetu kwanza moja tu ya kuanza kwa. Hivyo sisi ni kwenda na int ndogo ni sawa na safu katika i. Hivyo jambo moja taarifa, kila wakati kitanzi hii executes, sisi ni mapya hatua moja zaidi pamoja. Wakati sisi kuanza sisi kuangalia hii moja. wakati mwingine sisi iterate kupitia, sisi ni kuanzia saa moja hii na kumshirikisha ni thamani yetu ndogo. Hivyo ni sawa na Bubble aina ambapo tunajua kwamba baada ya kupitisha moja, kipengele hii ya mwisho ni Iliyopangwa. Na uteuzi aina, ni kinyume tu. Katika kila kupita, tunajua kwamba moja ya kwanza ni Iliyopangwa. Baada ya kupita ya pili, pili moja itakuwa sorted. Na kama wewe aliona na mifano slide, sehemu yetu yamepangwa tu anaendelea kukua. Hivyo kwa kuweka moja wetu ndogo kwa arrays i, kila ni kufanya ni constricting nini sisi ni kuangalia hivyo kama kupunguza idadi ya kulinganisha sisi kufanya. Je, hiyo mantiki kwa kila mtu? Je, unahitaji mimi kukimbia kwa njia ya kwamba tena polepole au kwa maneno tofauti? Mimi nina furaha. OK. Hivyo sisi ni hifadhi thamani katika hatua hii, lakini pia tunataka kuhifadhi index. Hivyo sisi ni kwenda kuhifadhi nafasi ya ndogo moja, ambayo ni kwenda tu kuwa i. Hivyo sasa Jacob ni kuridhika. Tuna mambo kuhifadhiwa. Na sasa sisi haja ya kuangalia kupitia sehemu zisizochambuliwa wa safu. Hivyo katika kesi hii hii itakuwa zisizochambuliwa yetu. Hii ni i. OK. Hivyo kile sisi ni kwenda kufanya ni kwenda kuwa kwa kitanzi. Wakati wowote unahitaji iterate kupitia safu, akili yako inaweza kwenda kwa ajili ya kitanzi. Hivyo kwa baadhi int k equals-- nini tunafikiri k ni kwenda sawa kuanza na? Hii ni nini sisi kuweka kama ndogo wetu thamani na tunataka kulinganisha. Nini tunataka kulinganisha kwa? Ni kwenda kuwa hii moja ijayo, haki? Hivyo tunataka k kuwa initialized i pamoja na 1 kuanza. Na tunataka k katika kesi hii sisi tayari ukubwa kuhifadhiwa hadi hapa, ili tuweze tu kutumia ukubwa. Ukubwa kuwa ukubwa wa safu. Na sisi tu wanataka update k na moja kila wakati. Baridi. Hivyo sasa tunahitaji kupata ndogo kipengele hapa. Hivyo kama sisi iterate kupitia, sisi nataka kusema, kama safu katika k ni chini ya value-- yetu ndogo hii ni mahali ambapo sisi ni kweli kuweka wimbo wa nini ndogo here-- basi tunataka reassign nini thamani yetu ndogo ni. Hii ina maana kwamba, oh, sisi ni iterating kupitia hapa. Chochote thamani ni hapa ni si yetu jambo ndogo. Hatutaki hilo. Tunataka reassign yake. Hivyo kama sisi ni reassigning hivyo, je, unafikiri wanaweza kuwa katika hii kificho hapa? Tunataka reassign ndogo na msimamo. Hivyo kile ni ndogo sasa? STUDENT: Array k. Mwalimu: Array k. Na nini nafasi sasa? Nini fahirisi ya thamani yetu madogo? Ni k tu. Hivyo safu k, k, mechi up. Hivyo sisi alitaka reassign hiyo. Na kisha baada ya sisi kupatikana ndogo yetu, hivyo mwishoni mwa hii kwa kitanzi hapa tumepata nini ndogo wetu thamani ya, hivyo sisi tu byta yake. Katika kesi hiyo, kama wanasema wetu thamani ndogo ni nje hapa. Hii ni thamani yetu ndogo. Sisi tu wanataka wabadilishane hapa, ambayo ni nini kwamba wabadilishane kazi chini alifanya, ambayo sisi tu aliandika up pamoja dakika kadhaa iliyopita. Hivyo ni lazima kuangalia ukoo. Na basi itakuwa tu iterate kupitia mpaka inafikia njia yote na mwisho, ambayo ina maana kwamba kuwa na vipengele sifuri kwamba ni zisizochambuliwa na kila kitu kingine imekuwa yamepangwa. Mantiki? zaidi kidogo kwa uthabiti? kificho msaada? STUDENT: Kwa kawaida, kamwe kweli kufafanua au mabadiliko hayo, jinsi gani unajua? Mwalimu: Hivyo jambo moja taarifa juu hapa ni int kawaida. Hivyo sisi ni kusema katika aina hii sort-- ni kazi katika hii case-- ni uteuzi aina, ni kupita katika na kazi. Hivyo kama ilikuwa si kupita katika, ungependa kufanya kitu kama na urefu wa safu au ungependa iterate kupitia kupata urefu. Lakini kwa sababu ni kupita katika, tunaweza tu matumizi yake. Wewe tu kudhani kwamba mtumiaji alitoa wewe ukubwa halali kwamba kweli inawakilisha ukubwa wa safu yako. Baridi? Kama wewe guys kuwa na shida yoyote na hizi au unataka zaidi mazoezi coding aina juu yako mwenyewe, unapaswa kwenda study.cs50. Ni chombo. Wana kusahihisha kwamba unaweza kweli kuandika. Wao kufanya pseudocode. Wana videos zaidi na slides ikiwa ni pamoja na wale wa mimi kutumia hapa. Hivyo kama wewe ni bado hisia kidogo fuzzy, kujaribu kuwa nje. Kama siku zote, kuja kuzungumza na mimi, pia. Swali? STUDENT: Je, akisema ukubwa inaelezwa awali? Mwalimu: Ndiyo. Ukubwa ni awali defined up hapa katika kazi tamko. Hivyo kudhani kuwa ni kuwa kupita katika kwa mtumiaji, na kwa ajili ya unyenyekevu wa, tunakwenda kudhani kwamba user alitupa ukubwa sahihi. Baridi. Hivyo hiyo ni uteuzi aina. Guys, najua sisi ni kujifunza mengi leo. Ni data mnene kwa sehemu. Hivyo, pamoja na kwamba, sisi ni kwenda kwenda kuingizwa aina. OK. Hivyo kabla ya kuwa sisi kufanya Runtime yetu uchambuzi hapa. Hivyo katika kesi bora, nafasi tangu mimi ilionyesha yenu meza Mimi tayari aina ya alitoa mbali. Lakini kesi bora Runtime, je, sisi kufikiri? Kila kitu sorted. N mraba. Mtu yeyote kuwa na maelezo kwa nini unafikiri? STUDENT: Wewe ni kulinganisha through-- Mwalimu: Haki. Wewe ni kulinganisha njia ya. Katika kila iteration, ingawa sisi ni decrementing hii kwa moja, bado uko kutafuta njia ya kila kitu kupata moja ndogo. Hivyo hata kama thamani yako ndogo ni hapa mwanzoni, bado uko kulinganisha dhidi ya kila kitu kingine kuhakikisha ni jambo ndogo. Hivyo itabidi kuishia mbio kwa njia ya takriban n mraba nyakati. Wote haki. Na nini kesi mbaya? Pia n mraba kwa sababu wewe ni kwenda kuwa kufanya kwamba utaratibu huo. Hivyo katika kesi hii, uteuzi aina ina kitu kwamba sisi pia kuwaita inatarajiwa Runtime. Hivyo kwa wengine, sisi tu kujua juu na chini mipaka. Kulingana na jinsi mambo yetu orodha ni au jinsi zisizochambuliwa ni, wao kutofautiana kati ya n au n squared. Hatujui. Lakini kwa sababu uteuzi aina ina sawa mbaya na kesi bora, kwamba inatuambia kwamba hakuna jambo aina gani ya pembejeo sisi kuwa, kama ni kabisa yamepangwa au kabisa kubadili yamepangwa, ni kwenda kuchukua kiasi hicho cha wakati. Hivyo katika kesi hiyo, kama wewe kukumbuka kutoka meza yetu, ni kweli alikuwa thamani kwamba aina hizi mbili hawana, ambayo ni inatarajiwa Runtime. Hivyo tunajua kwamba wakati wowote sisi kukimbia uteuzi aina, ni uhakika kukimbia n mraba muda. Hakuna tofauti huko. Ni tu ilivyotarajiwa. Na, tena, kama unataka kujifunza zaidi, kuchukua CS 124 katika spring. Wote haki. Tumeona hii moja. Baridi. Hivyo insertion aina. Na mimi nina pengine ni kwenda kuwaka kwa njia hii. Mimi si kuwa nyie kanuni ya yake. Tutaweza tu kutembea kwa njia hiyo. Hivyo insertion aina ni aina ya sawa na uteuzi aina katika kwamba tuna wote wawili zisizochambuliwa na yamepangwa sehemu ya safu. Lakini nini tofauti ni kwamba kama sisi kwenda kwa njia ya moja kwa moja, sisi tu kuchukua chochote idadi ni ya pili katika zisizochambuliwa yetu, na kwa usahihi aina yake katika safu yetu Iliyopangwa. Ni itabidi kufanya maana zaidi na mfano. Hivyo kila kitu kuanza kama zisizochambuliwa, tu kama na uteuzi aina. Na tunakwenda aina hii katika wakipanda ili kama tumekuwa. Kadhalika kupita wetu wa kwanza sisi kuchukua thamani kwanza na sisi kusema, sawa, wewe ni sasa katika orodha na wewe mwenyewe. Kwa sababu wewe ni katika orodha na wewe mwenyewe, wewe ni sorted. Hongera kwa kuwa kipengele kwanza katika safu hii. Uko tayari yamepangwa yote juu yako mwenyewe. Hivyo sasa tuna yamepangwa na safu zisizochambuliwa. Hivyo sasa sisi kuchukua kwanza. Kile kinachotokea kati hapa na hapa ni kwamba sisi kusema, OK, sisi ni kwenda kuangalia thamani ya kwanza ya safu yetu zisizochambuliwa na tunakwenda pembejeo katika wake mahali sahihi katika safu Iliyopangwa. Hivyo kile sisi ni sisi kuchukua 5 na sisi kusema, sawa, 5 ni kubwa zaidi kuliko 3, hivyo sisi tu kuingiza haki na haki ya hiyo. Sisi ni njema. Hivyo basi sisi kwenda kwenye moja ijayo. Na sisi kuchukua 2. Sisi tunasema, OK, 2 ni chini kuliko 3, hivyo tunajua kwamba mahitaji ya kuwa katika mbele ya orodha yetu ya sasa. Hivyo kile sisi kufanya ni sisi kushinikiza 3 na 5 chini na sisi hoja 2 katika yanayopangwa kwanza. Hivyo sisi ni tu kuingiza ndani mahali sahihi ni lazima. Kisha sisi kuangalia wetu moja ya pili, na sisi kusema 6. OK, 6 ni kubwa kuliko kila kitu katika safu yetu Iliyopangwa, hivyo sisi tu tag juu ya mwisho. Na kisha sisi kuangalia 4. 4 ni chini ya 6, ni chini ya kuliko 5 lakini kubwa kuliko 3. Hivyo sisi tu kuingiza haki katika katikati kati ya 3 na 5. Hivyo kufanya kuwa kidogo kidogo zaidi halisi, hapa ni aina ya wazo la nini kilichotokea. Hivyo kwa kila kipengele zisizochambuliwa, sisi kuamua ambapo katika sehemu Iliyopangwa ni. Hivyo kuweka katika akili yamepangwa na zisizochambuliwa, tuna traverse kupitia na takwimu nje ambapo inafaa katika safu Iliyopangwa. Na sisi kuingiza kwa shifting vipengele na haki ya chini. Na kisha sisi tu kuweka iterating kupitia mpaka sisi kuwa na orodha kabisa yamepangwa ambapo zisizochambuliwa sasa ni sifuri na sorted inachukua hadi ukamilifu wa orodha yetu. Hivyo, tena, kufanya mambo hata thabiti zaidi, tuna pseudocode. Hivyo kimsingi kwa i ni sawa na 0 kwa n minus 1, hiyo ni urefu wa safu yetu. Tuna baadhi ya kipengele kwamba ni sawa na safu ya kwanza au fahirisi ya kwanza. Sisi kuweka j sawa na kwamba. Hivyo wakati j ni mkubwa kuliko sifuri na safu, j minus 1 ni mkubwa kuliko kipengele, hivyo wote kwamba anafanya ni kuhakikisha kwamba j yako kweli inawakilisha sehemu zisizochambuliwa wa safu. Hivyo wakati bado kuna mambo kutatua na j minus moja is-- nini ni kipengele wake? J alikuwa kamwe defined hapa. Ni aina ya annoying. OK. Anyways. Hivyo j minus 1, wewe ni kuangalia kipengele mbele yake. Wewe kusema, sawa, ni kipengele kabla popote mimi am-- hebu kweli kuteka hii nje. Basi hebu kusema hii ni kama juu ya kupita yetu ya pili. Hivyo i ni kwenda kuwa sawa 1, ambayo ni hapa. Hivyo i ni kwenda kuwa sawa na 1. Hii itakuwa 2, 4, 5, 6, 7. Wote haki. Hivyo kipengele yetu katika kesi hii ni kwenda kuwa sawa na 4. Na tuna baadhi ya j kwamba itakuwa sawa na 1. Oh, j ni decrementing. Hiyo ni nini. Hivyo j ni sawa na i, hivyo nini hii ni Msemo ni kwamba kama sisi kusonga mbele, sisi ni maamuzi tu kuhakikisha kwamba sisi siyo juu ya Indexing njia hii wakati sisi ni kujaribu kuingiza mambo katika orodha yetu Iliyopangwa. Hivyo wakati j ni sawa na 1 katika kesi hii na safu j minus one-- hivyo safu j minus 1 ni 2 katika case-- hii kama hiyo kubwa kuliko kipengele, basi wote hii ni kufanya ni shifting mambo chini. Hivyo katika kesi hii, safu j minus moja itakuwa safu sifuri, ambayo ni 2. 2 si mkuu zaidi kuliko 4, hivyo hii haina nitafanya. Hivyo mabadiliko hana hoja chini. Nini hii hapa ni tu kusonga safu yako sorted chini. Katika kesi hiyo, kwa kweli, sisi inaweza do-- hebu kufanya hii 3. Hivyo kama sisi ni kutembea kwa njia na mfano huu, tuko sasa hapa. Hii ni Iliyopangwa. Hii ni zisizochambuliwa. Baridi? Hivyo i ni sawa na 2, hivyo kipengele yetu ni sawa na 3. Na j yetu ni sawa na 2. Hivyo sisi kuangalia njia na sisi kusema, sawa, ni safu j minus moja kubwa kuliko kipengele kwamba sisi ni kuangalia? Na jibu ni ndiyo, haki? 4 ni mkubwa kuliko 3 na j ni 2, hivyo kanuni hii executes. Hivyo sasa nini cha kufanya safu katika 2, hivyo hapa hapa, sisi wabadilishane yao. Hivyo sisi tu kusema, sawa, safu saa 2 sasa ni kwenda kuwa 3. Na j ni kwenda sawa j minus 1, ambayo ni 1. Hiyo ni ya kutisha, lakini nyie kupata wazo. J sasa ni sawa na 1. Na safu j ni kwenda tu kuwa sawa na kipengele yetu, ambayo ilikuwa 4. Mimi kufutika kitu mimi hawapaswi kuwa au miswrote kitu, lakini nyie kupata wazo. Ni hoja katika n. Na kisha kama hii walikuwa, ingekuwa kitanzi tena na kusema, sawa, j ni 1 ya sasa. Na safu j minus 1 ni sasa 2. Ni 2 chini ya kipengele yetu? Hakuna? Hiyo ina maana kwamba tumekuwa kuingizwa kipengele hii katika doa sahihi katika safu yetu Iliyopangwa. Basi tunaweza kuchukua hii na sisi kusema, OK, safu yetu sorted ni hapa. Na itachukua idadi hii ya 6 na kuwa kama, sawa, ni 6 chini ya idadi hii? Hakuna? Baridi. Sisi ni faini. Kufanya hivyo tena. Sisi tunasema 7. Ni 7 chini ya mwisho safu yetu Iliyopangwa? Hakuna Hivyo sisi ni faini. Hivyo hii itakuwa kutatuliwa. Kimsingi yote hii haina ni ni kusema kuchukua kipengele kwanza ya safu yako zisizochambuliwa, takwimu nje ambapo unaendelea katika safu yako sorted. Na hii tu inachukua huduma ya swaps kufanya hivyo. Wewe ni kimsingi tu swapping mpaka ni katika doa haki. picha Visual ni kwamba wewe ni kusonga kila kitu chini kwa kufanya hivyo. Hivyo ni kama nusu Bubble aina-esque. Angalia utafiti 50. Mimi sana kupendekeza kujaribu na kanuni hii juu yako mwenyewe. Kama una masuala yoyote au unataka kuona sampuli kificho kwa aina insertion, tafadhali basi mimi kujua. Mimi nina daima karibu. Hivyo kesi mbaya Runtime na kesi bora Runtime. Kama wewe guy aliona kutoka meza Mimi tayari ilionyesha wewe, ni wote n mraba na n. Hivyo aina ya kwenda mbali ya kile sisi aliyesema kuhusu na aina yetu ya awali, mbaya kesi Runtime ni kwamba kama ni kabisa zisizochambuliwa, tuna kulinganisha yote ya nyakati hizi n. Sisi kufanya mengi yote ya kulinganisha kwa sababu kama ni ili reverse, tunakwenda kusema, sawa, hii ni sawa, hii ni nzuri, na hii moja itakuwa na ikilinganishwa dhidi ya moja ya kwanza kuwa wakiongozwa nyuma. Na kama sisi kupata ya kutolewa mwisho wa mkia, tuna kulinganisha, kulinganisha, na kulinganisha dhidi ya kila kitu. Hivyo kuishia kuwa takriban n squared. Kama ni sahihi basi kusema, sawa, 2, wewe ni nzuri. 3, wewe ni ikilinganishwa na 2. Wewe ni nzuri. 4, wewe tu kulinganisha na mkia. Wewe ni nzuri. 6, kulinganisha na mkia, wewe ni faini. Hivyo kwa kila doa kama ni tayari yamepangwa, wewe ni kufanya kulinganisha moja. Hivyo ni tu n. Na kwa sababu tuna bora kesi Runtime ya n na kesi mbaya Runtime ya n mraba, hatuna Runtime inatarajiwa. Ni tu inategemea machafuko ya orodha yetu huko. Na tena, mwingine graph na meza nyingine. Hivyo tofauti kati ya aina. Mimi tu kwenda kwa breeze kupitia, mimi kujisikia kama tumekuwa aliyesema sana kuhusu jinsi kila aina ya kutofautiana na kuunganisha pamoja. Hivyo kuunganisha aina ni moja ya mwisho Mimi atalitoboa nyie pamoja. Sisi kufanya kuwa picha pretty colorful. Hivyo kuunganisha aina ni algorithm kujirudia. Hivyo wewe guys kujua nini kazi ya kujirudia ni? Mtu yeyote wanataka kusema? Unataka kujaribu? Hivyo kazi ya kujirudia ni tu kazi kwamba wito yenyewe. Hivyo kama wewe guys ni ukoo na mlolongo Fibonacci, hiyo ni aliona kujirudia kwa sababu wewe kuchukua mbili zilizopita na kuongeza yao pamoja kupata moja ijayo yako. Hivyo kujirudia, mimi daima kufikiria ya recursion kama kama ond hivyo wewe ni kama spiraling chini ndani yake. Lakini ni tu kazi kwamba wito yenyewe. Na, kwa kweli, kweli haraka mimi unaweza kuonyesha nini kwamba inaonekana kama. Hivyo kujirudia hapa, kama sisi kuangalia, hii ni njia ya kujirudia kwa jumla juu ya safu. Hivyo wote kwamba sisi kufanya ni tuna Jumla kazi Jumla kwamba inachukua ukubwa na safu. Na kama taarifa, ukubwa decrements na moja kila wakati. Na wote ni gani ni kama x ni sawa na zero-- hivyo kama ukubwa wa safu ni sawa na zero-- anarudi sifuri. Vinginevyo sums hii mwisho kipengele cha safu, na kisha inachukua Jumla ya mapumziko ya safu. Hivyo ni tu kuvunja chini katika matatizo na ndogo ndogo. Long hadithi fupi, recursion, kazi kwamba wito yenyewe. Kama kwamba ni yote wewe got nje ya hii, kwamba ni nini kazi ya kujirudia ni. Kama wewe kuchukua 51, utapata sana, vizuri sana na recursion. Ni kweli baridi. Alifanya akili katika kama 3:00 usiku mmoja nje. Na mimi nilikuwa kama, kwa nini mimi kamwe kutumia hii? Hivyo kwa kuunganisha aina, kimsingi nini ni kwenda kufanya ni ni kwenda kuvunja chini na kuvunja chini mpaka ni mambo tu moja. mambo moja ni rahisi kutatua. Tunaona kwamba. Kama una kipengele moja, ni tayari kuchukuliwa Iliyopangwa. Kadhalika pembejeo ya mambo n, kama n ni chini ya 2, tu kurudi kwa sababu kwamba njia ni aidha 0 au 1 kama tumeona. Wale ni kuchukuliwa mambo Iliyopangwa. Vinginevyo kuvunja katika nusu. Aina nusu ya kwanza, kutatua pili nusu, na kisha kuunganisha yao kwa pamoja. Nini ni kuitwa kuunganisha aina. Hivyo tuna hapa tutaweza kutatua hayo. Hivyo sisi kuendelea kuwa nao mpaka safu ukubwa ni 1. Hivyo wakati ni 1, sisi tu kurudi sababu hii ni safu Iliyopangwa, na hii ni safu Iliyopangwa, na kwamba safu Iliyopangwa, tuko wote yamepangwa. Hivyo basi nini cha kufanya ni sisi kuanza kuunganisha pamoja. Hivyo njia unaweza kufikiri juu ya kuunganisha ni wewe tu kuondoa ndogo idadi ya kila moja ya arrays ndogo na tu append kwa safu uliojitokeza. Hivyo kama wewe kuangalia hapa, wakati tuna seti hizi tuna 4, 6, na 1. Wakati tunataka kuunganisha hizi, sisi kuangalia hizi mbili za kwanza na sisi kusema, sawa, 1 ni ndogo, unaendelea mbele. 4 na 6, kuna kitu kulinganisha kwa, tu tag juu ya mwisho. Wakati sisi kuchanganya hizi mbili, sisi tu kuchukua moja ndogo ya hizi mbili, hivyo ni 1. Na sasa sisi kuchukua ndogo ya hizi mbili, hivyo 2. Ndogo ya hizi mbili, 3. Ndogo ya hizi mbili, 4, 5, 6. Hivyo wewe ni kuunganisha mbali tu haya. Na kwa sababu wameweza wamekuwa yamepangwa awali, wewe tu moja kulinganisha kila wakati huko. Hivyo zaidi kificho hapa, uwakilishi tu. Hivyo kuanza katikati na you aina kushoto na kulia na kisha wewe tu kuunganisha hizo. Na hatuna kificho kwa kuunganisha haki hapa. Lakini tena, kama wewe kwenda juu ya kujifunza 50, utakuwa huko. Vinginevyo kuja kuzungumza na mimi kama wewe ni bado kuchanganyikiwa. Hivyo baridi jambo hapa ni kwamba kesi bora, kesi mbaya, na inatarajiwa Runtime wote ni katika logi n, ambayo ni bora kuliko tumekuwa kuonekana kwa ajili ya mapumziko ya aina yetu. Tumeona n mraba na nini sisi kweli kupata hapa ni n logi n, ambayo ni kubwa. Kuangalia jinsi bora zaidi kwamba ni. Kama nzuri Curve. Hivyo zaidi ufanisi. Kama wewe milele unaweza, matumizi ya kuunganisha aina. Itakuwa kuokoa muda. Kisha tena, kama sisi alisema, kama uko chini katika mkoa huu chini, haina kufanya kwamba mengi ya tofauti. Kupata hadi maelfu na maelfu ya pembejeo, wewe dhahiri wanataka ufanisi zaidi algorithm. Na, tena, meza yetu nzuri ya yote aina ya kwamba wewe guys kujifunza leo. Hivyo najua imekuwa siku mnene. Hii si lazima kwenda kukusaidia na pset yako. Lakini nataka tu kufanya Kanusho sehemu hiyo siyo tu kuhusu psets. Nyenzo hii yote ni haki mchezo kwa midterms yako. Na pia kama wewe kufanya kuendelea na CS, haya ni misingi muhimu kwamba ungependa haja ya kujua. Hivyo baadhi ya siku itakuwa zaidi kidogo pset msaada, lakini baadhi ya wiki itakuwa bidhaa zaidi halisi kwamba inaweza kuonekana super muhimu na wewe sasa hivi, lakini mimi ahadi kama wewe kuendelea juu ya itakuwa sana, muhimu sana. Hivyo hiyo ni kwa ajili ya sehemu. Chini ya waya. Mimi alifanya hivyo ndani ya dakika moja. Lakini kuna kwenda. Nami kuwa donuts au pipi. Ni mtu yeyote mzio chochote, kwa njia? Mayai na maziwa. Hivyo donuts ni hakuna? OK. Wote haki. Chocolate hakuna? Starburst. Starbursts ni nzuri. OK. Tunakwenda kuwa Starburst wiki ijayo basi. Hiyo ni nini mimi itabidi kupata. You guys kuwa wiki kubwa. Kusoma spec yako. Napenda kujua kama una maswali yoyote. Pset mbili darasa lazima nje na wewe kwa Alhamisi. Kama una maswali yoyote kuhusu jinsi mimi hadhi kitu au kwa nini mimi hadhi kitu njia mimi hakuwa, tafadhali email yangu, kuja kuzungumza na mimi. Mimi nina mambo kidogo hii wiki, lakini mimi ahadi Mimi bado kujibu ndani ya masaa 24. Hivyo kuwa kubwa wiki, kila mtu. Bahati nzuri juu ya pset yako.