JASON Hirschhorn: Välkommen till vecka tre, alla. Vi har en hektisk men spännande avsnitt framför oss. Så först, därför att vi har gjort vissa framsteg med kursen men vi fortfarande har en hel del att lära kvar att göra, jag är ska visa er några resurser som skulle visa sig vara oerhört hjälp eftersom du inte bara vända din Problemet ställer, men också smälta alla det material vi ger er i föreläsningar och kortfilmer och avsnitt. Sen ska vi spendera de första 20 till 25 minuters avsnitt gå över GDB, som du kan eller inte kan ha används vid denna punkt, men det är en otroligt användbart verktyg som kommer att hjälpa dig att felsöka dina program. Många av er kanske har använt printf i mitt i ditt program att räkna vad en variabel uppgick. GDB är ännu bättre än printf och inte skruva upp din kod eftersom du köra det på en körbar fil. Så går vi över 10 mest användbara kommandon du behöver för GDB, och vi är kommer att gå på en övning tillsammans så i problem set tre och framåt, du kan använda GDB för att felsöka dina program. Och slutligen kommer vi att gå igenom några sortering och sökning algoritmer som du såg på föreläsning, och vi är kommer att faktiskt kod, inte bara pseudokod, men kod binär sökning, bubbla sortera och val av sort. Så först, jag vill gå över resurserna. Detta är en omfattande lista, och det är mindre typsnitt eftersom jag hade mycket att passar på här. Men dessa kommer inte bara hjälpa dig, igen, med problemsamlingar och smälta information du lärt dig, men definitivt, kom frågesport tid, dessa kommer vara otroligt hjälpsamma. Så först, konstaterar föreläsningen. Om du går till cs50.net/lectures och bläddra till vecka och dag, ser du att det finns noteringar för varje lecture, vilket inte är helt enkelt en transkript, men en redigerad version av vad som angavs i föreläsning med kod strängar och andra hjälp tidbits. Jag rekommenderar starkt att gå över dem. Och sedan också, det finns källkod tillgängliga från varje föreläsning. Och återigen, kommer dessa bilder också vara tillgängligt på cs50.net/sections i kväll. Så andra är shortsen varje vecka som täcker ämnen, vanligtvis 5 till 15 minuter i längd. Och de som förhoppningsvis kommer att ge dig en bra primer på olika ämnen. Tredje - och detta är helt ny här år - är study.cs50.net. Om du inte har kollat ​​upp det, jag rekommenderar starkt att du gör det. Du får välja ett ämne. Vi har massor av frågor om det. Så till exempel, väljer du Funktioner. Det ger dig några diabilder och noterar på funktioner. De är faktiskt de bilder som TF uppmuntras att använda under vår presentationer i avsnitt. Det finns också tips och tricks för att hantera med funktioner, och det finns övnings problem som hjälper du arbetar med funktioner. Vi ger dig också länkar till korta på funktioner och de tider som fungerar har kommit upp i föreläsningen. Så study.cs50.net, helt ny här år, en fantastisk resurs. Nästa, jag har människan, som är den manuella kommando som du kan köra på kommandorad. Så om du har några frågor om en kommando, till exempel, rand, som vi mötte förra veckan under avsnitt och du har förmodligen stött på i ditt problem inställd när man går igenom generera kod, men om du skriver man rand, får du den sida som berättar allt om rand. Det ger dig vad som krävs, det parametrar som krävs, samt avkastning typ och en kort beskrivning av denna funktion. Så kolla rand. Det kan vara en liten ordrik och förvirrande, så ibland tycker jag att helt enkelt googla det jag vill veta är det bästa sättet att hitta svaret. Så öva med Google. Få bra på Google. Det kommer att bli din bästa vän. Förutom Google, om du inte kan hitta det på Google, cs50.net/discuss, det är diskussionsforumet. Chanserna är om du har en fråga, en av dina 700 + kamrater också har att fråga och kan ha bett det redan i diskutera forum och få den besvarad. Så om du har en vanlig fråga eller du har en fråga som du tror kanske andra människor kanske har stött på, kolla cs50.net/discuss. Slutligen, de två sista, om du vill prata med en riktig människa, kontor timmar måndag till fredag. Det finns även online-kontorstid för förlängnings studenter. Och sist men absolut inte minst, mig, utropstecken. Ni har alla mina kontaktuppgifter. Om du behöver något, vänligen aldrig tveka inte att kontakta mig. Du är alltid välkommen att göra det. Mycket få av er har lagt till mig på Gchat, så det har varit en besvikelse, men förhoppningsvis som kommer att förändras mellan detta och nästa avsnitt. Har du frågor så långt på resurser? Bra. Slutligen, en annan kontakt för feedback, sayat.me/cs50. Du kan ge mig anonym respons om hur jag gör. Det var riktigt bra förra veckan. Jag fick ett par kommentarer från er direkt efter avsnitt, plus från andra elever som såg det under veckan, och det var otroligt bra. Jag kommer att försöka begränsa min användning av ordet "söt", men jag ska visa min entusiasm och spänning på andra sätt. Men det fanns andra tilläggs materiella återkopplingar, både plus och delta. Så snälla, jag ger er respons på dina problemsamlingar. Känn dig fri att ge mig feedback på min undervisning. Jag är här för er. Bra. Det är allt jag har för det första avsnittet. Är det någon som har någon frågor hittills? Och jag har en notering om kontrollcentralen. Förlängnings studenter har messaged mig säger att de inte får något ljud, men det är utanför min makt för att fixa. Så förhoppningsvis blir det lösas inom kort. Om du tittar på nätet, hej, men du kan inte höra mig. Så först, ska vi att gå igenom GDB. GDB, som jag antydde tidigare, är ett felsökningsverktyg mycket bättre än printf. Så för att komma igång med GDB, killar, om du vill öppna upp din apparat och ta den fil som jag mailade till dig tidigare - den här filen kommer också att tillgänglig online på lite - och kör GDB. / namnet på filen. Först, naturligtvis, måste du kompilera fil eftersom GDB fungerar bara på körbara filer. Men om du någonsin vill starta GDB, det första du gör, du kör GDB. / Caesar. Så det är namnet på det program som vi är kommer att gå med det just nu. Så jag kommer att skriva att Caesar, som kommer att ge mig en körbar fil här markeras med grönt. Och sedan ska jag köra GDB. / Cesar. Och där du går. Du ser att vi har en text talar om för mig om den version av GDB, ger mig viss garantiinformation, och då vi har BNP-prompten, som ser sorterar av som vår kommandoraden, men du ser att det är öppet Paren, GDB, nära Paren. Innan vi fortsätter och felsöka den här filen som jag skickade till er alla, låt oss titta på några användbara kommandon så vi har en känsla av vad vi kommer att täcka. Dessa kommandon visas här i ordning som jag vanligtvis använder dem. Så jag startar mitt program genom att köra GBD. / Namnet på programmet, i det här fallet, Caesar. Och sedan det första jag gör 99,9% av tiden är typ rast menar. Det sätter en brytpunkt vid huvud. I huvudsak, vad du gör det är programmet kommer att stanna vid huvud så att du kan börja granska den linje för rad, snarare än att köra alla vägen igenom. Du kan bryta vid olika din kod, men viktigaste är i allmänhet en bra ställe att börja. Nästa kommando jag kör är körning. Det startar programmet körs, och Om du måste ange kommandoraden argument, kör du det kommandot. Kör med argumenten. Så eftersom vi går över en version av C, som är det program ni skrev för pset två - den här, naturligtvis, har en del buggar i det att vi förhoppningsvis hittar - vi ska köra köra med några kommandot line argument eftersom Caesar, som ni vet per problemet ställa spec, tar lite kommandoradsargument. Nästa par kommandon, nästa man faktiskt kallas nästa. Att man tar dig rad för rad genom ditt program. Så slår n sedan Enter tar dig till nästa rad, verkställande föregående rad. Steg inte bara tar dig till nästa rad, men det tar dig inuti funktioner. Så om du har skrivit en funktion i din kod, eller om du vill utforska en att jag, till exempel, kan du träffa er, och snarare än att gå till nästa rad av filen som du går igenom höger nu, kommer du faktiskt kliva in denna funktion och se dess kod. List visar, i mycket användarvänlig format, de 10-tal linjer runt var du är i din kod så du kan faktiskt se filen i stället för att byta tillbaka och tillbaka mellan olika vyer. Print är som printf, som namnet antyder. Det visar vad en variabel är lika. Info lokalbefolkningen är riktigt bra. Detta är en specialversion av tryck. Info lokalbefolkningen visar dig alla de lokala variabler, skriver ut dem alla ut för dig som finns tillgängliga. Så jag i allmänhet, snarare än att behöva skriva ut de fyra variablerna som jag är nyfiken på om jag är i en for-slinga för exempel, jag bara skriva info lokalbefolkningen, och det kommer att visa mig vad min disk i är lika, samt den array som jag är arbetar med jämlikar. Slutligen, fortsätt. Skriva paus stoppar dig vid brytpunkten. Du kan gå igenom rad för linje med nästa och steg. Fortsätt kör programmet till din nästa bryta punkt eller till det att hela om det finns inga fler brytpunkter. Inaktivera tar bort brytpunkter om du beslutade paus vid huvud var olämpligt, du vill ställa in den någon annanstans. Och slutligen q, sluta, spårar ur GDB. Så detta program. / Caesar, vi kommer att titta igenom just nu och vi ska använda GDB för att hitta buggar i det här programmet. Jag körde det här programmet tidigare med Kontrollera 50, och jag fick en rynka pannan. Allt det existerade, det sammanställas, det passerade en hel del av testerna, men för någon anledning har den inte passera den femte testet, svarvning BARFOO, versaler, till E-D-U-I-R-R, versaler, med användning av tre som en nyckel. Jag kom ganska nära. Jag fick med en bokstav. Så det finns några små misstag i här. Jag har tittat igenom min kod. Jag kunde inte lista ut det. Förhoppningsvis kan ni hjälpa mig lista ut vad felet är. Så det är fel att vi är efter. Låt oss gå in i GDB. Återigen, jag kör GDB. / Caesar, så nu är vi i GDB. Och vad är det första sak jag ska göra? Jag har just gått in i GDB. Någon ge mig en bra kommando för att komma in. STUDENTEN break. JASON Hirschhorn: break. Fantastiskt. Låt oss skriva det i. Ni kan titta på upp här eller följ tillsammans på dina datorer. Break, och du kommer att se en brytpunkt fastställdes till - det ger mig några konstiga minnesadress, och det ger mig också radnumret. Om jag skulle se tillbaka på den här filen, Jag skulle inse att huvud hände på linje 21. Vad ska jag köra nästa? Är mitt program körs? Nej. Så vad ska jag köra nästa? STUDENT: Kör. JASON Hirschhorn: Kör. Ska jag köra bara springa, eller bör Jag lägger en del andra saker i? STUDENT: Kör med argumentet. JASON Hirschhorn: Kör med kommandoargument. Och eftersom jag felsökning av en mycket specifik fall, ska jag ange att kommandoradsargumentet. Så jag kör tre, som är, återigen, utmatningen jag fick från Check 50. Starta programmet. Vi går igenom ett par rader. Du kommer nu se att vi är på rad 21. Hur vet jag att vi är på rad 21? Därför att om man tittar till vänster mitt terminalfönster, där det står linje 21. Och det ger mig, faktiskt, det kod som är vid linjen 21. Så jag misspoke tidigare. Huvud är faktiskt inte på linje 21. Huvud är ett par rader över 21. Men på rad 21, det är där vi bryter. Denna kodrad har ännu inte verkställts. Det är viktigt. Linjen som du ser har inte utförts ännu. Det är nästa kodrad du är på väg att köra. Så nästa rad, eftersom ni är förmodligen bekant med, är detta villkor kontroll för att se om jag har trädde en kommandorad argument. Och en till i, vad är den andra en del av det som gör? Vad är att jag? STUDENT: Ändra det till ett heltal. JASON Hirschhorn: Förlåt? STUDENT: Det ändrar Argumentet till ett heltal. JASON Hirschhorn: Så en till jag ändrar arg v1 från en sträng till ett heltal. Och vad är det kontroll? STUDENT: Om det finns en andra kommandorad argument åt sidan från att köra programmet. JASON Hirschhorn: Och vad är den andra halvan av det här Booleskt uttryck kontroll? Denna del hit, en till mig? STUDENT: Om det är negativt. JASON Hirschhorn: Att se till vad? STUDENT: Att se till att det är i själva verket positivt. JASON Hirschhorn: Exakt. Detta är att kontrollera om det är negativ, och om det är negativt, jag har en känsla av nästa rad kanske ska jag skrika åt användaren. Så låt oss slå slut att genomföra denna linje. Vi ser inte att linje som ni kanske förväntas se skrika på användare och sedan återvänder, eftersom denna linje inte köra. Jag angav 3. Så jag gjorde faktiskt anger två kommando line argument, och 3 är större än noll. Så vi såg den linjen, avrättades vi, men vi ville inte gå inne i om tillståndet. Så nu, nästa, ser jag att jag ställer int nyckel är lika med en till jag arg v1. Så det är jag skapa en variabel nyckel. Så om jag skriver ut nyckeln just nu, eftersom som gör att du kan se värde inuti variabel, nyckel är lika med 47. Det är konstigt, men naturligtvis, det beror på att jag har inte avrättades den linjen ännu. Så nu om jag slog n, köra den linjen, och gör utskriftsknapp, kommer nyckeln lika 3, vilket är vad vi förväntar oss att det till lika. Så återigen, i GDB, den linje du ser du inte har verk ännu. Du måste slå n eller s eller ett nummer av andra kommandon till faktiskt exekvera den linjen. Skriv ut nyckeln. Nyckel s vid 3. Så långt är allt bra. String är vanlig text. Låt oss köra den linjen. Jag får en sträng från användaren. Låt oss se i min Kontrollera 50, jag ange BARFOO versaler, så det är vad jag ska skriva. Om jag nu skriva ut vanlig text. Du ser att det är lika med en sträng. Det ger mig en annan konstig hexadecimal nummer, men det gör i faktiskt säga att min sträng är BARFOO. Om jag ville se vad nyckeln uppgick vid denna punkt, hur kunde jag kontrollera nyckeln? STUDENTEN Print nyckel. JASON Hirschhorn: Print nyckel, exakt. Och faktiskt, det finns en genväg. Om du tröttnar på att skriva ut, du kan bara skriva sid. Så p knapp gör exakt samma sak. Och igen, ser jag att det är lika med 3. Om jag ville ta reda på vad både nyckel och BARFOO equaled samtidigt men jag var trött på att skriva varje ett individuellt, jag kan skriva info lokalbefolkningen. Det ger mig viktiga jämlikar 3. Enkel text motsvarar BARFOO. Det ger mig också dessa två konstiga saker upptill, denna variabel i och denna variabel n. De som faktiskt existerande i mitt huvudprogram. Vi har inte stött på dem ännu, men som en förhandsvisning, som existerar i mitt för slinga. Så just nu, de lika lite konstig siffror, eftersom de inte har initierats ännu, men de finns kvar i minnet, så att de bara satt till några sopor värde. Men vi ser nyckeln i klartext text där. Så jag kommer att köra den här linjen, linje 34, den för slingan. Vi kommer att hoppa in i för slinga genom att träffa n.. Och vi är inne i för slingan. Vi är på vår första kontroll. Och återigen, bör dessa slags titta bekant för dig, eftersom det var en Caesar program som skrevs, men igen, har något slags bugg. Och nu om jag gör info lokalbefolkningen, eftersom jag är insidan som för slinga, ser du att jag är lika med noll, eftersom vi förväntar oss. Det är vad vi ställa in den till och initieras det i för slingan. n är lika med 6. Det är också rimligt att vi satt den till strlen av ren text. Så jag gillar att göra info lokalbefolkningen eller skriv ut till variabel ofta att se till att allt är alltid vad Jag förväntar mig att det lika. I detta fall är allt vad jag förväntar mig det lika. Så låt oss börja röra sig genom detta för slinga. Linjen jag är på är linje 36, om vanligt text i är större än ett och vanlig text i är mindre än eller lika med z. Jag vet att mitt problem är inte med min första brev, är det med den andra bokstaven. Om vi ​​ser tillbaka på Check 50, B går till E böter. Jag tar det A och lämnar den som ett A, inte ändra det till D. So något är fel med det andra brevet. Så jag ska flytta det på en sekund. Men om jag ville kolla vad vanligt text jag equaled i detta särskilda fall, jag tycker att det borde vara vad? Vad ska klartext jag lika i detta första omgången genom att loopen? STUDENT: Zero? JASON Hirschhorn: Enkel text av I? Så det borde vara kapital B. Jag, naturligtvis, är lika med noll, men oformaterad text bygel noll avslutad bygel motsvarar B eftersom strängar, som vi såg förra veckan, är array, så vi får det första tecknet från det. Så återigen, om jag skrivas ut vanlig text av Jag, jag tror faktiskt få karaktären B. Och det är snyggt, eller hur? Jag behöver faktiskt inte klartext I. Det är inte en av de variabler som jag som eller initieras, men du kan skriva ut ut en mängd saker om du skulle vilja. Men låt oss gå igenom. Om klartext jag är större än A och klartext I är mindre än eller lika med Z, helt klart är det sant att vi har ett kapital B. Jag kommer att köra lite kommando på det. Vi såg att matte förra veckan, så vi ska tar det för givet att det fungerar rätt enligt Check 50. Dessa klamrar, den första visade att jag lämnar om tillstånd, den andra visade att jag lämnar för loopen. Och så nu när jag slog Nästa, vi får se Vi är tillbaka på för slingan igen. Vi går igenom för slingan igen. Låt oss verkligen kliva in i andra iteration av för slingan och typ info lokalbefolkningen. Så vi är i den andra iterationen vår för slinga. Jag är lika med 1, som vi förväntar oss. N är lika med 6, som vi förväntar oss. Nyckel lika med 3, som vi förväntar oss. Och ren text, ser du, är lika med EARFOO nu, inte BARFOO längre eftersom i vårt tidigare iterationen, var B ändras till ett kapital E. Så vi är på väg att stöta på problem, så detta är där vi ska dyka i felsökning. Men det någon som har några frågor om vad vi har gjort hittills? Fantastiskt. Så vi är på väg att genomföra detta om tillstånd, klartext fäste jag stängt fäste större än A och vanlig text jag mindre än eller lika med Z. Men innan Jag går in i det, eftersom det är här Jag vet att mitt misstag är, jag vill peka ut vanlig text av I. So låt oss sätta utskrift. Den gör motsvara tecknet A, så att verkar så långt är allt gott och väl. Så jag räknar med denna linje per min logik, denna linje ska vara sant. Det är en stor bokstav. Men om jag slog n, vi inser att detta linje, i själva verket inte köras. Jag hoppade ner till else if. Varför hände det? STUDENT: Eftersom du har ditt tillstånd av vanlig text är större än A, inte är lika med eller större än. JASON Hirschhorn: Så jag hade min oformaterad text I är större än A, som inte är större än eller lika med. Så klart, gjorde huvudstaden A inte utlösa detta om tillstånd, och vi gjorde inte kliva in i det, och vi gjorde inte göra de nödvändiga ändringarna. Så det är det, faktiskt. Jag kom på min bugg. Jag skulle kunna gå tillbaka i min källfilen, ändra det, och uppdatera den och kör Check 50 igen. Men vi får se, bara för pedagogik s skull, om jag fortsätter att gå. Den annars om inte köra heller, men vad stället lika är kommandot det ändras inte. Så det har inte förändrats alls, och om jag skriva ut ren text här, vi får se att gå genom att för slingan inte gjorde det, i själva verket, ändra på det andra tecknet alls. Det är fortfarande en kapital A. Så återigen, debuggade vi våra misstag. Vi insåg att det inte fanns viss logik saknas. Och vi debuggade det i förväg innan faktiskt köra den linjen, men du skulle ha märkt hade vi bara slå på Nästa och hoppa till det annars om, det innebär att att om villkoret var inte sant. Vi har inte, i själva verket får resultatet förväntas vi. Så då vi skulle ha genomfört, hade vi inte varit så klok, att titta på att om tillstånd och kontrollera om, i själva verket, våra villkor bör utvärderas till sant i det aktuella sammanhanget. Det var allt för felsökning av det här programmet. Är det någon som har några frågor? Vilket kommando skulle jag slog till sluta GDB? F: Och då jag blir ombedd, sluta hur som helst? Ja eller nej. Jag ska träffa ja, och jag har slutat GDB. Så det var en snabb primer till GDB. Faktiskt, i ett verkligt scenario Jag gjorde detta på kontorstid. Jag GDBed detta exakt program på kontorstid med en elev. Och om vi går tillbaka till de kommandon som vi såg tidigare, använde vi break, först sak gjorde vi. Vi använde springa med kommandoradsargument, andra saken gjorde vi. Vi använde bredvid en hel del att flytta oss genom linjer. Och återigen, den korta versionen nästa är n.. Det är inom parentes i grått på bilden. Vi använde inte steget, men vi gjorde inte nödvändigtvis för detta fall. Men vi skulle kunna använda den i lite senare på idag om vi felsökning, för exempel binär sökning när binära Sök heter i ett separat funktion, men det finns något fel med det. Vi kommer att vilja kliva in samtalet till binär sökning och faktiskt felsöka det. Lista vi använde inte heller eftersom vi hade en bra känsla för vår kod, men om jag ville få en känsla för vilken kod jag var runt, jag kunde bara använda listan. Skriv att vi använt, info lokalbefolkningen som vi använt. Fortsätt att vi inte behöver använda i detta fall, varken vi behöver använda inaktivera, men vi gjorde användning sluta. Återigen, dessa 10 kommandon, öva på dem. Om du förstår dessa 10 kommandon, du bör fastställas för felsökning alla utfärda med GDB. Så vi är på väg att gå på, igen, till springande punkten i avsnitt idag, att gå över dessa sortering och sökning algoritmer. Innan vi gör det, återigen, några frågor, kommentarer, oro för GDB? Så är alla kommer att använda GDB stället printf? Så alla, för all framtid skull, alla nickar huvudet rätt nu, så jag kommer att se dig på kontorstid och alla TF kommer att se dig och de kommer att säga, visa mig hur man använder GDB, och du kommer att kunna för att visa dem, eller hur? Typ av? Kanske förhoppningsvis. Cool. Så vi kommer att flytta in sortering och sökning. Du ser jag har en lista som redan sorterade för oss, men det kommer inte vara fallet alltid. Så i den problembild specifikation för problem set tre, du har shorts att du kan titta på, och det faktiskt ber dig att titta på dessa shorts. Även i föreläsning i förra veckan, gick vi över en hel del av dessa algoritmer, så jag är inte kommer att tillbringa tid i klassen går över dessa algoritmer igen eller ritning bilder för hur dessa algoritmer fungerar. Återigen, den informationen kan du re-watch föreläsning, eller att information fångas utomordentligt på shortsen för dessa sökningar, alla som finns på cs50.net. Så istället, vad vi ska göra är att skriva dessa program. Vi har en känsla, en mental modell, av hur de arbetar, och så vad vi ska göra är att koda dem på riktigt. Vi ska vända den mentala modell, den bilden, om man så vill, i faktiska koden. Och om du var lite förvirrad eller dimmig på den mentala modell, jag helt förstå. Vi ska inte faktiskt kommer att hoppa till kod direkt. Så medan denna prompt i detta bildspel frågar du att koda binär sökning, och faktiskt, en iterativ version av binär sökning, det första jag verkligen vill att du ska göra är att skriva några pseudokod. Så du har denna mentala modell om hur binär sökning fungerar. Ta ut ett papper om du har en lätt tillgänglig, eller öppna upp en textredigerare, och jag skulle vilja alla att skriva. Ta fyra minuter att skriva pseudokod för binär sökning. Återigen, tänk på det mentala modell. Jag ska komma runt om du har frågor och vi kan dra bilden ut. Men först, innan vi börjar programmera, Jag skulle vilja skriva pseudokod för binär sökning så när vi dyka in, har vi några riktning som där vi ska gå. STUDENT: Kan vi anta den rad av värden som vi får är redan sorterade? JASON Hirschhorn: Så för binär sökning till arbete - utmärkt fråga - du måste ta i en sorterad matris med värden. Så antar att det kommer att fungera. Vi ska gå tillbaka till den här bilden. Du ser i lila funktionen deklaration är bool binary_search int värde, int-värden, int n. Detta bör ser bekant om du har redan närmade sig eller fått din händer smutsiga med problemet set. Men det är funktionsdeklarationen. Återigen, inte ska behöva oroa sig för så mycket just nu. Vad jag verkligen vill att du ska göra är att ta fyra minuter till pseudo binär söka, och sedan går vi över den som en grupp. Och jag kommer att komma runt. Om du har frågor är du välkommen fri att räcka upp handen. Varför inte ta två minuter att avsluta den pseudo? Jag vet att detta kan verka löjligt att Vi spenderar så mycket tid på något som inte ens egentligen i C, men framför allt för dessa mer utmanande algoritmer och problem uppsättningar som vi måste ta reda på, med början i pseudokod inte oroa om syntaxen, bara behöva oroa logiken, är otroligt bra. Och på det sättet, du är inte lösa två otroligt svåra problem på en gång. Du ska bara fokusera på logiken, och då du flyttar in i syntaxen. OK. Låt oss börja gå igenom pseudokoden. Jag har skrivit upp här, binär sökning pseudokod. Vi kommer att skriva detta på ombord tillsammans. Eller ska jag skriva det och du kommer att ge mig uppmaning jag behöver. Så kan någon ge mig den första raden i pseudokoden som du skrev för binär sökning? Ja, Annie? STUDENT: Medan längden på listan är större än noll. JASON Hirschhorn: Medan längd på listan är större än noll. Och återigen ser vi några C-ser syntaktiska saker på här. Men det mesta av detta är på engelska. Var det någon som har någon linje de sätter innan detta i sin pseudo-kod? STUDENT: Få en array av sorterade siffror. JASON Hirschhorn: Du skrev "få en matris med sorterade siffror. "Per den funktionsdeklarationen, kommer vi att passera en matris av sorterat antal. STUDENTEN [OHÖRBAR]. JASON Hirschhorn: Så Vi kommer att ha det. Men ja, om vi inte hade det, vi skulle behöva sortera vårt utbud av siffror, eftersom binär sökning bara fungerar på sorterade arrayer. Så medan längden på listan är lika med noll, jag är ska sätta i några klammerparenteser så att det ser lite mer ut som C. Men samtidigt verkar för att kartlägga på en while-slinga, så inne i denna stund loop vad behöver vi för att göra för binär sökning? Någon annan som inte har gett mig en svara på ännu men som skrev det här? STUDENT: Gå till mitten av listan. JASON Hirschhorn: Tom. Gå till mitten av listan. Och följdfrågan, vad gör vi när vi är på mitten av listan? STUDENT: Gör en kontroll om det är det nummer du letar efter. JASON Hirschhorn: Excellent. Gå i mitten av listan och kontrollera om vårt värde är där - fantastiskt. Var det någon som har något annat som var annorlunda än det här? Det är precis rätt. Det första vi gör i binär sökning är att gå till mitten av listan och kontrollera om vårt värde är där. Så jag antar att om vårt värde är där, vad gör vi? STUDENT: Vi återvänder noll [OHÖRBAR]. JASON Hirschhorn: Ja, om vår värde är det, fann vi det. Så vi kan säga något sätt, men detta Funktionen är definierad, vi talar om för användaren vi fann det. Om det inte finns där, men det är där det blir knepigt. Så om det inte finns där, någon annan som arbetade med binär sökning eller har en idé nu, vad gör vi? STUDENT: Fråga. JASON Hirschhorn: Ja? STUDENT: Är arrayen redan sorterade? JASON Hirschhorn: Ja, vi antar matrisen är redan sorterade. STUDENT: Så då måste man kontrollera om det värde som du ser är större än det värde som du vill, kan du flytta till mitten av den andra halvan. JASON Hirschhorn: Så om mitten av listan är större än vad vi är söker, då vet vi vad? Vi rör oss där? STUDENT: Du vill flytta till den halva av listan med tal lägre än så. JASON Hirschhorn: Så vi ska kalla det vänster. Så om mitten är större, kan vi söka den vänstra halvan av listan. Och sedan genom sökningen, vilken menar jag med sökandet? STUDENTEN [OHÖRBAR]. JASON Hirschhorn: Vi går till mitten. Vi upprepar faktiskt denna sak. Vi går tillbaka genom vår while-slinga. Jag ska ge er den sista - annars, om det är mitt mindre än vad vi gör, vad gör vi här? STUDENT: Gå till höger. JASON Hirschhorn: Sök rätt. Det ser bra ut, men det någon som har något som vi kanske saknas eller något annat som du sätter i pseudo-kod? Så det här är vad vi har hittills. Även om längden av listan är större än noll, kommer vi att gå till mitten av listan och kontrollera om vårt värde är där. Om mitten är större, kommer vi att söka vänster, annars om mitten är mindre, ska vi söka rätt. Så vi har alla haft viss erfarenhet av ord vi använder i datavetenskap och de verktyg vi har. Men du kommer redan att märka att vi var tala engelska, men vi hittade en massa saker som verkade för att kartlägga den till verktyg som vi har i vår kodning verktygslåda. Så höger utanför bat, vi är inte kommer att faktiskt koda ännu. Vad är det vi ser här på engelska som kartor på att saker och ting kan vi skriva i C? STUDENT: Medan. JASON Hirschhorn: Medan. Så denna stund här kartor på vad? STUDENT: En while-slinga. JASON Hirschhorn: En while-slinga? Eller förmodligen mer allmänt en slinga. Vi vill göra något om och om igen. Så vi kommer att koda en loop. Och vi redan vet, för vi har gjort detta ett par gånger och vi har gott om exempel där ute, hur man faktiskt skriver detta index för en slinga. Så det borde vara ganska lätt. Vi borde kunna få det började ganska snabbt. Vad ser vi här? Vilka andra strukturer syntaxer, saker som vi känner till i C, gör vi redan har en känsla utifrån bort av de ord vi använt? Ja, Anna? [OHÖRBAR] bara skojar. Anna, gå vidare. STUDENT: Om och annat. JASON Hirschhorn: Om och annat - här. Så vad gör de se ut? STUDENT: En om annat uttalande. JASON Hirschhorn: Ja, förhållanden, eller hur? Så vi måste antagligen skriva några villkor. Och återigen, men kanske förvirrande i första, vi har i allmänhet en känsla nu om hur man skriver villkor och syntaxen för villkor. Och om vi inte gör det, vi ser bara upp syntax för förhållanden, klippa och klistra att, eftersom vi vet att vi behöver en förutsättning för detta. Alla andra saker som vi ser att kartan på saker vi kan behöva göra i C? Ja, Aleha? STUDENT: Det kan vara självklart, genom att bara kolla om en värde är lika med något. JASON Hirschhorn: Så hur ska vi kontrollera och - så gå till mitten av listan och kolla om vårt värde är det? Hur ska vi göra det i C? Vad är syntaxen för det? STUDENT: Lika, lika. JASON Hirschhorn: Lika, lika. Så denna kontroll är förmodligen kommer att vara ett likhets, lika. Så vi vet att vi behöver att någonstans. Och faktiskt, bara att skriva det, Vi ser dessa andra saker. Vi kommer att behöva göra några jämförelseoperatorer in där - fantastiskt. Så det faktiskt ser ut, med och stora, har vi inte skrivit en ord av C-kod än. Men vi fick den mentala modellen ner via föreläsningar och dessa shorts. Vi skrev pseudo-kod som en grupp. Och redan har vi 80%, om inte 90% av vad vi behöver göra. Nu behöver vi bara att koda den, vilket återigen är en icke-trivialt problem att lösa. Men åtminstone vi är fast på logiken. Åtminstone nu när vi går till kontorstid, Jag kan säga att jag vet vad jag behöver att göra, men kan du påminna mig om syntaxen? Eller även om kontorstid är trångt, du kan Google för syntaxen, snarare än att fastna på logiken. Och återigen, snarare än att försöka lösa logiken och syntaxproblem alla på en gång, är det ofta mycket bättre att bryta dessa två svåra problem ut i två mer hanterbara och kära och göra det pseudokod först och sedan koden i C. Så låt oss se vad jag gjorde för pseudo-kod i förväg. Även om längden av listan är större än noll, titta på mitten i listan. Om antalet hittade tillbaka sant, annars om antalet högre, söka vänster. Else om antalet är lägre, sök rätt, returnera false. Så det ser nästan identiska om inte nästan identisk med vad vi skrivit. Faktiskt, Tom, det du sa först, bryta mitt i listan och om nummer hittas i två rapporter är faktiskt vad jag gjorde. Jag kombinerade dem där. Jag borde ha lyssnat på du första gången. Så det är den pseudo-kod som vi har. Om du vill nu, sorry, gå tillbaka till vårt ursprungliga problem. Låt oss kod binary.c. Så genomföra en iterativ version av binär sökning med hjälp av följande funktionsdeklarationen. Och du behöver inte kopiera ner riktigt än. Jag faktiskt går att öppna upp just här binary.c. Så det finns funktionsdeklarationen i mitten av skärmen. Och så ser jag tog pseudo-kod från på mina sidor, men nästan identiska vad vi skrev, och sätta det i för dig. Så nu, låt oss ta fem minuter att koda denna funktion. Och igen, om du har några frågor, upp handen, låt mig veta, jag ska komma runt. STUDENTEN [OHÖRBAR]. JASON Hirschhorn: Så jag tog det binära Sök definition på överst, på linje 12. Det är vad jag fått för mina slide. Och sedan allt detta pseudo-kod jag bara kopiera och klistras från bilden, pseudokod slide. Jag är fortfarande inte höra [OHÖRBAR]. Så om du är klar med din genomförande, jag vill kolla upp det. Jag mailade dig helpers.h filen tidigare i denna klass. Och det kommer att finnas tillgängliga på nätet också för nedladdning för personer som tittar detta avsnitt tiden fördröjs. Och jag bara använt den generiska fördelningen kod från pset3. Så jag tog find.C, använda min helpers.h fil snarare än den helpers.h fil som har gett i distributionen kod. Och jag var tvungen att göra en annan förändring i find.C snarare än att kräva bara helt enkelt sök, ring binary_search. Så om du vill testa din kod, vet att det är hur man gör det. Faktum är att när vi ska köra den här koden just nu, jag gjorde bara en kopia av min pset3 katalog, återigen, bytte ut hjälpare filer och sedan gjort att förändras i find.C ringa binary_search snarare än att bara söka. JASON Hirschhorn: Ja. Har du frågor? STUDENT: Nevermind. JASON Hirschhorn: Inga bekymmer. Nåväl, låt oss komma igång. Vi kommer att koda detta som en grupp. En andra anmärkning. Återigen, detta är, kan enkelt bytas ut mot in för Problem Set Tre. Jag har min helpers.h fil som, snarare än helpers.h vi gett, förklarar binär sökning, bubbla sortera och val av sort. Och i find.c märker du på linjen, vad är det, linje 68, kallar vi binär sök snarare än sökning. Så återigen, den kod som är tillgänglig nätet eller den kod som du är skapar just nu lätt kan bytas i för p set 3 för att kontrollera det. Men först, låt oss koda binär sökning. Vår funktion deklaration, vi tillbaka en bool. Vi tar ett heltal som kallas värde. Vi tar en array av heltal kallas värderingar, och vi tar n vara storleken på matrisen. På rad 10, just här, har jag skarp inkluderar stdbool.h. Är det någon som vet varför det finns där? Så vad betyder det kodrad göra? STUDENT: Det kan du använda en typ bool avkastning. JASON Hirschhorn: Exakt. STUDENT: Eller det är ett bibliotek som gör att att använda en typ bool avkastning. JASON Hirschhorn: Så den kraftiga inkluderar stdbool.h linje ger mig några definitioner och förklaringar för saker att jag får använda i detta bibliotek. Så bland de som säger att det finns denna typ kallas bool, och det kan vara sant eller falskt. Så det är vad den linjen gör. Och om jag inte har den linjen, skulle jag få i trubbel för att skriva detta ord här, bool, precis där. Exakt rätt. Så jag behöver det i denna kod. OK. Så denna, återigen, är en iterativ versionen, inte en rekursiv en. Så låt oss komma igång. Låt oss börja med det första linje av pseudokod. Och förhoppningsvis kommer vi - eller inte förhoppningsvis. Vi kommer att gå runt i rummet. Vi går rad för rad, och jag kommer att hjälpa du räkna ut den linje som vi behöver att skriva först. Så medan längden på listan är större än noll. Låt oss börja i fronten. Vilken linje ska jag skriva Här, i kod? STUDENT: Även parentes n är större än 0. JASON Hirschhorn: Medan n är stor än 0. Så n är storleken på en lista, och vi kollar om - [inplacering UTTRYCKER] JASON Hirschhorn: - sorry? STUDENT: Hur vet vi att n är storleken på listan? JASON Hirschhorn: Förlåt. Per den pset specifikation, sökandet och fungerar sorterar du behöver för att skriva, n är storleken på listan. Jag glömde att förklara det här. Men ja. n är storleken på listan, i det här fallet. Så medan n är större än 0. OK. Det kan visa sig vara lite problematiskt Men om det går på. Eftersom vi kommer att fortsätta att känna till storleken på listan under hela denna funktion, men säger att vi börjar med en samling av fem heltal. Och vi går igenom och vi har nu minskat ner det till en uppsättning av två heltal. Vilka två heltal är det? Storleken är 2 nu när vi vill titta på, men som 2 är det? Är det vettigt att fråga? OK. Jag frågar igen. Så vi börjar med denna samling av 5 heltal, och n är lika med 5, eller hur? Vi kommer att gå igenom här. Vi ska nog ändra storlek, rätt, eftersom det går på. Vilket är vad vi säger att vi vill göra. Vi vill inte söka hela saken igen. Så säger vi ändra det till 2. Vi tar halva listan som är konstigt. Så bara plocka 2. Så nu n är lika med 2. Jag ber om ursäkt för de fattiga torra radera markörer. Rätt? Och vi söker igenom listan igen med en lista med storlek 2. Tja, är vår samling fortfarande av storlek 5. Vi säger att vi bara vill Sök 2 fläckar i den. Så som två fläckar är de? Låter det vettigt? Är de vänster 2 fläckar? Är de rätt 2 ställen? Är de de 2 mitt fläckar? Vi har brutit problemet ner, men vi faktiskt inte vet vilken del av problemet vi fortfarande tittar på, bara genom att ha dessa två variabler. Så vi behöver lite mer då, medan n är större än 0. Vi måste veta var det n är i våra faktiska array. Så det någon som har en byta till denna linje? Merparten av denna linje är helt rätt. Finns det ett annat tillägg? Kan vi byta ut något för n till gör denna linje lite bättre? Mm-hm? STUDENT: Kan du initierar en variabel såsom längd på n som sedan kommer att användas senare i funktion? JASON Hirschhorn: Så initiera en variabel längd med n, och vi använder det senare? Men då vi uppdaterar bara längd och vi fortfarande stöter på detta problem, där vi skära ner längden på vårt problem, men vi vet aldrig var, faktiskt, denna längd kartor på. STUDENT: Är inte det kommer att hända senare när du säger, söka vänster, Sök rätt? Du kommer att gå till en annan område av ditt - JASON Hirschhorn: Vi kommer att gå till ett område, men hur vet vi vilket är att gå till? Om vi ​​bara har matrisen och denna n, hur vet vi var de ska gå till i arrayen. I ryggen, ja? STUDENT: Har du, liksom, en lägre gräns och en övre gräns variabel eller något sådant? JASON Hirschhorn: OK. Så det här är en annan idé. Snarare än att bara hålla reda på storlek, vi hålla reda på den nedre och övre gräns variabel. Så hur vi beräknar storleken från en undre gräns och övre gräns? [inplacering UTTRYCKER] JASON Hirschhorn: subtraktion. Och även att hålla reda på den nedre bundna och övre gräns för att låta oss veta, Vi söker dessa två? Ska vi söka dessa två hit? Ska vi söka på två mitten? Förmodligen inte de två mellersta, eftersom detta i själva verket är binär sökning. Men nu kommer vi att kunna få den storlek, utan också gränserna för arrayen. I huvudsak, om vi har vår jätte telefonbok, vi slita den på mitten. Vi vet nu var det mindre telefonbok är. Men vi är faktiskt rippning telefonboken i halv. Vi behöver fortfarande veta var nya gränserna för vårt problem är. Är det någon som har några frågor om det? Ja? STUDENT: Skulle det fungera genom att skapa en variabel, jag, att du sedan bara flytta position i förhållande till dess nuvarande position, och längden, n? JASON Hirschhorn: Och vad är jag? STUDENT: Som jag vara som sorts - Som du vill initiera i för att vara den mellanposition av matrisen. Och sedan, om värdet på position i i mitten av uppsättningen i befunnits vara lägre än det värde som du behöver, jag nu blir längden av arrayen, plus Värdet på I dividerat med två. Liksom, se, flytta dig i - JASON Hirschhorn: Höger. STUDENT: - upp till - JASON Hirschhorn: Så jag är nästan positiva som kommer att fungera. Men poängen är, behöver du två bitar av information här. Du kan göra det med början och slut, eller så kan du göra det med storlek, och sedan någon markör. Men du behöver två stycken av information här. Du kan inte klara sig med bara en. Låter det vettigt? Så vi kommer att gå igenom, och vi kommer att göra [OHÖRBAR] och skapa några markörer. Vad gjorde du skriver in din kod? STUDENT: Jag sa bara int bunden en är lika med 0. JASON Hirschhorn: Låt oss kalla att int, början. STUDENT: OK. JASON Hirschhorn: Det gör mer meningsfullt för mig. Och? STUDENT: Jag sa, jag antar, int slutar. JASON Hirschhorn: int slutar. STUDENT: Jag antar, n minus 1, eller något liknande. Liksom, det sista elementet. JASON Hirschhorn: Så du skrev, int början är lika med 0, semikolon, och int slut är lika med n minus 1, semikolon. Så i huvudsak, vad vi gör Här, 0 den första positionen. Och som vi vet i matriser, går de inte upp till n, går de upp till n minus 1. Så vi har några gränser för vår samling. Och dessa inledande gränser råkar vara de ursprungliga gränserna för vårt problem. OK. Så det låter bra. Sen om vi går tillbaka till denna linje, medan längden av listan är större än 0, vilken, i stället för N, bör vi sätter in här? STUDENT: Skriv slutar minus början. JASON Hirschhorn: När slutar minus början är större än 0? OK. Och vi kunde, om vi ville göra det lite trevligare, vad annat kunde vi göra? Om vi ​​ville rensa denna kod upp lite? Hur kan vi bli av med 0? Detta är bara en fråga stil. Det är rätt just nu. STUDENTEN Ending inte lika början? JASON Hirschhorn: Vi kan göra vad? [inplacering UTTRYCKER] STUDENTEN Ending är större? JASON Hirschhorn: Ja. Vi kan bara göra när du slutar är större än början. Rätt. Vi lade början till andra sidan om det, och vi blev av med 0. Så det här bara ser en lite renare. OK. Så, medan längden på listan är 0, skrev vi som är större samtidigt som slutar än början. Vi kommer att sätta in vårt behov klamrar, och sedan det första vi vill göra är att titta på dem i en liten lista. Du? Kan du ge mig den - STUDENT: Om parentes värde hakparentes - JASON Hirschhorn: Om parenteser värde hakparentes. STUDENT: slutar delat med 2. JASON Hirschhorn: Ending? STUDENT: Jag ser ett problem med ditt - JASON Hirschhorn: OK. Tja, titta på mitten. Hur vet vi vad mitt är? Yeah. Så låt mig ta bort den koden. Hur vet vi vad mitt är? I vad som helst, när du har början och i slutet, hur tycker du att mitten? STUDENT: Du genomsnitt. STUDENT: Du lägger dem tillsammans och sedan - JASON Hirschhorn: Lägg dem tillsammans och sedan? STUDENT: Och du genomsnitt. Dela det med 2. JASON Hirschhorn: Lägg dem samman och dividera med 2. Så int mitten är lika? Tom, kan du ge den till mig? STUDENT: Början plus slutar - JASON Hirschhorn: Början plus slutar. STUDENT: Alla, hållare, delat med 2. JASON Hirschhorn: Alla, inom parentes, dividerad med två. Så det ger mig mitt av något, korrigera? STUDENT: Du måste också att runda upp. JASON Hirschhorn: Vad gör du menar, jag behöver för att runda upp det? [inplacering UTTRYCKER] STUDENT: För om det är en udda nummer, då är det som om - JASON Hirschhorn: Tja, OK. Så jag kunde runda upp. Men om det är ett ojämnt antal, 5, kan jag tar en bort från mitten. Eller om det är ett jämnt tal, snarare det är en bättre fråga. Om det är 4, har vi bara 4, kan jag ta den första "mitten", citat, unquote eller den andra "mitt" en. Antingen skulle fungera för en binär sökning, så jag egentligen inte behöver för att runda det. Men det finns en annan sak som jag måste titta på den här raden. Vi kanske inte inser det än, men vi ska återkomma till det. Eftersom denna linje faktiskt fortfarande behöver en annan sak. Men än så länge har vi skrivit fyra rader kod. Vi har fått vår början och slutar markörer. Vi har vår while-slinga, som kartlägger den direkt till vår pseudokod. Vi tittar på mitten som mappar direkt på vår pseudokod. Jag skulle säga att detta går till mitten på listan, denna rad kod. Och sedan, när vi går till mitten av listan, nästa sak vi måste göra är kontrollera om vårt värde är där för den pseudokod som vi skrev tidigare. Så hur ska vi kontrollera om vårt värde är vid mitten av listan? Du. Varför inte göra det här? STUDENT: Om vårt värde är är vid mitten är lika med vad vi än ställer in - Jag menar lika lika med - JASON Hirschhorn: Det - OK. STUDENT: Jag är inte säker på vad det variabel vi söker för även om, är att - [inplacering UTTRYCKER] STUDENTEN [OHÖRBAR]. JASON Hirschhorn: Exakt. Per funktionsdeklarationen, Vi letar efter ett värde. Så vi söker efter ett värde i en matris med värden. Så du är exakt rätt. Du kommer att göra, om det öppna föräldra värde fäste mitten stängd Fästets jämlikar lika värde, och inuti finns vad behöver vi göra? Om vårt värde är där, vad behöver vi göra? [inplacering UTTRYCKER] STUDENT: Tillbaka noll. JASON Hirschhorn: Returnera sant. STUDENT: Returnera sant. JASON Hirschhorn: Michael, vad gör denna linje göra? STUDENTEN [OHÖRBAR] programmet har körts sin gång, och det är över, och du har vad du behöver göra? JASON Hirschhorn: Programmet eller vad? I det här fallet? STUDENT: Funktionen. JASON Hirschhorn: Funktionen. Och så, för att återgå till vad som kallas den och ge den värdet sant. Exakt rätt. Main. Vad är det för typ retur av huvud, Michael? STUDENT: int, heltal? JASON Hirschhorn: int, exakt. Ett heltal. Det var bara en fråga för att se till ni har varit på toppen av det. Vad innebär det oftast tillbaka, om allting fungerar bra? STUDENT: Noll. JASON Hirschhorn: Zero. Exakt rätt. STUDENT: Om detta återkommer bara sant, det finns ingen information som ges om vad - Åh, det är bara att säga att det värde är inuti matrisen. JASON Hirschhorn: Exakt. Detta program är inte att ge information om var exakt värde är. Det är bara att säga, ja, vi hittade det, eller nej, det gjorde vi inte det. Så om antalet hittas, return true. Jo, faktiskt vi bara gjorde det riktigt snabbt med att en rad kod. Så jag ska flytta den linjen av pseudokod. STUDENT: Inte vi behöver att ändra arrayen? Det bör vara värden, inte värde, eller hur? JASON Hirschhorn: Förlåt. Tack. STUDENT: Ja. JASON Hirschhorn: Denna rad bör vara värden. Exakt rätt. OK. Så vi har tittat på mitt lista. Om antalet hittade avkastning sant. Fortsätter med vår pseudokod, om mitten är större, sök kvar. Så jag hade i här, om antalet högre, sök kvar. Konstantin, kan du ge mig denna kodrad? STUDENT: Om värdet på mitten - JASON Hirschhorn: Så om värde - om öppen paren värderar fäste mitten nära fäste - STUDENT: Är mindre än värdet? JASON Hirschhorn: Är mindre än. STUDENT: Mindre än värdet. JASON Hirschhorn: Värde. Jo, faktiskt, vill du kontrollera om numret - Ursäkta. Det är lite förvirrande. Men annars om antalet i mitt i listan är större. STUDENT: Åh, OK. JASON Hirschhorn: Jag ska ändra på det. Annars om mitten är högre, vi vill söka vänster, OK? Och vad gör vi inne detta om tillstånd? STUDENT: Kan jag göra en liten förändring till tillståndet, ändra det till annars om? JASON Hirschhorn: Else om? OK. Så här koden kommer att utföra ungefär samma. Men det fina med att använda om, annars om, annars om eller om det, annars om, annars innebär att endast en av dem kommer att kontrolleras, inte alla tre av dem, potentiellt. Och det gör det lite trevligare på den dator som är köra ditt program. Så [? Konstantin,?] Vi är inne i den här linjen, annars om värderingar, fäste mitten nära fästet är större än värdet. Vad behöver vi göra? Vi måste söka vänster. Hur gör vi det? Jag ska ge dig en start. Vi har dessa två saker som kallas börjar och slutar. Så vad som behöver hända till början? Om du vill söka till vänster om lista, får vi vår nuvarande början. Vad behöver vi göra det? STUDENT: Vi sätter början till mitten plus 1. JASON Hirschhorn: Så om vi är söka på vänster? STUDENT: Förlåt, mitt minus - så ändelsen skulle vara mitt minus 1 och början - JASON Hirschhorn: Och vad händer med början? STUDENT: Det förblir densamma. JASON Hirschhorn: Så börden förblir densamma. Om vi ​​söker vänster, vi är använder samma början - exakt rätt. Och det slutar? Tyvärr, vad betyder det slutar lika igen? STUDENT: Middle minus 1. JASON Hirschhorn: Middle minus 1. Nu, varför minus 1, inte bara mitt? STUDENTEN Den mellersta är ur bilden redan, eftersom vi hade kontrollerat att den är ute? JASON Hirschhorn: Det är exakt rätt. Den mellersta är ute ur bilden. Vi kontrollerade redan i mitten. Så vi vill inte "mitt" citat unquote, att fortsätta att vara i array som vi söker. Så det här är fantastiskt. Else om värden fäste mitten är större än värdet slutar jämlikar mitt minus 1. Jeff, hur är detta sista raden? STUDENT: Else. Värden mitten är mindre än värdet? JASON Hirschhorn: Vi ska du ger mig annat. Så om du inte ger mig - STUDENT: Så då börjar skulle vara mitt plus 1. JASON Hirschhorn: Början jämlikar mitten plus 1, återigen, för samma Anledningen till att Constantine gav oss tidigare. Och i slutet, har som inte gett mig en kodrad ännu? Returnera false, Aleha, vad vi skriver här? STUDENTEN returnera false. JASON Hirschhorn: returnera false. Och vi måste göra det, för om vi inte att den är, måste vi säga att vi hittade inte det. Och vi sa att vi ska gå tillbaka en bool, så vi har definitivt återvända en bool någonstans. Så låt oss köra den här koden. Jag är faktiskt tänker - så vi är i terminalen. Vi ska klara vårt fönster. Låt oss göra allt. Vi fann att det finns ett fel. Det finns ett fel på rad 15, förväntas semikolon i slutet av deklaration. Så vad har jag glömt? STUDENT: Semikolon. JASON Hirschhorn: Semikolon rätt upp här. Jag tror att det var Toms kod. Så Tom, [OHÖRBAR]. Skojar bara. Låt oss inte göra hela igen. STUDENTEN Vad Dropbox katalog bör vi vara på detta? JASON Hirschhorn: Så du kan bara titta på detta lite. Men återigen, om du ville flytta detta koda in din pset3 katalog för att försöka ut, det är vad jag gjorde. Om du kommer att märka här - ledsen, bra fråga. [? LS,?] Jag har här på find.c koden från denna veckas distro kod. Jag har helpers.h. Jag har en Make-fil som jag faktiskt redigerade lite för att inkludera dessa nya filer vi skriver. Allt i denna lag kommer att finnas tillgänglig, inte distributionskoden, men den nya Gör filen, den nya helpers.h filen kommer finnas tillgängliga på nätet för nedladdning. Återigen, så de är de extra koder vi har. Så gör alla, per denna linje, gör hitta, binär, val bubbla - märken alla tre av dem och sammanställer i denna körbar kod find. Så generellt, vill vi inte att direkt till check50. Vi vill köra några tester på egen hand. Men bara så att vi kan påskynda lite, check50 2013 pset3.find kommer att passera i helpers.c-- min dåliga. Jag har inte det just nu. Så vi faktiskt kommer att köra koden på riktigt. Usage.find /, vet du vad det betyder? STUDENT: Du behöver en andra kommandoraden på det. JASON Hirschhorn: Jag behöver en andra kommandorad. Och per specifikationen, jag behöver att ange vad vi letar efter. Så låt oss titta efter 42. Vi kommer att hålla den i sorterad, eftersom vi har inte skrivit ännu en sorteringsfunktion - 42, 43, 44. Och Kontroll D inte hittar nålen i höstacken. Det är illa. Det är definitivt där. Låt oss prova något annat. Kanske är det för att jag satte det i början. Låt oss göra 41, 42, 43. Så där. Man fann det. Låt oss uttrycka det i slutet nu, bara så att vi kan vara noggrann - 40, 41, 42. Hittade inte nålen. Så jag nämnde detta tidigare. Tyvärr visste jag detta skulle hända. Men för pedagogiska ändamål, det är bra att utforska den. Det fungerar inte. Av någon anledning, kan inte hitta den. Vi vet vad som finns där, men vi inte hitta den. Så en sak vi kan göra är att gå igenom GDB för att hitta den, men inte vem som helst, utan att gå igenom GDB, ha en känsla av var vi skruvas upp? [? Madu? ?] STUDENT: Jag tror att det kan bli när man slutar är lika med början, och det är bara en en-inslag listan. Då är det bara ignorerar det istället att faktiskt kontrollera det. JASON Hirschhorn: Det är exakt rätt. När avslutningen är lika med början, gör vi fortfarande har en del i vår lista? STUDENT: Ja. JASON Hirschhorn: Ja, i själva verket är vi har en och endast en del. Och det kommer sannolikt att hända när, per koden som vi testade, vi är på framför höstacken eller vid slutet av höstack. Det är där början och slut kommer att lika en, med binär sökning. Så i dessa två fall är det inte fungerade, eftersom sinande var lika med början. Men om sinande är lika med början, gör detta medan loop köra? Det gör det inte. Och vi kunde ha kontrollerat det igen genom GDB. Så hur kan vi åtgärda det här koden, eftersom när medan slutar är lika med början, vill vi också här while-slinga för att köra. Så vad fix kan vi göra till linje 18? STUDENTEN [OHÖRBAR] är större än eller lika med. JASON Hirschhorn: Exakt rätt. Medan sluttid är större än eller lika med början. Så nu ser vi till att få det hörn fall i slutet. Och låt oss se. Låt oss köra det en gång till. Låt oss göra allt. Återigen måste du bara följa med här. Hitta 41 denna gång. Bara hålla det konsekvent. Hitta 42. Låt oss uttrycka det i början - 42, 43, 44. Vi fann det. Så det var verkligen förändringen vi behövde göra. Det var en hel del kodning vi precis gjorde, binär sökning. Är det någon som har några frågor innan Jag går vidare in i rader som vi skrev i binär sökning, eller hur vi tänkte ut vad vi räkna ut? Innan vi går vidare vill jag också peka att i stort, vi kartlagt vår pseudo-kod en till en på vår kod. Vi hade så knepig sak att räkna ut med börjar och slutar. Men hade ni inte listat ut det, du skulle ha skrivit ganska mycket identisk kod, med undantag för de två översta raderna. Och då skulle du ha insett när du gjorde det i kontroller och fall som du behöver något annat. Så även om du hade följt vår pseudo-kod rad för rad, skulle du har fått alla utom två rader koda du behövs för att skriva. Och jag skulle vara villig att satsa att ni skulle ha räknat ut det ganska snabbt, att du behövs för att sätta någon form av markör i det att räkna reda på var du var. Det igen, är kraften i att göra pseudo-kod i förväg. Så vi kan göra logiken först, och sedan Vi kan oroa syntaxen. Hade vi varit förvirrad om logiken samtidigt som man försöker att skriva denna kod i C, vi skulle ha fått alla trasslat till. Och då vi skulle ställa frågor om logik och syntax och meshning dem alla tillsammans. Och vi skulle ha blivit förlorade i vad som kan snabbt bli en mycket svårt problem. Så låt oss gå vidare nu till val av sort. Vi har 20 minuter kvar. Så jag har en känsla av att vi inte kommer att kunna få igenom alla val slag och bubbel sort. Men låt oss åtminstone försöka för att avsluta val sortera. Så genomföra val sortera använder Följande funktionsdeklarationen. Återigen, detta tas från problem set specifikation. Int värden är konsoler, är en array av heltal. Och int.n är storleken på matrisen. Urval sort går att sortera denna array. Så enligt vår mentala modell av val sortera, vi drar - Först går vi igenom listan den första tid, hitta det minsta antalet, lägga den i början, hitta den andra minsta antal, lägga den i andra plats om vi vill sortera i stigande ordning. Jag tänker inte tvinga dig att skriva pseudo-kod just nu. Men innan vi gör koden som en klass i fem minuter, kommer vi att skriva pseudo-kod så att vi har någon mening om vart vi ska. Så försök att skriva pseudokod på egen hand. Och sedan försöka vända det pseudo-kod i kod. Vi kommer att göra det som en grupp i fem minuter. Och naturligtvis, låt mig veta om du har några frågor. STUDENT: Att det? JASON Hirschhorn: Se hur långt du kan komma i två minuter. Jag förstår att du inte kommer att kunna avsluta. Men vi kommer att gå över det här som en grupp. Du är all kodning så [OHÖRBAR], så jag är ledsen att pausa det du gör. Men låt oss gå igenom det här som en grupp. Och återigen, binär sökning, ni alla ger mig en om inte flera rader kod. Tack för det. Vi kommer att göra samma sak här, kod tillsammans som en grupp. Så val sort - låt oss skriva några snabba pseudo-kod. Per mental modell, kan någon ge mig den första raden i pseudo-kod, tack? Vad vill jag göra? STUDENT: Även om listan är i ordning. JASON Hirschhorn: OK, medan listan är i ordning. Och vad menar du med "out of order?" STUDENT: Även om [OHÖRBAR] har inte sorterats. JASON Hirschhorn: Medan listan är ur funktion, vad gör vi? Ge mig den andra raden, snälla, Marcus. STUDENT: Så hitta nästa minsta talet. Detta kommer att vara indragna. JASON Hirschhorn: Så hittar Nästa minsta talet. Och sedan någon annan? När vi hittar den näst minsta nummer, vad gör vi? Jag kommer att säga hitta det minsta antalet. Det är vad vi vill göra. Så hitta det minsta antalet. Men vad ska vi göra? STUDENTEN [OHÖRBAR] till början. JASON Hirschhorn: Förlåt? STUDENT: Lägg den i början av listan. JASON Hirschhorn: Så placera den i i början av listan. Och vad gör vi med den saken det var i början på listan, eller hur? Vi ska skriva över något. Så var ska vi sätta det? Ja, Anna? STUDENT: Var det minsta Antalet var? JASON Hirshhorn: Så sätter början av listan där minsta talet var. Så när listan är i ordning, hitta det minsta antalet, placera den i i början av listan, placera början av listan där minsta talet var. Marcus, kan du formulera om denna linje medan listan är ur funktion? STUDENT: Även om siffrorna har inte sorterats? JASON Hirshhorn: OK, så för att vet att siffrorna inte har varit sorteras, vad behöver vi göra? Hur mycket behöver vi gå igenom den här listan? STUDENT: Så jag antar att en for-loop, eller samtidigt, medan siffrorna kontrolleras är mindre än längden av listan? JASON Hirshhorn: OK, det är bra. Jag tror att jag misphrased min fråga dåligt. Jag försökte bara komma på vi kommer att behöva gå igenom hela listan. Så medan listan är ur funktion, för mig är svårt att kartlägga den. Men i grund och botten, det är hur Jag tycker om det här. Gå igenom hela listan, hitta minsta antalet, placera den i början - faktiskt, du har rätt. Låt oss sätta dem båda. Så när listan är i ordning, vi behöver gå igenom hela listan gång, hitta det minsta antalet, plats den i början av listan, sätta början av listan där minsta antal var, och sedan om den Listan är fortfarande ur funktion, vi har fick gå igenom detta processen igen, eller hur? Det är därför val sortera, Big-O runtime av urvals sortera, någon? STUDENT: n kvadrat. JASON Hirshhorn: n i kvadrat. Eftersom som Marcus och jag bara insåg Här kommer vi att behöva gå igenom listan listan antal gånger. Så gå igenom något av längden n n antal gånger är faktiskt n kvadrat. Så det här är vår pseudokod. Det ser mycket bra ut. Är det någon som har några frågor om pseudokoden? Eftersom faktiskt urval sort bör förmodligen komma 1-1, kod från pseudokod. Så några frågor om logiken i pseudokoden? Fråga nu. Val av sort - medan listan är ute av ordning, vi kommer att gå igenom den och hitta den minsta varje gång och lägga den i fronten. Så medan listan är ur funktion, kan någon ge mig den kodrad som har inte gett mig en linje av koden ännu, snälla? Det låter som en vad? STUDENT: Det är en for-loop. JASON Hirshhorn: Det låter gillar en for-loop. OK, kan du ge mig den för loop? For - Elev: Jag är lika med 0. JASON Hirshhorn: i eller - Vad är det vi saknar? Vad går just här? STUDENT: Int. JASON Hirshhorn: Exakt. (Int i = 0; - STUDENT: i