JASON HIRSCHHORN: Welcome til uge tre, alle sammen. Vi har en travl men spændende sektion foran os. Så det første, fordi vi har gjort nogle fremskridt med kurset, men vi har stadig har en masse at lære tilbage at gøre, er jeg kommer til at vise jer nogle ressourcer der skulle vise sig at være utrolig nyttigt, da du ikke kun nærmer dig din Problemet sætter, men også fordøje alle det materiale, vi giver jer i foredrag og shorts og afsnit. Så vi kommer til at tilbringe de første 20 til 25 minutters afsnit går over GDB, som du måske eller måske ikke har anvendes på dette tidspunkt, men det er en utroligt nyttigt værktøj, der vil hjælpe dig debug dine programmer. En masse af jer måske har brugt printf i midten af ​​dit program til at regne ud af, hvad en variabel umådeholdent. GDB er endnu bedre end printf og ikke skrue op din kode, fordi du køre det på en eksekverbar fil. Så vi vil gå over de 10 mest nyttige kommandoer, du har brug for GDB, og vi er kommer til at gå på en øvelse sammen, så i problemet sæt tre og videre, du kan bruge GDB at hjælpe debug dine programmer. Og endelig, vi kommer til at gå over nogle sortering og søgning algoritmer at du så i foredrag, og vi er vil faktisk kode, ikke blot pseudokode, men kode binær søgning, boble sortere, og udvælgelse slags. Så det første, jeg ønsker at gå over ressourcerne. Dette er en omfattende liste, og det er mindre skrift, fordi jeg havde en masse at passe på her. Men disse vil ikke kun hjælpe dig, igen, med problemet sæt og fordøje de oplysninger, du har lært, men afgjort, kom quiz tid, vil disse være utrolig nyttigt. Så det første, foredraget noter. Hvis du går til cs50.net/lectures og rulle til den pågældende uge og dag, vil du se at der er bemærkninger til de enkelte foredrag, der er ikke blot en transkript, men en redigeret version af hvad der blev dækket i foredrag med kode snippets og andre nyttige godbidder. Jeg kan varmt anbefale at gå over dem. Og så så godt, er der kildekode tilgængelig fra hver forelæsning. Og igen, vil disse dias også være tilgængelig online på cs50.net/sections denne aften. Så sekund er de shorts hver uge, dækker emner, som regel 5 til 15 minutter i længden. Og dem, forhåbentlig vil give dig en stor primer på forskellige emner. Tredje - og det er helt nyt denne år - er study.cs50.net. Hvis du ikke har tjekket det ud, jeg varmt anbefale, at du gør det. Du kommer til at vælge et emne. Vi har dusinvis af emner på der. Så du for eksempel vælge Funktioner. Det giver dig nogle dias og noter om funktioner. Det er faktisk de dias, TFs opfordres til at bruge under vores præsentationer i afsnit. Der er også tips og tricks til at håndtere med funktioner, og der er praksis problemer, der hjælper du arbejder med funktioner. Vi giver dig også links til kort på funktioner og de tidspunkter, der fungerer er kommet op i foredraget. Så study.cs50.net Nybygget dette år, en fantastisk ressource. Dernæst har jeg mand, som er den manuelle kommando, som du kan køre på kommandolinjen. Så hvis du har spørgsmål om en kommando for eksempel rand, som vi stødte i sidste uge under sektion og du har sandsynligvis stødt på dit problem sæt, når der går gennem generere kode, men hvis du skriver mand rand, får du den side, fortæller dig alt om rand. Det giver dig, hvad det tager, det parametre, det tager, samt afkast type og en kort beskrivelse af denne funktion. Så tjek rand. Det kan være lidt ordrige og forvirrende, så nogle gange finder jeg, at simpelthen at google, hvad jeg ønsker at vide er den bedste måde at finde svaret. Så praksis med Google. Få gode hos Google. Det vil blive din bedste ven. Samt Google, hvis du ikke kan finde det på Google, cs50.net/discuss, det er diskussionsforum. Chancerne er, hvis du har et spørgsmål, en dine 700 + peers har også at spørgsmål og kan have bedt allerede i diskutere fora og har det besvaret. Så hvis du har et almindeligt spørgsmål eller du har et spørgsmål som du mener måske andre mennesker måske har kørt ind, tjek cs50.net/discuss. Endelig er den sidste to, hvis du vil tale med en virkelig menneske, kontor timer mandag til fredag. Der er også online kontortid for udvidelse studerende. Og sidst men bestemt ikke mindst, mig, udråbstegn. Du har alle mine kontaktoplysninger. Hvis du har brug for noget, bedes du aldrig velkommen til at kontakte mig. Altid velkommen til at gøre det. Meget få af jer har tilføjet mig på Gchat, så der har været skuffende, men forhåbentlig, der vil skifte mellem dette og næste afsnit. Eventuelle spørgsmål, så langt på ressourcerne? Store. Endelig et andet stik til feedback, sayat.me/cs50. Du kan give mig anonym tilbagemelding om, hvordan jeg gør. Det var virkelig nyttige i sidste uge. Jeg fik et par kommentarer fra jer lige efter sektion, plus fra andre studerende, der så det i løbet af ugen, og det var utroligt hjælpsomme. Jeg vil forsøge at begrænse min brug af ordet "sød", men jeg vil vise min entusiasme og begejstring på andre måder. Men der var andre yderligere materielle feedbacks, både plusser og Delta. Så please, jeg giver jer tilbagemeldinger på dit problem sæt. Du er velkommen til at give mig feedback på min undervisning. Jeg er her for jer. Store. Det er alt jeg har for den første sektion. Er der nogen har nogen spørgsmål indtil videre? Og jeg har en note til vagtcentralen. Extension studerende har messaged mig siger, at de får ikke nogen lyd, men der er ude af min magt at fastsætte. Så forhåbentlig, der får løst inden længe. Hvis du ser online, hej, men du kan ikke høre mig. Så først skal vi at gå gennem GDB. GDB, som jeg antydede tidligere, er et fejlfindingsværktøj meget bedre end printf. Så for at komme i gang med GDB, gutter, hvis du ønsker at åbne op dit apparat og tage den fil, jeg sendt til dig tidligere - denne fil vil også være tilgængelig online i en bit - og køre GDB. / navnet på filen. Først, selvfølgelig, er du nødt til at kompilere fil fordi GDB fungerer kun på eksekverbare filer. Men hvis du nogensinde ønsker at starte GDB, den første ting du gør, du kører GDB. / Cæsar. Så det er navnet på det program, vi er kommer til at gå med det lige nu. Så jeg har tænkt mig at skrive gøre Cæsar, som vil give mig en eksekverbar fil her markeret med grønt. Og så har jeg tænkt mig at køre GDB. / Cesar. Og der du går. Du kan se vi har noget tekst fortæller mig om den version af GDB, giver mig nogle oplysninger om garanti, og så vi har BNP prompt, som ser slags ligesom vores kommandolinje prompt, men du kan se det er åbent paren, GDB, tæt paren. Før vi fortsætter, og debug denne fil som jeg sendte til jer alle, lad os se på nogle nyttige kommandoer, så vi har en fornemmelse af det, vi kommer til at dække. Disse kommandoer er vist her i rækkefølge, som jeg normalt bruger dem. Så jeg starter mit program ved at køre GBD. / Navnet på det program, i dette tilfælde, Cæsar. Og så den første ting jeg gør 99,9% af tiden er typen pause betyder. Det sætter en pause punkt på main. Væsentlige, hvad du laver der er programmet vil stoppe ved vigtigste, så du kan begynde at undersøge det linie linje, snarere end at køre alle vejen igennem. Du kan bryde på forskellige din kode, men vigtigste er generelt en godt sted at starte. Den næste kommando jeg kører køres. Det starter programmet kører, og hvis du har brug for at indtaste kommandolinjen argumenter, du kører det på den kommando. Løb med argumenterne. Så da vi skal over en version af C, som er det program, du fyre skrev for PSET to - denne ene, selvfølgelig, har nogle bugs i det, som forhåbentlig finder vi - vi kommer til at køre løb med en kommando line argumenter fordi Cæsar, som du fyre vide per problemet sæt spec, tager nogle kommandolinjeargumenter. De næste par kommandoer, den næste man faktisk kaldes næste. At man tager dig linje for linje gennem dit program. Så rammer n derefter på Enter tager dig til næste linje, udførelse den foregående linje. Step tager du ikke kun til den næste linje, men det tager dig inde funktioner. Så hvis du har skrevet en funktion i din kode, eller hvis du ønsker at udforske en til i, for eksempel, kan du hit s, og snarere end at gå til den næste linje den fil, du går igennem lige nu, vil du faktisk træde ind denne funktion, og se sin kode. Listen viser dig, i meget brugervenlig format, de 10 eller deromkring linjer omkring hvor du i øjeblikket er i din kode så du kan faktisk se filen snarere end at skulle skifte tilbage og tilbage mellem forskellige synspunkter. Print er ligesom printf, som navnet antyder. Det viser dig, hvad en variabel lig. Info lokale er virkelig nyttige. Dette er en særlig udgave af print. Info lokale viser dig alle de lokale variabler, udskriver dem alle ud for dig der findes i øjeblikket. Så jeg generelt, snarere end at skulle udskrive de fire variable, som jeg er nysgerrig, hvis jeg er i en for-løkke, for eksempel, jeg bare skrive info lokalbefolkningen, og det vil vise mig, hvad min counter i lig, samt array, at jeg er arbejder på ligemænd. Endelig fortsætter. Typing pause stopper dig ved knækpunkt. Du kan gå igennem linje linje med næste og trin. Fortsæt kører programmet til din næste knækpunkt eller indtil afslutningen, hvis der ikke er flere break point. Disable fjerner break point, hvis du besluttede pause på vigtigste var upassende, du ønsker at sætte den et andet sted. Og endelig q, holde op, får ud af GDB. Så dette program,. / Cæsar, vi at se igennem lige nu, og vi vil bruge GDB at finde bugs i dette program. Jeg kørte dette program tidligere med Check 50, og jeg fik en panderynken. Alt det eksisterede, er det kompileret, det bestået en masse af prøverne, men for eller anden grund, var det ikke passere den femte test, drejning BARFOO alle caps, i E-D-U-I-R-R, alle kasketter, bruge tre som en nøgle. Jeg fik temmelig tæt på. Jeg slap med et bogstav. Så der er nogle små fejl i her. Jeg har kigget igennem min kode. Jeg kunne ikke regne det ud. Forhåbentlig kan du fyre hjælpe mig regne ud, hvad denne fejl er. Så det er den fejl, vi er søger efter. Lad os flytte ind GDB. Igen, jeg har kørt GDB. / Cæsar, så nu er vi i GDB. Og hvad er den første ting jeg skal gøre? Jeg har netop indgået GDB. Nogen give mig en god kommando til at komme ind. STUDENT: Break main. JASON HIRSCHHORN: Break main. Fantastic. Lad os skrive det i. Du fyre kan se op her, eller følg sammen på dine computere. Break vigtigste, og du vil se en break point blev sat til - det giver mig nogle underlige hukommelse adresse, og det giver mig også den linje nummer. Hvis jeg skulle se tilbage på denne fil, Jeg ville indse, at main skete på linie 21. Hvad skal jeg køre næste? Er mit program kører? Nej. Så hvad skal jeg køre næste? STUDENT: Kør. JASON HIRSCHHORN: Kør. Skal jeg bare køre løb, eller skal Jeg tilføje nogle andre ting i? STUDENT: Løb med argumentet. JASON HIRSCHHORN: Løb med kommandoen argumenter. Og da jeg debugging en meget specifik tilfælde, skal jeg indtaste det kommandolinje argument. Så jeg vil løber tre, der er, igen, output jeg fik fra Check 50. Start program. Vi går gennem et par linjer. Du vil nu se, at vi er på linie 21. Hvordan kan jeg vide, at vi er på linje 21? Fordi hvis man ser til venstre af min terminal vindue, der det siger linie 21. Og det giver mig, faktisk, det kode, der er på linie 21. Så jeg misspoke tidligere. Main er faktisk ikke på linie 21. Main er et par linjer over 21.. Men på linje 21, der er hvor vi bryder. Denne linje kode har endnu ikke udført. Det er vigtigt. Den linje, du ser ikke har blevet henrettet endnu. Det er den næste linje kode du er ved at udføre. Så den næste linje, som du fyre er sikkert bekendt med, er dette tilstand kontrol for at se, om jeg har indtastet en kommandolinje argument. Og et til i, hvad der er den anden en del af, at gøre? Hvad er en til i? STUDENT: at ændre det til et heltal. JASON HIRSCHHORN: Undskyld? STUDENT: Det ændrer den argument til et heltal. JASON HIRSCHHORN: Så en til i skifter arg v1 fra en streng til et heltal. Og hvad er det kontrol? STUDENT: Hvis der er en anden kommandolinjeargument, bortset fra at køre programmet. JASON HIRSCHHORN: Og hvad er i anden halvdel af dette Boolsk udtryk kontrol? Denne del herovre, en for jeg? STUDENT: Hvis det er negativt. JASON HIRSCHHORN: Making sikker på hvad? STUDENT: At sikre det er i virkeligheden positivt. JASON HIRSCHHORN: Præcis. Dette er kontrol for at se, om det er negativ, og hvis den er negativ, jeg har en fornemmelse af den næste linje magt være mig råben på brugeren. Så lad os ramte ende at udføre denne linje. Vi kan ikke se, at linje, som du fyre måske forventet at se råben på bruger og derefter vender tilbage, fordi denne linje ikke udføre. Jeg trådte 3. Så jeg havde faktisk indtaste to kommando line argumenter, og 3 er større end nul. Så vi så, at linje, vi henrettet, men vi havde ikke træde inde i hvis betingelse. Så nu, næste, jeg ser jeg indstilling int nøgle svarer til en til i arg v1. Så det er mig skabe en variabel nøgle. Så hvis jeg udskrive nøgle lige nu, fordi der giver dig mulighed for at se den værdien inden variablen, nøgle er lig 47.. Det er underligt, men selvfølgelig, det er fordi jeg ikke har henrettet denne linje endnu. Så nu, hvis jeg ramte n, udføre denne linje, og gøre print nøgle, vil nøgle lig 3, hvilket er, hvad vi forventer, at lig. Så igen i GDB, den linje, du se, du ikke har udført endnu. Du er nødt til at slå n eller s eller et nummer af andre kommandoer til faktisk udføre den pågældende linje. Print nøgle. Keys ved 3. Så langt, så godt. String er almindelig tekst. Lad os udføre denne linje. Jeg får en snor fra brugeren. Lad os se i min Check 50, jeg indtaste BARFOO alle caps, så det er, hvad jeg vil komme ind. Hvis jeg nu udskrive almindelig tekst. Du vil se det er lig en streng. Det giver mig nogle andre underlige hexadecimal nummer, men det gør i Faktisk sige, at min streng er BARFOO. Hvis jeg ønskede at se, hvad nøglen svarede på dette punkt, hvordan kunne jeg tjekke nøgle? STUDENT: Print nøgle. JASON HIRSCHHORN: Print nøgle, nøjagtigt. Og faktisk, der er en genvej. Hvis du bliver træt af at skrive print, du kan bare skrive p. Så p nøgle gør nøjagtig de samme ting. Og igen, jeg ser det er lig 3. Hvis jeg ønskede at finde ud af, hvad både nøgle og BARFOO svarede samtidig men jeg var træt af at skrive hver én ud enkeltvis, I kunne skrive info lokalbefolkningen. Det giver mig vigtige ligemænd 3. Almindelig tekst lig BARFOO. Det giver mig også disse to underlige ting i toppen, denne variabel i og denne variabel n.. De er faktisk eksisterende i min hovedprogrammet. Vi har ikke mødt dem endnu, men som et eksempel, der eksistere i min for-løkke. Så lige nu, de lige nogle underlige tal, fordi de ikke har været initialiseret endnu, men de findes stadig i hukommelsen, så de er bare sat nogle skrald værdi. Men vi kan se nøglen i almindelig tekst lige der. Så jeg har tænkt mig at udføre denne linje, linie 34, for-løkken. Vi kommer til at springe i for loop ved at trykke n. Og vi er inde i for-løkken. Vi er på vores første check. Og igen, bør disse slags kigge velkendt for dig, fordi det var en Cæsar-program, der blev skrevet, men igen, har en slags bug. Og nu, hvis jeg gør info lokalbefolkningen, fordi jeg er indeni, der for-løkke, vil du se at jeg er lig med nul, som vi forventer. Det er, hvad vi satte det til og initialiseres det i for-løkken. n er lig med 6. Det giver også mening, fordi vi har sat det til strlen almindelig tekst. Så jeg kan lide at gøre info locals eller udskrive til variabel ofte for at sikre, at alt er altid hvad Jeg forventer, at det lige. I dette tilfælde, er alt hvad jeg forventer, at det lige. Så lad os begynde at bevæge sig gennem dette for løkke. Den linje jeg er på er linie 36, hvis almindelig Teksten i er større end en og almindelig Teksten i er mindre end eller lig med z. Jeg kender mit problem er ikke med min første brev, er det med det andet bogstav. Hvis vi ser tilbage på Check 50 B går til E fint. Jeg tager A og lade det som en A, ikke ændrer det til D. Så noget er galt med det andet bogstav. Så jeg har tænkt mig at flytte der i en anden. Men hvis jeg havde lyst til at kontrollere, hvad almindelig tekst, jeg svarede i dette særlige tilfælde, jeg mener, det bør være, hvad? Hvad skal almindelig tekst jeg lige i dette første runde gennem for-løkken? STUDENT: Zero? JASON HIRSCHHORN: Almindelig tekst af I? Så det bør være hovedstad B. Jeg, selvfølgelig, lig med nul, men almindelig tekst beslag nul lukket beslag lig B fordi strenge, som vi så i sidste uge, er array, så vi får den første tegn fra det. Så igen, hvis jeg udskrives almindelig tekst af Jeg, jeg gør i virkeligheden, får karakter B. Og det er pæn, ikke? Jeg har faktisk ikke almindelig tekst I. Det er ikke en af ​​de variabler, jeg sat eller initialiseret, men du kan udskrive ud af en hel række ting hvis du gerne vil. Men lad os komme igennem. Hvis almindelig tekst I er større end A og klartekst I er mindre end eller lig med Z, der klart er sandt, fordi vi har en kapital B. Jeg har tænkt mig at køre en kommando på den. Vi så, at matematik i sidste uge, så vi vil tager det for givet, at det virker ret i henhold til check 50 år. Disse krøllede parenteser, den første viste, at jeg var afslutter hvis tilstand, den anden viste at jeg forlader for-løkken. Og så nu når jeg ramte Dernæst vil vi se Vi er tilbage på for-løkken igen. Vi går gennem for loop igen. Lad os faktisk træde ind i anden iteration af for-løkken og type info lokale. Så vi er i den anden iteration vores for loop. Jeg er lig med 1, som vi forventer. N er lig med 6, som vi forventer. Key lig 3, som vi forventer. Og almindelig tekst, vil du se, lig EARFOO nu, ikke BARFOO længere, fordi i vores tidligere iteration, B var ændret til et stort E. Så vi er ved at støde på problemet, så det er, hvor vi kommer til at dykke ned i debugging. Men nogen har nogen spørgsmål om, hvad vi har gjort hidtil? Fantastic. Så vi er ved at udføre dette, hvis betingelse, almindelig tekst beslag jeg lukkede beslag større end A og almindelig tekst I mindre end eller lig med Z. Men før Jeg går ind i det, fordi det er her Jeg kender min fejl er, vil jeg påpege ud almindelig tekst af I. Så lad os sætte udskrive. Det gør lig tegnet A, således at synes så langt, alt er godt og rigtigt. Så jeg forventer, at denne linje pr min logik, denne linje skal være sandt. Det er et stort bogstav. Men hvis jeg ramte n, vi indse, at dette linje, i virkeligheden, ikke udføre. Jeg sprang ned til andet, hvis. Hvorfor skete det? STUDENT: Fordi du har din tilstand af almindelig tekst er større end A, ikke lig med eller større end. JASON HIRSCHHORN: Så jeg havde min almindelig tekst I er større end A, ikke er større end eller lig med. Så klart, hovedstaden A ikke gjorde udløser dette, hvis tilstand, og det gjorde vi ikke træde ind i det, og det gjorde vi ikke gøre det nødvendige skift. Så det er det, faktisk. Jeg regnede ud af min bug. Jeg kunne gå tilbage i min kildefil, ændre det, og opdatere den og køre Tjek 50 igen. Men vi vil se, bare for pædagogik s skyld, hvis jeg holde. Det andet, hvis ikke udfører enten, men hvad stedet lig er kommandoen der ikke ændrer sig. Så det er ikke ændret på alle, og hvis jeg udskrive almindelig tekst her, vil vi se at gå ved at for-løkken ikke i virkeligheden, ændre det andet tegn på alle. Det er stadig en kapital A. Så igen, vi fejlrettet vores fejl. Vi indså, at der var vis logik mangler. Og vi fejlrettet det forud for tid, før faktisk udfører denne linje, men du ville have bemærket havde vi bare hit Next og hoppe til det andet, hvis det betyder, at at hvis betingelse var ikke sandt. Vi havde ikke i virkeligheden, får det resultat, vi havde forventet. Så vi kunne have været bedt om det, havde vi ikke været så klog, at se på at hvis tilstand og kontrollere, om i virkeligheden, vores tilstand bør evaluere på sandt i den aktuelle kontekst. Det er alt for debugging dette program. Er der nogen, der har nogen spørgsmål? Hvad kommando kunne jeg ramt at afslutte GDB? Q. Og så vil jeg blive bedt om, Afslut alligevel? Ja eller nej. Jeg får ramt ja, og jeg er holdt op GDB. Så det var en hurtig primer til GDB. Faktisk, i en virkelig situation, Jeg gjorde det på kontortid. Jeg GDBed netop dette program på kontortid med en elev. Og hvis vi går tilbage til de kommandoer, vi så før, vi brugte pause vigtigste først ting vi gjorde. Vi brugte køre med kommandolinjeargumenter, anden ting, vi gjorde. Vi brugte næste en masse at flytte os gennem linjer. Og igen, den korte version næste er n. Det er i parentes gråt på diaset. Vi brugte ikke skridt, men det gjorde vi ikke nødvendigvis i denne sag. Men vi kan bruge det i en lidt senere på i dag, hvis vi debugging for eksempel binær søgning, når binær søgning kaldes i en separat funktion, men der er nogle fejl med det. Vi kommer til at ønsker at træde ind i opkaldet til binær søgning og faktisk debug det. Liste vi ikke bruge enten fordi vi havde en god fornemmelse af vores kode, men hvis jeg ønskede at få en fornemmelse af, hvad kode jeg var omkring, kunne jeg bare bruge listen. Udskriv vi brugte, info locals vi brugt. Fortsæt vi ikke behøver at bruge i denne tilfælde heller ikke vi skal bruge deaktivere, men vi gjorde brug afslutte. Igen, disse 10 kommandoer, praktisere dem. Hvis du forstår disse 10 kommandoer, du skal være indstillet til debugging enhver Problem med GDB. Så vi er ved at gå på igen, til det springende punkt i dag, at gå over disse sortering og søgning algoritmer. Før vi gør det, igen, spørgsmål, kommentarer, bekymringer for GDB? Så er alle kommer til at bruge GDB snarere end printf? Så alle, for evighed skyld, alle nikker deres hoved ret nu, så jeg vil se dig på kontortid og alle TFS vil se dig og de vil sige, vise mig, hvordan man bruger GDB, og du vil være i stand at vise dem, right? Slags? Måske forhåbentlig. Fedt. Så vi kommer til at flytte ind sortering og søgning. Du vil se, at jeg har en liste allerede sorteres for os, men det vil ikke at være tilfældet altid. Så i det problem indstillet specifikation for problem sæt tre, du har shorts at du kan se, og det faktisk beder dig om at se disse shorts. Også i foredrag i sidste uge, gik vi over en masse af disse algoritmer, så jeg er ikke kommer til at tilbringe tid i klassen går i løbet af disse algoritmer igen eller tegning billeder til hvordan disse algoritmer virker. Igen, at oplysninger, kan du re-watch foredrag, eller at oplysninger er fanget fremragende på shorts for disse søgninger, som alle som er tilgængelige på cs50.net. Så i stedet for, hvad vi vil gøre, er at skrive disse programmer. Vi har en følelse, en mental model af, hvordan de arbejder, og så hvad vi vil at gøre, er at kode dem for alvor. Vi kommer til at dreje, at mental model, det billede, hvis du vil, i det faktiske kode. Og hvis du var lidt forvirret eller diset på det mentale model, jeg er helt forstå. Vi er faktisk ikke kommer til at springe til kode samme. Så mens denne prompt i dette dias spørger du at kode binær søgning, og faktisk en iterativ version af binær søgning, den første ting jeg virkelig ønsker dig at gøre, er skrive nogle pseudokode. Så du har denne mentale model hvordan binær søgning værker. Tag et ark papir, hvis du har en let tilgængelig, eller åbne en tekst editor, og jeg vil gerne alle til at skrive. Tage fire minutter til at skrive pseudokode for binær søgning. Igen, så tænk på, at mental model. Jeg kommer rundt, hvis du har spørgsmål og vi kan tegne billedet ud. Men først, før vi begynder at programmering, Jeg vil gerne skrive pseudokode for binær søgning, så når vi dykke i, har vi nogle retning som til, hvor vi skal lede. STUDENT: Kan vi antage den vifte af værdier, vi får, er allerede sorteres? JASON HIRSCHHORN: Så for binær søgning at arbejde - glimrende spørgsmål - du nødt til at tage i en sorteret matrix af værdier. Så antager det vil virke. Vi vil gå tilbage til dette dias. Du vil se i lilla funktionen erklæringen er bool binary_search int værdi, int værdier, int n. Dette bør ser bekendt, hvis du har allerede nærmede sig eller fået din hænder beskidte med problemet sæt. Men det er din funktion erklæring. Igen, ikke skulle have behov for at bekymre sig om at meget i dette øjeblik. Hvad jeg virkelig ønsker dig at gøre er at tage fire minutter til pseudokoden binær søge, og så vil vi gå over det som en gruppe. Og jeg vil komme rundt. Hvis du har spørgsmål, er du velkommen fri til at hæve din hånd. Hvorfor tager du ikke tage to minutter mere at slutte op pseudokoden? Jeg ved, at dette kan virke latterligt, at vi bruger så meget tid på noget, der er ikke engang faktisk i C, men især for disse mere udfordrende algoritmer og problem sæt, som vi er nødt til at regne ud, starter i pseudokode ikke bekymre om syntaksen, bare bekymre sig om logik, er utroligt hjælpsomme. Og på den måde, du er ikke at løse to utroligt vanskelige problemer på én gang. Du er bare fokusere på logik, og så du flytter ind i syntaks. OK. Lad os begynde at gå igennem pseudokode. Jeg har skrevet op her, binær søg pseudokode. Vi skriver dette på bord sammen. Eller jeg vil skrive det, og du vil give mig anvisningerne, jeg har brug for. Så kan nogen give mig den første linje i pseudokode du skrev for binær søgning? Ja, Annie? STUDENT: Mens længden af listen er større end nul. JASON HIRSCHHORN: Mens længden af listen er større end nul. Og igen ser vi nogle C-leder syntaktiske ting på her. Men det meste af dette er på engelsk. Har nogen har nogen linje de lægger før dette i deres pseudo-kode? STUDENT: Få et array af sorteret numre. JASON HIRSCHHORN: Du skrev "får en vifte af sorterede numre. "Per den funktion erklæring, vil vi passerer et array af sorteret numre. STUDENT: [uhørligt]. JASON HIRSCHHORN: So vi vil have det. Men ja, hvis vi ikke har det, vi vil være nødvendigt at sortere vores udvalg af tal, fordi binær søgning kun virker på sorteret arrays. Så mens længden af ​​listen er lig med nul, er jeg kommer til at sætte nogle krøllede parenteser at gøre det ser lidt mere ligesom C. Men mens synes at kortlægge på en mens loop, så inde i dette, mens loop hvad skal vi gøre for binær søgning? Nogen andre, der ikke har givet mig en svar endnu, men der skrev dette? STUDENT: Gå til midten af ​​listen. JASON HIRSCHHORN: Tom. Gå til midten af ​​listen. Og opfølgende spørgsmål, hvad gør vi, når vi er på midt på listen? STUDENT: Har en check, om der er det nummer, du leder efter. JASON HIRSCHHORN: Excellent. Gå midt på listen, og tjek hvis vores værdi er der - fantastisk. Har nogen har noget andet der var anderledes end dette? Det er helt rigtigt. Det første, vi gør i binær søgning er at gå til midten af ​​listen og at se, om vores værdi er der. Så jeg antager, hvis vores værdi er der, hvad gør vi? STUDENT: Vi vender tilbage nul [uhørligt]. JASON HIRSCHHORN: Ja, hvis vores værdien er der, vi fandt det. Så vi kan fortælle en eller anden måde, men dette funktion er defineret, vi fortælle brugeren vi fandt det. Hvis det ikke er der, selvom, det er hvor det bliver tricky. Så hvis det ikke er der, en anden, der arbejdede på binær søgning eller har en idé nu, hvad gør vi? STUDENT: Spørgsmål. JASON HIRSCHHORN: Ja? STUDENT: Er array allerede sorteres? JASON HIRSCHHORN: Ja, vi antager array allerede sorteret. STUDENT: Så du er nødt til at kontrollere, om den værdi, du ser, er større end den værdi, du ønsker, kan du flytte til midten af ​​den anden halvdel. JASON HIRSCHHORN: Så hvis midten af listen er større end hvad vi søger, så vi hvad? Vi bevæger hvor? STUDENT: Du ønsker at flytte til den halvdel af listen med lavere antal end det. JASON HIRSCHHORN: Så vi vil kalde det venstre. Så hvis midten er større, kan vi søge venstre halvdel af listen. Og derefter ved søgning, hvad mener jeg med søgning? STUDENT: [uhørligt]. JASON HIRSCHHORN: Vi går til midten. Vi har faktisk gentage denne ting. Vi går tilbage gennem vores while-løkke. Jeg vil give dig den sidste - andet, hvis midten er mindre end hvad vi gør, hvad gør vi her? STUDENT: Gå til højre. JASON HIRSCHHORN: Søg til højre. Det ser godt ud, men nogen har noget, som vi kan mangle eller noget andet, som du sætter i din pseudo-kode? Så dette er hvad vi har hidtil. Mens længden af ​​listen er større end nul, vi kommer til at gå til midten af ​​listen og kontrollere, om vores værdi er der. Hvis den midterste er større, vil vi søg venstre, ellers hvis midten er mindre, vi kommer til at søge mod højre. Så vi har alle haft et vist kendskab til de vilkår, vi bruger i datalogi og de værktøjer, vi har. Men du vil allerede mærke at vi var tale på engelsk, men vi fandt en masse ting, som syntes at kortlægge på redskaber, vi har i vores kodning værktøjskasse. Så ret off the bat, vi er ikke vil faktisk kode endnu. Hvad ser vi her på engelsk, at kortene på ting, vi kan skrive i C? STUDENT: Mens. JASON HIRSCHHORN: Mens. Så dette, mens lige her kort på hvad? STUDENT: En while-løkke. JASON HIRSCHHORN: Et stykke loop? Eller sandsynligvis mere generelt en løkke. Vi ønsker at gøre noget igen og igen. Så vi kommer til at kode en løkke. Og vi allerede kender, fordi vi har gjort dette et par gange, og vi har masser af eksempler derude, hvor faktisk at skrive dette indeks til en sløjfe. Så det bør være temmelig nemt. Vi bør være i stand til at få det startede temmelig hurtigt. Hvad ser vi her? Hvilke andre strukturer grammatikker, tingene at vi er bekendt med i C, så gør vi allerede har en følelse af baseret off af de ord, vi har brugt? Ja, Anna? [Uhørligt] just kidding. Anna, gå videre. STUDENT: Hvis og andet. JASON HIRSCHHORN: Hvis og andet - lige her. Så hvad gør de ud? STUDENT: An hvis ellers erklæring. JASON HIRSCHHORN: Ja, betingelser, right? Så vi vil sandsynligvis nødt til at skrive nogle betingelser. Og igen, selvom måske forvirrende ved første, vi generelt har en mening nu af hvordan man skriver betingelser og syntaksen for forhold. Og hvis vi ikke gør det, vi bare kigge op syntaks for forhold, klippe og indsætte at fordi vi ved, at vi brug for en betingelse her. Alle andre ting, vi ser, at kortet på ting, vi måske nødt til at gøre i C? Ja, Aleha? STUDENT: Det kan være indlysende, ved blot at kontrollere, hvis en værdi er lig med noget. JASON HIRSCHHORN: Så hvordan kan vi kontrollere og - så gå til midten af ​​listen og kontrollere, hvis vores værdi er der? Hvordan gør vi det i C? Hvad er syntaksen for det? STUDENT: Lig, lig. JASON HIRSCHHORN: Lig, lig. Så denne kontrol er sandsynligvis kommer at være et lighedstegn, lig. Så vi vil vide, at vi har brug for, at et eller andet sted. Og faktisk, bare i at skrive det, vi ser de andre ting. Vi er nødt til at gøre nogle sammenligning operatører derinde - fantastisk. Så det faktisk ser ud, ved og stor, har vi ikke skrevet en ord af C-kode endnu. Men vi fik den mentale model ned via foredrag og disse shorts. Vi skrev pseudo-kode som en gruppe. Og allerede, vi har 80%, hvis ikke 90% af, hvad vi skal gøre. Nu er vi bare nødt til at kode det, som igen er en ikke-trivielt problem at løse. Men i det mindste er vi fast på logik. Mindst nu når vi går til kontortid, Jeg kan sige, jeg ved hvad jeg har brug for at gøre, men du kan minde mig af syntaksen? Eller selv om der overfyldt kontortid, du kan google for syntaks, snarere end at blive hængende på logik. Og igen, snarere end at forsøge at løse logik og syntaks problemer alle på én gang, er det ofte meget bedre at bryde disse to vanskelige problemer ud i to mere håndterbare dem og gøre det pseudokode først og derefter kode i C. Så lad os se, hvad jeg gjorde for pseudo-kode i forvejen. Mens længden af ​​listen er større end nul, se på den midterste af listen. Hvis antallet fundet returnerede sandt, ellers hvis tal højere, søg venstre. Else hvis antallet er lavere, søg højre, return false. Så ser næsten identiske, hvis ikke næsten identisk med, hvad vi skrev. Faktisk, Tom, hvad du sagde først, bryde midten af ​​listen, og hvis nummer findes i to erklæringer er faktisk, hvad jeg gjorde. Jeg kombinerede dem der. Jeg skulle have lyttet til du første gang. Så det er pseudo-kode, vi har. Hvis du ønsker at nu, undskyld, gå tilbage til vores oprindelige problem. Lad os kode binary.c. Så implementere en iterativ udgave af binær søgning ved hjælp af følgende funktion erklæring. Og du behøver ikke at kopiere det ned endnu. Jeg er faktisk kommer til at åbne op lige her binary.c. Så der er den funktion erklæring i midten af ​​skærmen. Og du vil se, at jeg tog pseudo-kode fra på mine sider, men næsten identiske til, hvad vi skrev, og sætte det i for dig. Så nu, lad os tage fem minutter at kode denne funktion. Og igen, hvis du har spørgsmål, hæve din hånd, lad mig vide, vil jeg kommer rundt. STUDENT: [uhørligt]. JASON HIRSCHHORN: Så jeg tog den binære søg definition på top, på linje 12. Det er, hvad jeg fik for mine dias. Og så alt dette pseudo-kode jeg lige kopieres og indsættes fra dias, pseudo-kode dias. Jeg er stadig ikke høre [uhørligt]. Så hvis du er færdig med din implementering, vil jeg tjekke det. Jeg mailede dig helpers.h fil tidligere i denne klasse. Og det vil være tilgængelige online såvel til download for mennesker ser denne sektion tid forsinket. Og jeg brugte bare den generiske fordeling kode fra pset3. Så jeg tog find.C, bruge min helpers.h fil snarere end helpers.h fil der er givet i fordelingen kode. Og jeg havde at gøre en anden ændring i find.C snarere end at ringe simpelthen søg, ring binary_search. Så hvis du ønsker at teste din kode, vide, at det er sådan, man gør det. I virkeligheden, når vi skal køre denne kode lige nu, jeg har lige lavet en kopi af min pset3 mappe, igen, byttet ud de hjælpere filer og derefter foretaget, at ændre i find.C at kalde binary_search snarere end blot at søge. JASON HIRSCHHORN: Ja. Har du spørgsmål? STUDENT: Nevermind. JASON HIRSCHHORN: Ingen bekymringer. Nå, lad os komme i gang. Vi vil kode det som en gruppe. En anden tone. Igen, dette er, kan nemt byttes i for Problem Set Tre. Jeg har min helpers.h fil, som snarere end helpers.h vi er givet, erklærer binær søgning, boble sortere og udvælgelse slags. Og i find.c du vil opdage på linje, hvad er det, linje 68, vi kalder binær søg snarere end søgning. Så igen, den kode, der er til rådighed online eller den kode, du er skaber lige nu let kan byttes i for p sæt 3 til at tjekke det. Men først, lad os kode binær søgning. Vores funktion erklæring, vi returnere en bool. Vi tager et heltal kaldet værdi. Vi tager et array af heltal kaldet værdier, og vi tager n være størrelsen af ​​matrixen. På linje 10, lige her, jeg har skarp omfatter stdbool.h. Er der nogen vide, hvorfor det er der? Så hvad betyder det linje kode gøre? STUDENT: Det giver dig mulighed for at bruge en bool returtype. JASON HIRSCHHORN: Præcis. STUDENT: Eller det er et bibliotek, der giver mulighed at anvende en bool returtype. JASON HIRSCHHORN: Så den skarpe omfatte stdbool.h linje giver mig nogle definitioner og erklæringer for ting at jeg får lov til at bruge i dette bibliotek. Så blandt dem siger, at der er denne type kaldes bool, og det kan være sandt eller falsk. Så det er hvad denne linje gør. Og hvis jeg ikke havde denne linje, jeg ville komme i problemer for at skrive dette ord lige her, bool, lige der. Præcis højre. Så jeg har brug for, at der i denne kode. OK. Så dette igen, er en iterativ version, der ikke en rekursiv én. Så lad os komme i gang. Lad os starte med denne første linje pseudokode. Og forhåbentlig vil vi - eller ikke forhåbentlig. Vi kommer til at gå rundt i lokalet. Vi vil gå linje for linje, og jeg vil hjælpe du regne ud den linje, vi har brug for skrive først. Så mens længden af ​​listen er større end nul. Lad os starte i front. Hvilken linje skal jeg skrive her, i koden? STUDENT: Mens parentes n er større end 0. JASON HIRSCHHORN: Mens n er stor end 0. Så n er størrelsen af ​​en liste, og vi tjekker, om - [indskyde STEMMER] JASON HIRSCHHORN: - undskyld? STUDENT: Hvordan kan vi vide, at n er størrelsen på listen? JASON HIRSCHHORN: Undskyld. Per PSET specifikationen søgningen og sortere funktioner du har brug for at skrive, n er størrelsen på listen. Jeg glemte at forklare det her. Men ja. n er størrelsen af listen, i dette tilfælde. Så mens n er større end 0. OK. Det kan vise sig lidt problematisk selv, hvis tingene går videre. Fordi vi vil fortsætte med at kende størrelsen på listen i denne funktion, men siger vi starter med en vifte af 5 heltal. Og vi går igennem, og vi har nu indsnævret det ned til et array af to heltal. Hvilket 2 heltal er det? Størrelsen er 2 nu, at vi ønsker at se på, men som 2 er, at? Giver det mening, det spørgsmål? OK. Jeg spørger igen. Så vi starter med denne række af 5 heltal, og n er lig med 5, right? Vi kører igennem her. vi sandsynligvis ændre størrelsen, ret, da tingene går videre. Hvilket er, hvad vi siger, vi ønsker at gøre. Vi ønsker ikke at søge fuld ting igen. Så siger vi ændre det til 2.. Vi tager halvdelen af ​​den liste, der er mærkeligt. Så bare vælge 2. Så nu n er 2. Jeg undskylder for de fattige tør slette markører. Right? Og vi søger gennem listen igen med en liste over str. 2. Tja, vores array er stadig af str. 5. Vi siger, at vi kun ønsker at søg 2 pletter i det. Så der 2 spots er dem? Giver det mening? Er de venstre 2 spots? Er det de rigtige 2 spots? Er de de 2 midterste spots? Vi har brudt problemet ned, men vi faktisk ikke ved, hvilken del af det problem, vi stadig kigger på, bare ved at have disse to variable. Så vi har brug for lidt mere derefter, mens n er større end 0. Vi har brug for at vide, hvor der n er i vores faktiske array. Så nogen har en skifte til denne linje? Det meste af denne linje er helt korrekt. Er der en anden tilføjelse? Kan vi bytte noget ud for n til gøre denne linje en smule bedre? Mm-hm? STUDENT: Kan du initialisere en variabel såsom længde til n, der vil så blive brugt senere i funktion? JASON HIRSCHHORN: Så initialisere en variabel længde n, og vi bruger det senere? Men så har vi bare opdatere længde og vi stadig løbe ind i dette problem, hvor vi skære ned på længden af ​​vores problem, men vi ved aldrig, hvor, faktisk, denne længde kort på. STUDENT: Er det ikke kommer til at ske senere, når du siger, søg venstre, søg ret? Du kommer til at gå til en anden område af dit - JASON HIRSCHHORN: Vi kommer til at gå til et område, men hvordan kan vi vide der er til at gå til? Hvis vi kun har array, og dette n, hvordan kan vi vide, hvor man gå i arrayet. I ryggen, ja? STUDENT: Har du, ligesom, en lavere grænse og en øvre grænse variabel eller sådan noget? JASON HIRSCHHORN: OK. Så dette er en anden idé. Snarere end blot at holde styr på størrelse, vi holde styr på den nedre og øvre grænse variabel. Så hvordan kan vi beregne størrelsen fra en nedre grænse og øvre grænse? [indskyde STEMMER] JASON HIRSCHHORN: subtraktion. Og også at holde styr på den nederste bundet og øvre grænse at lade os vide, Vi søger disse to? Er vi søger disse to herovre? Er vi søge på to midten? Sandsynligvis ikke de to midterste, fordi dette i virkeligheden er binær søgning. Men nu vil vi være i stand til at få den størrelse, men også for rammerne af arrayet. I det væsentlige, hvis vi har vores kæmpe telefonbog, vi rippe den i halve. Vi ved nu, hvor der er mindre telefonbog er. Men vi er faktisk ikke rippe telefonbogen i halve. Vi har stadig brug for at vide, hvor nye grænser for vores problem er. Er der nogen har nogen spørgsmål om det? Ja? STUDENT: Ville det fungere ved at skabe en variabel, i, at man så bare flytte stilling i forhold til dens aktuelle position, og længden, n? JASON HIRSCHHORN: Og hvad er jeg? STUDENT: Ligesom jeg er ligesom en slags - Ligesom du ville initialisere jeg at være den midterstilling af matrixen. Og derefter, hvis værdien på position i i midten af ​​arrayet i fundet være mindre end den værdi, du har brug for, jeg nu bliver længden af ​​array plus værdien af ​​i divideres med 2. Ligesom, se du skifte i - JASON HIRSCHHORN: Right. STUDENT: - op til - JASON HIRSCHHORN: Så jeg er næsten positive, der vil arbejde. Men pointen væsen, skal du to stykker af information her. Du kan gøre det med begyndelsen og slutningen, eller du kan gøre det med størrelse, og derefter nogle markør. Men du behøver to stykker af information her. Du kan ikke komme af med blot én. Betyder det giver mening? Så vi kommer til at gå igennem, og vi kommer til at gøre [uhørligt] og skabe nogle markører. Hvad lavede du skriver i din kode? STUDENT: Jeg sagde bare int bundet en er lig med 0. JASON HIRSCHHORN: Lad os kalde at int, begynder. STUDENT: OK. JASON HIRSCHHORN: Det gør mere mening for mig. Og? STUDENT: Jeg sagde, jeg gætte, int slutter. JASON HIRSCHHORN: int slutter. STUDENT: Jeg gætter på, n minus 1, eller noget lignende. Ligesom, det sidste element. JASON HIRSCHHORN: Så du skrev, int begynder lig 0 semikolon og int slutning er lig n minus 1, semikolon. Så det væsentlige, hvad vi gør her, 0 den første position. Og som vi ved i arrays, de ikke går op til n, de går op til n minus 1. Så vi har nogle grænser i vores array. Og disse indledende grænser tilfældigvis de oprindelige grænser for vores problem. OK. Så det lyder godt. Så hvis vi går tilbage til denne linje, mens længden af ​​listen er større end 0, hvad stedet for n, bør vi sætter i her? STUDENT: Skriv slutter minus begyndelsen. JASON HIRSCHHORN: Mens slutter minus begynder er større end 0? OK. Og vi kunne, hvis vi ønskede at gøre, at en lidt pænere, hvad ellers kunne vi gøre? Hvis vi ønskede at rense denne kode lidt op? Hvordan kan vi slippe af med 0? Dette er blot en stil spørgsmål. Det er korrekt, lige nu. STUDENT: Afslutning ikke lige begyndelse? JASON HIRSCHHORN: Vi kan gøre hvad? [indskyde STEMMER] STUDENT: Ending er større? JASON HIRSCHHORN: Ja. Vi kan bare gøre, mens slutter er større end begyndelsen. Right. Vi har tilføjet begyndt til den anden side af det, og vi sluppet af 0. Så dette ser bare en lidt renere. OK. Så mens længden af ​​listen er 0, skrev vi at mens slutter, er større end begyndelsen. Vi kommer til at sætte i vores nødvendig krøllede parenteser, og derefter den første ting vi ønsker at gøre, er at se på dem i en lille liste. Dig? Kan du give mig det - STUDENT: Hvis parentes værdi firkantet beslag - JASON HIRSCHHORN: Hvis parentes værdi firkantet beslag. STUDENT: Ending divideres med 2. JASON HIRSCHHORN: Ending? STUDENT: Jeg ser et problem med din - JASON HIRSCHHORN: OK. Tja, se på midten. Hvordan kan vi vide, hvad den midterste er? Ja. Så lad mig slette denne kode. Hvordan kan vi vide, hvad den midterste er? I noget, når du har begyndelsen og enden, hvordan kan du finde midten? STUDENT: Du gennemsnittet. STUDENT: Du tilføjer dem sammen og derefter - JASON HIRSCHHORN: Tilføj dem sammen og derefter? STUDENT: Og du gennemsnittet. Dividere det med 2.. JASON HIRSCHHORN: Tilføj dem sammen og dividere med 2.. Så int midterste lig? Tom, kan du give mig det? STUDENT: Begyndelsen plus slutter - JASON HIRSCHHORN: Begyndelsen plus slutter. STUDENT: Alle, beslag, divideret med 2.. JASON HIRSCHHORN: Alle, i parentes, divideret med to. Så det giver mig den midterste af noget, korrekt? STUDENT: Du skal også til at runde det op. JASON HIRSCHHORN: Hvad gør du mener, jeg har brug for at runde det op? [indskyde STEMMER] STUDENT: Fordi hvis det er et ulige nummer, så er det ligesom - JASON HIRSCHHORN: Nå, OK. Så jeg kunne runde det op. Men hvis det er et ulige antal, 5, kan jeg idet 1 væk fra midten. Eller hvis det er et lige tal, snarere der er en bedre sag. Hvis det er 4, har vi kun 4, kan jeg tage den første "midten", citat, citat slut eller den anden "midten" en. Enten ville arbejde for en binær søgning, så jeg behøver faktisk ikke at runde det. Men der er en anden ting, jeg nødt til at se på denne linje. Vi er måske ikke klar over det endnu, men vi vil vende tilbage til det. Da denne linje faktisk stadig brug en anden ting. Men indtil videre har vi skrevet fire linjer kode. Vi har fået vores start og slutter markører. Vi har vores while-løkke, der kortlægger på direkte til vores pseudokode. Vi kigger på midten, der kortlægger direkte på vores pseudokode. Jeg vil sige dette går til midten af listen, denne linje kode. Og så, når vi går til midten af listen, den næste ting, vi skal gøre er kontrollere, om vores værdi er der for pseudokoden vi skrev tidligere. Så hvordan kan vi kontrollere, om vores værdi er midten af ​​listen? Dig. Hvorfor kan du ikke gøre det? STUDENT: Hvis vores værdi er er på midten er lig med hvad vi indstiller - Jeg mener lige lig - JASON HIRSCHHORN: It - OK. STUDENT: Jeg er ikke sikker på, hvad variabel vi leder for selv om, er, fordi - [indskyde STEMMER] STUDENT: [uhørligt]. JASON HIRSCHHORN: Præcis. Per funktionen erklæring, vi leder efter en værdi. Så vi søger efter en værdi i en vifte af værdier. Så du er helt rigtigt. Du vil gøre, hvis den er åben parentes værdi beslag midten lukket beslag ligemænd lig værdi, og inde er der hvad skal vi gøre? Hvis vores værdi er der, hvad skal vi gøre? [indskyde STEMMER] STUDENT: Tilbage nul. JASON HIRSCHHORN: Return sandt. STUDENT: Return sandt. JASON HIRSCHHORN: Michael, hvad betyder denne linje gøre? STUDENT: [uhørligt] programmet har kørt dens forløb, og der er over, og du har, hvad du skal gøre? JASON HIRSCHHORN: Programmet eller hvad? I dette tilfælde? STUDENT: Den funktion. JASON HIRSCHHORN: Den funktion. Og så for at vende tilbage til, hvad der kaldes det og give det den værdi, sandt. Præcis højre. Main. Hvad er returtypen af hoved, Michael? STUDENT: int, heltal? JASON HIRSCHHORN: int, nøjagtigt. Et heltal. Det var bare et spørgsmål for at sikre, du fyre har været på toppen af ​​det. Hvad betyder det normalt vender tilbage, hvis alle tingene fungerer godt? STUDENT: Zero. JASON HIRSCHHORN: Zero. Præcis højre. STUDENT: Hvis det bare returnerer true, der er ingen oplysninger bliver givet om hvad - Åh, er det bare at sige, at der værdi der er inde i array. JASON HIRSCHHORN: Præcis. Dette program er ikke at give oplysninger hvor nøjagtig værdi. Det er kun at sige, ja, vi fandt det, eller nej, vi ikke finde det. Så hvis nummer findes, returnere sandt. Tja, faktisk vi bare gjorde det rigtig hurtigt med at en linje kode. Så jeg vil flytte denne linje af pseudokode. STUDENT: Har vi ikke brug for at ændre array? Det bør være værdier, ikke værdi, right? JASON HIRSCHHORN: Undskyld. Tak. STUDENT: Ja. JASON HIRSCHHORN: Denne linje bør være værdier. Præcis højre. OK. Så vi har kigget på den midterste liste. Hvis antallet fundet afkast sandt. Fortsætter med vores pseudokode, hvis midten er større, søg venstre. Så jeg havde i her, hvis nummer højere, søg venstre. Konstantin, kan du give mig denne linje kode? STUDENT: Hvis værdien af ​​midten - JASON HIRSCHHORN: Så hvis værdi - hvis åben parantes værdier beslag midterste close beslag - STUDENT: Er mindre end værdi? JASON HIRSCHHORN: Er mindre end. STUDENT: Mindre end værdi. JASON HIRSCHHORN: Værdi. Tja, faktisk, du ønsker at kontrollere, om nummeret - Undskyld. Det er lidt forvirrende. Men ellers hvis antallet i midten af ​​listen er større. STUDENT: Åh, OK. JASON HIRSCHHORN: Jeg vil ændre det. Else hvis midten er højere, vi vil søge venstre, OK? Og hvad gør vi inde dette, hvis tilstand? STUDENT: Kan jeg lave en lille ændring i den tilstand, ændre det til andet, hvis? JASON HIRSCHHORN: Else nu hvis? OK. Så denne kode vil køre om det samme. Men det gode ved at bruge, hvis ellers hvis ellers hvis eller hvis ellers hvis ellers betyder, at kun en af ​​dem kommer til at skal kontrolleres, ikke alle tre af dem, potentielt. Og det gør det en lille smule pænere på den computer, der er kører dit program. Så [? Konstantin,?] Vi er inde i denne linje, ellers hvis værdier beslag midten luk beslag er større end værdi. Hvad skal vi gøre? Vi har brug for at søge venstre. Hvordan gør vi det? Jeg har tænkt mig at give dig en start. Vi har disse to ting kaldet begynder og slutter. Så hvad der skal ske til begyndelsen? Hvis du ønsker at søge venstre for liste, vi får vores nuværende begyndelsen. Hvad skal vi gøre det? STUDENT: Vi sætter begyndelsen til midten plus 1. JASON HIRSCHHORN: Så hvis vi er søge på venstre? STUDENT: Beklager, midterste minus - så slutningen ville være midten minus 1 og begyndelsen - JASON HIRSCHHORN: Og hvad sker til begyndelsen? STUDENT: Det forbliver den samme. JASON HIRSCHHORN: Så betydning forbliver den samme. Hvis vi søger til venstre, er vi anvendelse af den samme begyndelse - helt rigtigt. Og det slutter? Undskyld, hvad gør slutter lige igen? STUDENT: Middle minus 1. JASON HIRSCHHORN: Middle minus 1. Nu, hvorfor minus 1, ikke bare midten? STUDENT: Den midterste er ude af billedet allerede, fordi vi havde kontrolleret, at det er ude? JASON HIRSCHHORN: Det er helt rigtigt. Midten er ude af billedet. Vi har allerede tjekket midten. Så vi ønsker ikke "i midten", citat citat slut, at fortsætte med at være i array, vi leder. Så det er fantastisk. Else hvis værdier beslag midten er større end værdien slutter ligemænd midterste minus 1. Jeff, hvad med denne sidste linje? STUDENT: Else. Værdier midten er mindre end værdi? JASON HIRSCHHORN: Vi vil du giver mig andet. Så hvis du ikke giver mig - STUDENT: Så begynder ville være midten plus 1. JASON Hirschhorn: Begyndelsen ligemænd midten plus 1 igen for den samme grunden til, at Constantine gav os tidligere. Og til sidst, er der ikke givet mig en linje kode endnu? Return false, Aleha, hvad vi skriver her? STUDENT: Tilbage falsk. JASON HIRSCHHORN: Tilbage falsk. Og vi har brug for at gøre det, for hvis vi finder det ikke, er vi nødt til at sige, at vi kunne ikke finde det. Og vi sagde, at vi kommer til at returnere en bool, så vi helt sikkert nødt til at vende tilbage en bool et eller andet sted. Så lad os køre denne kode. Jeg er faktisk at gå til - så vi er i terminalen. Vi vil rydde vores vindue. Lad os gøre hele. Vi fandt der er en fejl. Der er en fejl på linje 15, der forventes semikolon ved udgangen af erklæring. Så hvad gjorde jeg glemme? STUDENT: semikolon. JASON HIRSCHHORN: Semikolon lige heroppe. Jeg tror, ​​det var Toms kode. Så Tom, [uhørligt]. Just kidding. Lad os gør alt igen. STUDENT: Hvad Dropbox mappe bør vi være i til dette? JASON HIRSCHHORN: Så du kan bare se for denne bit. Men igen, hvis du ønsker at flytte denne kode i din pset3 mappe til prøve det ud, det er, hvad jeg gjorde. Hvis du lægger mærke til her - undskyld, godt spørgsmål. [? LS,?] Jeg har i her find.c kode fra denne uges distro kode. Jeg har helpers.h. Jeg har en Make-fil, som jeg faktisk redigeret en smule til også at omfatte disse nye filer, vi skriver. Alt dette kodeks vil være til rådighed, ikke fordelingen kode, men den nye Gør fil, den nye helpers.h filen være tilgængelige online til download. Igen, så det er de ekstra koder, vi har. Så gør alt, pr denne linie gør finde, binær, boble valg - gør alle tre af dem og samler ind denne eksekverbar kode fund. Så generelt, ønsker vi ikke til lige til check50. Vi ønsker at køre nogle tests på vores egen. Men lige så vi kan fremskynde det en smule, check50 2013 pset3.find vil passere i helpers.c-- mit dårlige. Jeg har ikke lige nu. Så vi faktisk kommer til at køre koden for alvor. Usage.find /, ved du hvad det betyder? STUDENT: Du har brug for en anden kommandolinjen på det. JASON HIRSCHHORN: Jeg har brug for en anden kommandolinje. Og pr specifikationen, jeg har brug for at indtaste, hvad vi leder efter. Så lad os se efter 42. Vi vil holde det i sorterede, fordi vi har ikke skrevet en slags funktion endnu - 42, 43, 44. Og Kontrol D ikke fandt nål i en høstak. Det er dårlige. Det er helt sikkert der. Lad os prøve noget andet. Måske er det fordi jeg sætter det i begyndelsen. Lad os gøre 41, 42, 43. Der vi går. Den fandt det. Lad os sætte det i slutningen nu, bare så vi kan være grundig - 40, 41, 42. Fandt du ikke finde nålen. Så jeg nævnte dette tidligere. Desværre, jeg vidste dette skulle ske. Men for pædagogiske formål, det er godt at udforske det. Det fungerer ikke. Af en eller anden grund, kan den ikke finde den. Vi ved, hvad der er derinde, men vi ikke finde det. Så én ting, vi kan gøre, er at gå igennem GDB at finde det, men gør nogen, uden at gå gennem GDB, har en fornemmelse af, hvor vi skruet op? [? Madu? ?] STUDENT: Jeg tror, ​​det kan være, når slutter er lig med begyndelsen, og det er blot en en-element listen. Så er det bare ignorerer det i stedet for faktisk at kontrollere det. JASON HIRSCHHORN: Det er helt rigtigt. Når slutning lig begyndelsen, gør vi stadig har et element i vores liste? STUDENT: Ja. JASON HIRSCHHORN: Ja, i virkeligheden, vi har én og kun ét element. Og det vil sandsynligvis ske, når, per den kode, vi testede, vi er ved foran høstak eller slutningen af ​​høstak. Det er, hvor begyndelsen og slutning kommer til at lige en, med binær søgning. Så i disse to tilfælde er det ikke virkede, fordi slutter var lig med begyndelsen. Men hvis slutter er lig med starten betyder dette, mens løkken udføre? Det gør det ikke. Og vi kunne have kontrolleret der igen gennem GDB. Så hvordan kan vi løse denne kode, fordi når mens slutter er lig med begynder, vil vi også dette mens løkken til at køre. Så hvad fix kan vi gøre til linje 18? STUDENT: [uhørligt] er større end eller lig med. JASON HIRSCHHORN: Præcis højre. Mens slutningen er større end eller lig med begyndelsen. Så nu, vi sørge for at få det hjørne tilfældet i slutningen. Og lad os se. Lad os køre dette endnu en gang. Lad os gøre alle. Igen, er du nødt til bare følge med her. Find 41 denne gang. Bare holde det konsekvent. Find 42. Lad os sige det i starten - 42, 43, 44. Vi fandt det. Så det var faktisk ændringen vi skulle gøre. Det var en masse kodning vi lige gjorde, binær søgning. Er der nogen har nogen spørgsmål, før Jeg flytter på i linjer, vi skrev i binær søgning eller hvordan vi regnede ud af, hvad vi regne ud? Før vi går videre, vil jeg også gerne påpege ud af, at store og hele, vi kortlagt vores pseudokode en til én på vores kode. Vi havde det tricky ting at finde ud af med det begynder og slutter. Men havde du ikke regnet det ud, du ville have skrevet temmelig identisk kode, bortset disse top to linjer. Og så ville du have indset, når du gjorde det i kontrol og sager, du har brug for noget andet. Så selv hvis du havde fulgt vores pseudo-kode linje for linje, ville du har fået alle men to linjer af kode, du havde brug for at skrive. Og jeg ville være villig til at vædde på, at du fyre ville have alt regnet det ud temmelig hurtigt, at du havde brug for at sætte en slags markør i der at regne ud af, hvor du var. Det igen, er kraften i at gøre pseudo-kode i forvejen. Så vi kan gøre logikken først, og derefter vi kan bekymre sig om syntaks. Havde vi været forvirret over logikken mens du prøver at skrive denne kode i C, vi ville have fået alle rodet op. Og så ville vi være stille spørgsmål om logik og syntaks og meshing dem alle sammen. Og vi ville have fået tabt i, hvad der kan hurtigt blive en meget vanskeligt problem. Så lad os gå videre nu til valg slags. Vi har 20 minutter tilbage. Så jeg har en fornemmelse af, vi vil ikke være i stand til at komme igennem alle valg slags og boble slags. Men lad os i det mindste forsøg for at afslutte valget slags. Så gennemføre valget sortere ved hjælp af følgende funktion erklæring. Også denne taget fra problem sæt specifikationer. Int værdier parenteser, er et array af heltal. Og int.n er størrelsen af ​​denne array. Valg slags går at sortere dette array. Så per vores mentale model for udvælgelse sortere, vi trækker - første, vi går gennem listen den første tid, finde det mindste tal, sætte det i starten, finde den anden mindste tal, sætte det i anden position, hvis vi ønsker at sortere i stigende rækkefølge. Jeg er ikke tvinger dig til at skrive pseudo-kode lige nu. Men før vi gør koden som en klasse i fem minutter, vi kommer til at skrive pseudo-kode, så vi har nogle fornuft af hvor vi skal hen. Så forsøge at skrive pseudo-kode på din egen. Og derefter forsøge at slå denne pseudo-kode i kode. Vi vil gøre det som en gruppe fem minutter. Og selvfølgelig, så lad mig vide, hvis du har spørgsmål. STUDENT: At det? JASON HIRSCHHORN: Se hvor langt du kan komme i yderligere to minutter. Jeg forstår dig ikke vil være i stand til at afslutte. Men vi vil gå over dette som en gruppe. Du er al kodning så [uhørligt], så jeg er ked af at holde pause, hvad du laver. Men lad os gå igennem dette som en gruppe. Og igen, binær søgning, du alle give mig en, hvis ikke flere linjer kode. Tak for det. Vi kommer til at gøre det samme her, kode sammen som en gruppe. Så valg slags - lad os skrive nogle hurtige pseudo-kode. Per mental model, kan nogen give mig den første linje i pseudo-kode, tak? Hvad ønsker jeg at gøre? STUDENT: Mens listen er ude af drift. JASON HIRSCHHORN: OK, mens listen er ude af drift. Og hvad mener du med "ude af drift?" STUDENT: Mens [uhørligt] ikke er sorteret. JASON HIRSCHHORN: Mens listen er ude af drift, hvad gør vi? Giv mig den anden linje, please, Marcus. STUDENT: Så find den næste mindste tal. Dette vil blive indrykket. JASON HIRSCHHORN: Så find det næstmindste antal. Og så en anden? Når vi finder den næstmindste nummer, hvad gør vi? Jeg har tænkt mig at sige finde det mindste antal. Det er, hvad vi ønsker at gøre. Så find det mindste antal. Så hvad gør vi? STUDENT: [uhørligt] til begyndelsen. JASON HIRSCHHORN: Undskyld? STUDENT: Placer den i begyndelsen af ​​listen. JASON HIRSCHHORN: Så placere den i begyndelsen af ​​listen. Og hvad gør vi for at de ting der var i begyndelsen af listen, right? Vi overskrive noget. Så hvor skal vi sætte det? Ja, Anna? STUDENT: Hvor den mindste nummer var? JASON Hirshhorn: Så læg begyndelsen af den liste, hvor mindste tal var. Så mens listen er ude af drift, finder det mindste antal, som anbringes i begyndelsen af ​​listen, satte begyndelsen af ​​den liste, hvor mindste tal var. Marcus, kan du omformulere denne linje mens listen er i orden? STUDENT: Selvom tallene ikke er sorteret? JASON Hirshhorn: OK, så for at ved, at tallene ikke har været sorteret, hvad skal vi gøre? Hvor meget har vi brug for at gå gennem denne liste? STUDENT: Så jeg gætte en for-løkke, eller mens mens cifrene kontrolleret er mindre end længden af ​​listen? JASON Hirshhorn: OK, det er godt. Jeg tror, ​​jeg misphrased mit spørgsmål dårligt. Jeg prøvede bare at komme på vi er nødt til at gå gennem hele listen. Så mens listen er ude af drift, for mig, er svært at kortlægge på. Men dybest set, det er hvordan Jeg mener om dette. Gå gennem hele listen, skal du finde mindste tal, placer den i begyndelse - faktisk, du har ret. Lad os sætte dem begge. Så mens listen er ude af drift, vi nødt til at gå igennem hele listen én gang, finde det mindste tal, sted det i starten af ​​listen, sætte begyndelsen af ​​den liste, hvor mindste tal var og derefter, hvis det Listen er stadig ude af drift, vi har kom til at gå gennem denne processen igen, ikke sandt? Det er derfor, udvælgelse sortere, Big-O runtime udvælgelse slags, anyone? STUDENT: n potens. JASON Hirshhorn: n potens. Fordi ligesom Marcus og jeg har lige indset her, vi nødt til at gå gennem listen liste antal gange. Så går gennem noget af længde n n antal gange er faktisk n potens. Så dette er vores pseudokode. Det ser meget godt ud. Er der nogen har nogen spørgsmål om pseudokode? Fordi faktisk udvælgelse slags bør sandsynligvis kommer den ene til en, kode fra pseudokode. Så spørgsmål om logik pseudokode? Spørg det nu. Valg slags - mens listen er ude af orden, vi kommer til at gå igennem det og finde den mindste hver gang og sætte det i front. Så mens listen er i orden, kan nogen give mig den linje kode, der har ikke givet mig en linje kode endnu, please? Det lyder som en hvad? STUDENT: Det er en for-løkke. JASON Hirshhorn: Det lyder gerne en for-løkke. OK, kan du give mig for-løkken? For - STUDENT: Jeg lig 0. JASON Hirshhorn: I eller - hvad mangler vi? Hvad går lige her? STUDENT: Int. JASON Hirshhorn: Præcis. (Int i = 0; - STUDENT: i