JASON Hirschhorn: Velkommen til uke tre, alle sammen. Vi har en travel, men spennende seksjonen foran oss. Så først, fordi vi har gjort noen framskritt med kurset, men vi har fortsatt har mye læring igjen å gjøre, jeg er kommer til å vise noen ressurser dere som skulle vise seg å være utrolig nyttig som du ikke bare nærmer deg Problemet sett, men også fordøye alle materialet vi gi dere i forelesninger og shorts og seksjon. Så får vi kommer til å tilbringe de første 20 25 minutters avsnitt gå over GDB, som du kan eller ikke kan ha anvendes på dette punkt, men det er en utrolig nyttig verktøy som vil hjelpe deg å feilsøke programmene dine. Mange av dere har kanskje brukt printf i midten av programmet for å finne ut hva en variabel tangert. GDB er enda bedre enn printf og ikke skru opp koden din fordi du kjøre den på en kjørbar fil. Så går vi over 10 mest nyttig kommandoer du trenger for GDB, og vi er kommer til å gå på en øvelse sammen så i oppgavesettet tre og utover, du kan bruke GDB å hjelpe debug programmene dine. Og til slutt, kommer vi til å gå over noen sortering og søking algoritmer at du så på forelesning, og vi er kommer til å faktisk kode, ikke bare pseudo, men kode binære søk, boble sortere og valg liksom. Så først, ønsker jeg å gå over ressursene. Dette er en omfattende liste, og det er mindre skrift fordi jeg hadde mye å passe på her. Men disse vil ikke bare hjelpe deg, igjen, med problemet sett og fordøye informasjonen du har lært, men definitivt, kommer quiz tid, disse vil være utrolig nyttig. Så først, bemerker forelesningen. Hvis du går til cs50.net/lectures og bla til den ønskede uke og dag, vil du se at det er notater for hver forelese, noe som ikke er rett og slett en avskrift, men en redigert versjon av hva som ble dekket i foredrag med kode snutter og andre nyttige ting. Jeg anbefaler å gå over dem. Og da også, det er kildekoden tilgjengelig fra hver forelesning. Og igjen, vil disse lysbildene også være tilgjengelig online på cs50.net/sections denne kvelden. Så andre er de shorts hver uke som dekker temaer, vanligvis 5 til 15 minutter i lengde. Og de som forhåpentligvis vil gi deg en stor primer på forskjellige emner. Tredje - og dette er helt nytt denne år - er study.cs50.net. Hvis du ikke har sjekket det ut, jeg anbefaler at du gjør det. Du får velge et tema. Vi har dusinvis av emner på det. Så for eksempel, plukker du funksjoner. Det gir deg noen lysbilder og notater på funksjoner. De er faktisk de lysbildene som TFs oppfordres til å bruke under presentasjoner i seksjonen. Det er også tips og triks for å håndtere med funksjoner, og det er praksis problemer som hjelper du arbeider med funksjoner. Vi gir deg også lenker til kort på funksjoner og de gangene som fungerer har kommet opp i foredrag. Så study.cs50.net, splitter nytt dette år, en fantastisk ressurs. Deretter har jeg menneske, som er den manuelle kommando som du kan kjøre på kommandolinjen. Så hvis du har noen spørsmål om en kommando, for eksempel, rand, som vi møtte forrige uke under avsnittet og du har sannsynligvis oppstått i problemet satt når du går gjennom generere kode, men hvis du skriver mann rand, får du den siden som forteller deg alt om rand. Det gir deg det som trengs, det parametere det tar, samt retur type og en kort beskrivelse av denne funksjon. Så sjekk ut rand. Det kan være litt ordrike og forvirrende, så noen ganger finner jeg at bare Googling hva jeg ønsker å vite er den beste måten å finne svaret. Så øve med Google. Få gode på Google. Det vil bli din beste venn. I tillegg til Google, hvis du ikke kan finne det på Google, cs50.net/discuss, er det diskusjonsforum. Sjansene er hvis du har et spørsmål, en av dine 700 + jevnaldrende har også som spørsmål og kan ha spurt det allerede i diskuterer fora og har svart på det. Så hvis du har et vanlig spørsmål eller du har et spørsmål som du tror kanskje andre mennesker kan ha kjørt inn, sjekk ut cs50.net/discuss. Til slutt, de to siste, hvis du ønsker å snakke med et ekte menneske, kontor timer mandag til fredag. Det er også online kontortid for forlengelse studenter. Og sist, men absolutt ikke minst, meg, utropstegn. Dere har min kontaktinformasjon. Hvis du trenger noe, må du aldri nøl med å kontakte meg. Alltid gjerne gjøre det. Svært få av dere har lagt meg på Gchat, slik som har vært skuffende, men forhåpentligvis som vil veksle mellom dette og neste avsnitt. Eventuelle spørsmål så langt på ressursene? Flott. Til slutt, en annen plugg for tilbakemeldinger, sayat.me/cs50. Du kan gi meg anonym tilbakemelding på hvordan jeg gjør. Det var virkelig nyttig i forrige uke. Jeg fikk et par kommentarer fra dere rett etter delen, pluss fra andre studenter som så den i løpet av uken, og det var utrolig nyttig. Jeg kommer til å prøve og begrense min bruk av ordet "søt", men jeg vil vise min entusiasme og spenning på annen måte. Men det var andre tilleggs substansielle tilbakemeldinger, både positive og Delta. Så vær så snill, jeg gir dere tilbakemelding på oppgavesett. Føl deg fri til å gi meg tilbakemelding på min undervisning. Jeg er her for dere. Flott. Det er alt jeg har for den første delen. Er det noen som har noen spørsmål så langt? Og jeg har et notat for kontrollsenteret. Skjøte studenter har messaged meg sier at de ikke får noen lyd, men det er ute av min makt for å fikse. Så forhåpentligvis blir det løst innen kort tid. Hvis du ser på nettet, hi, men du kan ikke høre meg. Så først skal vi å gå gjennom GDB. GDB, som jeg antydet tidligere, er et feilsøkingsverktøy mye bedre enn printf. Så for å komme i gang med GDB, dere, hvis du ønsker å åpne opp apparatet og ta den filen som jeg mailet til deg tidligere - denne filen vil også være tilgjengelig på nettet i en bit - og kjøre GDB. / navnet på filen. Først, naturligvis, må du kompilere filen fordi GDB fungerer bare på kjørbare filer. Men hvis du noen gang ønsker å starte GDB, er det første du gjør, du kjører GDB. / Caesar. Så det er navnet på programmet vi er kommer til å gå med det akkurat nå. Så jeg kommer til å skrive gjøre Caesar, som vil gi meg en kjørbar fil her uthevet i grønt. Og så kommer jeg til å kjøre GDB. / Cesar. Og der du går. Du skjønner vi har litt tekst som forteller meg om hvilken versjon av GDB, gi meg noen garantiinformasjon, og da vi har BNP teksten, som ser liksom av som vår kommandolinjen, men du ser det er åpent paren, GDB, nære paren. Før vi fortsetter og feilsøke denne filen som jeg sendte til dere alle, la oss se på noen nyttige kommandoer, slik at vi har en følelse av hva vi kommer til å dekke. Disse kommandoene er listet her i rekkefølgen som jeg vanligvis bruker dem. Så jeg starter programmet ved å kjøre GBD. / Navnet på programmet, i dette tilfellet, Caesar. Og så er det første jeg gjør 99,9% av tiden er typen pause mener. Som setter en pause punkt på hoved. Hovedsak, hva du gjør det er programmet kommer til å stoppe på Hoved slik at du kan begynne å undersøke det linjen etter linjen, i stedet for å kjøre all veien gjennom. Du kan bryte på forskjellige punkter i koden din, men hoved er generelt en godt sted å begynne. Den neste kommando jeg kjører er løp. Det starter programmet kjører, og Hvis du trenger å skrive inn kommandolinjen argumenter, kjører du det som kommando. Kjør med argumentene. Så siden vi kommer over en versjon av C, som er det programmet dere skrev for PSett to - denne, selvfølgelig, har noen insekter i det som forhåpentligvis vil vi finne - vi kommer til å kjøre løp med en kommando argumenter fordi Caesar, som dere vet per problemet satt spec, tar litt kommandolinjeargumentene. Det neste par av kommandoer, den neste man blir faktisk kalt neste. At man tar du linje for linje gjennom programmet. Så treffer n deretter Enter tar deg til den neste linje, utføring forrige linje. Trinn tar ikke bare deg til neste linje, men tar du inne funksjoner. Så hvis du har skrevet en funksjon i koden din, eller hvis du ønsker å utforske et til i, for eksempel, kan du treffer s, og stedet for å gå til den neste linje i filen som du går gjennom akkurat nå, vil du faktisk gå inn denne funksjonen og se sin kode. Listen viser, i svært brukervennlig format, de 10 eller så linjer rundt hvor du befinner deg i koden så du kan faktisk se filen snarere enn å måtte bytte tilbake og tilbake mellom ulike visninger. Utskriften er som printf, som navnet tilsier. Som viser deg hva en variabel er lik. Info lokalbefolkningen er veldig nyttig. Dette er en spesiell versjon av print. Info lokalbefolkningen viser deg alle de lokale variabler, skriver dem ut for deg som er tilgjengelig for øyeblikket. Så jeg generelt, heller enn å måtte skrive ut de fire variabler som jeg er nysgjerrig på om jeg er i en for loop, for eksempel, jeg bare skrive info lokalbefolkningen, og det skal vise meg hva mitt teller jeg er lik, så vel som den matrise som er jeg arbeider med likemenn. Til slutt, fortsetter. Skrive pause stopper deg Stillingen ved pause punktet. Du kan gå gjennom linjen ved tråd med neste og trinn. Fortsett kjører programmet til din neste bryte punkt eller til den er ferdig hvis er det ingen flere brytepunkter. Deaktiver fjerner pause poeng hvis du besluttet pause på hoved var upassende, vil du sette den et annet sted. Og til slutt q, avslutte, kommer ut av GDB. Så dette programmet,. / Caesar, vi skal å se gjennom akkurat nå, og vi skal bruke GDB å finne bugs i dette programmet. Jeg kjørte dette programmet tidligere med Sjekk 50, og jeg fikk en rynke. Alt det eksisterte, det kompilert, det passerte en rekke av testene, men for noen grunn, gjorde det ikke passere den femte test, snu BARFOO, alle caps, inn E-D-E-I-R-R-, bokstaver, ved hjelp av tre som en nøkkel. Jeg fikk ganske nær. Jeg gikk av med én bokstav. Så det er noen små feil her. Jeg har sett gjennom min kode. Jeg kunne ikke finne ut av det. Forhåpentligvis kan dere hjelpe meg finne ut hva denne feilen er. Så det er feilen vi er søker etter. La oss flytte inn GDB. Igjen, jeg har kjørt GDB. / Caesar, så nå er vi i GDB. Og hva er det første ting jeg bør gjøre? Jeg har akkurat kommet inn GDB. Noen gi meg en god kommando for å gå inn. STUDENT: Bryt hoved. JASON Hirschhorn: Bryt hoved. Fantastisk. La oss skrive at i. Dere kan se deg her eller følg sammen på datamaskinene. Bryt hoved, og du vil se en break point ble satt til - det gir meg noen rare minneadresse, og det gir meg også linjenummer. Hvis jeg var å se tilbake på denne filen, Jeg ville innse at hoved skjedde på linje 21. Hva bør jeg kjøre neste? Er min program som kjører? Nei. Så hva bør jeg kjøre neste? STUDENT: Kjør. JASON Hirschhorn: Kjør. Skal jeg bare kjøre løp, eller skal Jeg legger til noen andre ting i? STUDENT: Kjør med argumentet. JASON Hirschhorn: Kjør med kommandoen argumenter. Og siden jeg feilsøker i en veldig spesifikk tilfelle, skal jeg gå inn for at Argumentet for kommandolinjen. Så jeg skal ikke kjøre tre, som er, igjen, output jeg fikk fra Check 50. Starte programmet. Vi går gjennom et par linjer. Du vil nå se at vi er på linje 21. Hvordan vet jeg at vi er på linje 21? Fordi hvis du ser til venstre av min terminalvindu, der det sier Line 21. Og det gir meg, faktisk, den kode som er i linje 21.. Så jeg misspoke tidligere. Hoved er faktisk ikke på linje 21. Main er et par linjer over 21. Men på linje 21, er at hvor vi bryte. Dette kodelinje har ennå ikke utført. Det er viktig. Linjen du ser har ikke blitt utført ennå. Det er den neste linje med kode du er i ferd med å gjennomføre. Så neste linje, som dere er sannsynligvis kjent med, er dette tilstand sjekke for å se om jeg har gikk inn i en kommandolinje argument. Og en til jeg, hva er den andre en del av det å gjøre? Hva er en til jeg? STUDENT: Endre det til et heltall. JASON Hirschhorn: Sorry? STUDENT: Det er å endre argumentet til et helt tall. JASON Hirschhorn: Så en til jeg endrer arg v1 fra en streng til et heltall. Og hva er det å sjekke? STUDENT: Hvis det er en andre kommandolinje argument, bortsett fra å kjøre programmet. JASON Hirschhorn: Og hva er den andre halvparten av dette Boolsk uttrykk sjekke? Denne delen over her, en til jeg? STUDENT: Hvis det er negativt. JASON Hirschhorn: Å sørge for hva? STUDENT: Sørge for at det er, faktisk, positive. JASON Hirschhorn: Nettopp. Dette er å sjekke for å se om det er negativ, og hvis den er negativ, I har en følelse av neste linje makt være meg roping på brukeren. Så la oss treffer enden for å utføre denne linjen. Vi kan ikke se at linjen som dere kanskje ventet å se roping på brukeren, og deretter retur, fordi denne linjen ikke kjøre. Jeg kom inn tre. Så jeg gjorde, faktisk, skriv to kommando argumenter, og tre er er større enn null. Så vi så den linjen, henrettet vi, men vi fikk ikke gå inne hvis betingelsen. Så nå, neste, jeg ser Jeg setter int nøkkel tilsvarer en til jeg arg v1. Så det er meg du oppretter en variabel nøkkel. Så hvis jeg skriver ut nøkkelen akkurat nå, fordi som lar deg se verdi inne i variabelen, Nøkkelen er lik 47. Det er rart, men selvfølgelig, det er fordi jeg har ikke henrettet den linjen ennå. Så nå hvis jeg treffer n, kjøre den linjen, og gjøre print nøkkel, vil nøkkelen lik 3, som er hva vi forventer at det skal være lik. Så igjen, i GDB, linjen du ser du ikke har utført ennå. Du må treffe n eller s eller et nummer av andre kommandoer til faktisk kjøre den linjen. Skriv ut nøkkelen. Keys på tre. Så langt, så bra. String er ren tekst. La oss kjøre den linjen. Jeg får en streng fra brukeren. La oss se i min Sjekk 50, jeg skriv BARFOO alle caps, så det er det jeg skal gå inn. Hvis jeg nå skrive ren tekst. Du vil se det tilsvarer en streng. Det gir meg noen rare heksadesimale tall, men det gjør i Faktisk si at min strengen er BARFOO. Hvis jeg ønsket å se hvilken tast tangert på dette punktet, hvordan kunne jeg sjekke nøkkelen? STUDENT: Skriv ut nøkkelen. JASON Hirschhorn: Skriv ut nøkkelen, akkurat. Og faktisk, det er en snarvei. Hvis du blir lei av å skrive print, du kan bare skrive s.. Så p-tasten gjør de samme ting. Og igjen, jeg ser det er lik tre. Hvis jeg ønsket å finne ut hva både nøkkel og BARFOO tangert samtidig men jeg var lei av å skrive hver en ut individuelt, jeg kunne skrive info lokalbefolkningen. Det gir meg viktige likhets tre. Ren tekst er lik BARFOO. Det gir meg også disse to rare ting på toppen, variabelen og denne variabelen n. De er faktisk eksisterende i min hovedprogrammet. Vi har ikke møtt dem ennå, men som en forhåndsvisning, de eksistere i min for loop. Så akkurat nå, de like noen rare tall, fordi de ikke har vært initialisert ennå, men de har fortsatt eksisterer i minnet, slik at de bare satt til noen søppel verdi. Men vi ser nøkkelen i ren tekst rett der. Så jeg kommer til å kjøre denne linjen, linje 34, for loop. Vi kommer til å hoppe i for loop ved å treffe n. Og vi er inne i for loop. Vi er på vår første sjekk. Og igjen, disse skal liksom se kjent for deg, fordi dette var en Cæsar-programmet som ble skrevet, men igjen, har en slags insekt. Og nå hvis jeg gjør info lokalbefolkningen, fordi jeg er innsiden som for loop, vil du se at jeg er lik null, som vi forventer. Det er det vi setter den til og initialisert det å i for loop. n er lik seks. Det gjør også fornuftig fordi vi satt det til strlen av ren tekst. Så jeg liker å gjøre info lokalbefolkningen eller print til variable ofte å sørge for at alt er alltid hva Jeg forventer at det skal være lik. I dette tilfellet er alt hva jeg forventer at det skal være lik. Så la oss begynne å bevege seg gjennom dette for loop. Linjen jeg er på det linje 36, hvis det er vanlig Teksten i er større enn en og vanlig Teksten i er mindre enn eller lik z. Jeg vet mitt problem er ikke med min første brev, er det med den andre bokstaven. Hvis vi ser tilbake på Check 50, B går til E fint. Jeg tar en og forlate det som en A, ikke endre det til D. Så noe er galt med den andre bokstaven. Så jeg kommer til å flytte det i et sekund. Men hvis jeg hadde lyst til å sjekke hva vanlig Teksten jeg tangert i denne spesielle Da tror jeg det skal være hva? Hva bør ren tekst jeg like i dette første runde gjennom for loop? STUDENT: Zero? JASON Hirschhorn: Ren tekst av jeg? Slik det skal være stor B. I naturligvis lik null, men ren tekst brakett null lukket vinkelen er B fordi strenger, som vi så i forrige uke, er array, så vi får den første tegnet fra det. Så igjen, hvis jeg printet ut ren tekst av I, I do i virkeligheten få tegnet B. Og det er ryddig, ikke sant? Jeg har ikke egentlig ren tekst I. Det er ikke en av de variablene jeg satt eller initialisert, men du kan skrive ut ut en hel rekke ting hvis du ønsker det. Men la oss gå gjennom. Hvis ren tekst jeg er større enn A og ren tekst I er mindre enn eller lik Z, som tydelig er sant fordi vi har en kapital B. Jeg kommer til å kjøre noen kommando på den. Vi så at matematikk i forrige uke, så vi får ta det for gitt at det fungerer retten ifølge Sjekk 50. Disse klammeparentes, den første viste at jeg var spennende hvis stand, viste det andre en at jeg avslutter for loop. Og så nå da jeg traff Neste, vi får se vi er tilbake på for-løkken igjen. Vi går gjennom for loop igjen. La oss faktisk gå inn i andre iterasjon av for løkke og type info lokalbefolkningen. Så vi er i den andre iterasjon av vår for loop. Jeg er lik 1, som vi forventer. N er lik 6, som vi forventer. Key er lik 3, som vi forventer. Og ren tekst, vil du se, lik EARFOO nå, ikke BARFOO lenger fordi i vår forrige iterasjon, B var endret til en kapital E. Så vi er i ferd med å møte problemet, så dette er der vi kommer til å dykke inn i debugging. Men er det noen som har noen spørsmål om hva vi har gjort så langt? Fantastisk. Så vi er i ferd med å gjennomføre dette hvis tilstand, ren tekst brakett jeg lukket brakett større enn A og ren tekst jeg mindre enn eller lik Z. Men før Jeg går inn på det, fordi det er der Jeg vet at min feil er at jeg ønsker å påpeke ut ren tekst av I. Så la oss sette print ut. Det gjør det tilsvare tegnet A, slik at virker så langt, er alt vel og bra. Så jeg forventer at denne linjen per min logikk, Denne linjen skal være sant. Det er en stor bokstav. Men hvis jeg treffer n, innser vi at dette linje, faktisk, ikke utføre. Jeg hoppet ned til annet hvis. Hvorfor skjedde det? STUDENT: Fordi du har din tilstand av ren tekst er større enn A, ikke er lik eller større enn. JASON Hirschhorn: Så jeg hadde min ren tekst I er større enn A, som ikke er større enn eller lik. Så klart, gjorde ikke hovedstaden A utløse dette hvis tilstanden, og vi gjorde ikke gå inn i det, og vi gjorde ikke gjør de nødvendige skift. Så det er det, faktisk. Jeg fant ut min feil. Jeg kunne gå tilbake i min kildefilen, endre det, og oppdatere det og kjøre Sjekk 50 igjen. Men vi får se, bare for pedagogikk er skyld, hvis jeg holde det gående. Annet hvis ikke kjøre heller, men hva stedet lik er kommandoen som ikke endres. Så det er ikke endret i det hele tatt, og hvis jeg skrive ren tekst her, vi får se kommer gjennom at for loopen ikke gjorde det, faktisk, endre det andre tegn i det hele tatt. Det er fortsatt en kapital A. Så igjen, vi feilsøkt vår feil. Vi innså at det var noen logikk mangler. Og vi feilsøkt det på forhånd før faktisk utfører den linjen, men du ville ha lagt merke hadde vi bare rammet Neste og gå til det annet hvis, det betyr at at hvis tilstanden var ikke sant. Vi gjorde ikke, faktisk, får resultatet vi forventet. Så da kunne vi ha blitt bedt om det, hadde vi ikke vært så slu, for å se på at hvis tilstand og sjekke om, faktisk, vår tilstand bør vurdere å sant i den aktuelle konteksten. Det er alt for debugging dette programmet. Er det noen som har noen spørsmål? Hvilken kommando kan jeg treffer å slutte GDB? Q. Og så skal jeg bli bedt om, slutte likevel? Ja eller nei. Jeg vil treffe ja, og jeg skal ha sluttet GDB. Så det var en rask primer til GDB. Egentlig, i en reell situasjon, Jeg gjorde dette i kontortiden. Jeg GDBed denne eksakte programmet på kontortid med en student. Og hvis vi går tilbake til kommandoene vi så før, brukte vi pause hoved, først ting vi gjorde. Vi brukte kjøre med kommandolinjeargumenter, andre ting vi gjorde. Vi brukte neste mye å flytte oss gjennom linjene. Og igjen, den korte versjonen neste er n. Det er i parentes i grått på lysbildet. Vi brukte ikke trinn, men vi gjorde ikke nødvendigvis må for dette tilfellet. Men vi kan bruke den i en litt senere på i dag hvis vi feilsøker, for eksempel binære søk når binær søk kalles i et eget funksjon, men det er noen feil med den. Vi kommer til å ønske å gå inn kallet til binære søk og faktisk feilsøke det. Lister vi fikk ikke bruke enten fordi vi hadde en god følelse av vår kode, men hvis jeg hadde lyst til å få en følelse av hva kode jeg var rundt, kunne jeg bare bruke listen. Skriv ut vi brukte, info lokalbefolkningen vi brukte. Fortsett vi ikke trenger å bruke i dette tilfelle, heller ikke vi trenger å bruke deaktivere, men vi gjorde bruk slutte. Igjen, disse 10 kommandoer, praktisere dem. Hvis du forstår disse 10 kommandoer, du bør settes for debugging noen utstede med GDB. Så vi er i ferd med å gå på, igjen, til crux av seksjonen i dag, gå over disse sortering og søking algoritmer. Før vi gjør det, igjen, noen spørsmål, kommentarer, bekymringer for GDB? Så er alle kommer til å bruke GDB snarere enn printf? Så alle, for all fremtid skyld, alle nikker hodet rett nå, så jeg vil se deg på kontortid og alle TFs vil se deg og de vil si, vis meg hvordan du bruker GDB, og du vil kunne å vise dem, ikke sant? Slags? Kanskje forhåpentligvis. Cool. Så vi kommer til å flytte inn sortering og søking. Du vil se jeg har en liste som allerede er sortert for oss, men som ikke kommer å være tilfelle alltid. Så i oppgavesettet spesifikasjon for Problemet satt tre, har du shorts som du kan se, og det faktisk ber deg om å se disse shorts. Også i foredrag i forrige uke, gikk vi over mange av disse algoritmene, så jeg er ikke kommer til å tilbringe tid i klassen går over disse algoritmene igjen eller tegning bilder for hvordan disse algoritmer fungerer. Igjen, at informasjon du kan re-watch forelesning, eller at informasjon fanges used på shorts for disse søk, alle som er tilgjengelig på cs50.net. Så i stedet, hva vi skal gjøre er å skrive disse programmene. Vi har en følelse, en mental modell, av hvordan de fungerer, og så hva vi skal å gjøre er å kode dem på ordentlig. Vi kommer til å slå den mentale modellen, det bildet, hvis du vil, inn i selve koden. Og hvis du var litt forvirret eller disig på mental modell, jeg helt forstå. Vi er faktisk ikke kommer til å hoppe til kode straks. Så mens denne meldingen i denne lysbilde spør du å kode binære søk, og faktisk, en iterativ versjon av binære søk, det første jeg virkelig ønsker at du skal gjøre er skrive noen pseudo. Så du har denne mentale modellen av hvordan binære søke fungerer. Ta ut et ark hvis du har en lett tilgjengelig, eller åpne en tekstredigeringsprogram, og jeg vil gjerne alle til å skrive. Ta fire minutter på å skrive pseudo for binære søk. Igjen, tenk på at mental modell. Jeg kommer rundt hvis du har spørsmål og vi kan trekke bildet ut. Men først, før vi starter programmeringen, Jeg vil gjerne skrive pseudo for binære søk så når vi dykke i, har vi noen retning som til hvor vi bør dra. STUDENT: Kan vi anta rekken av verdiene vi får er allerede sortert? JASON Hirschhorn: Så for binære søk å jobbe - utmerket spørsmål - du nødt til å ta i en sortert matrise av verdier. Så antar det vil fungere. Vi vil gå tilbake til dette lysbildet. Du vil se i lilla funksjonen Erklæringen er bool binary_search int verdi, int verdier, int n. Dette bør være kjent hvis du har allerede kontaktet eller fått din hendene skitne med problemet sett. Men det er din funksjon erklæring. Igjen, ikke skulle trenge å bekymre seg for at mye i dette øyeblikk. Det jeg egentlig vil at du skal gjøre er å ta fire minutter til pseudo binære søke, og deretter vil vi gå over det som en gruppe. Og jeg vil komme rundt. Hvis du har spørsmål, føler fritt til å heve hånden. Hvorfor ikke ta to minutter til slutt opp pseudo? Jeg vet dette kan virke latterlig at vi tilbringer så mye tid på noe som ikke engang faktisk i C, men spesielt for disse mer utfordrende algoritmer og problem sett som vi må finne ut, starter i pseudo ikke bekymre om syntaksen, bare å bekymre seg logikken, er utrolig nyttig. Og på den måten, du er ikke løse to utrolig vanskelige problemer på en gang. Du bare fokuserer på logikk, og så du flytte inn i syntaks. OK. La oss begynne å gå gjennom den pseudo. Jeg har skrevet opp her, binære søk pseudo. Vi skal skrive dette på borde sammen. Eller jeg skal skrive det, og du vil gi meg instruksjonene jeg trenger. Så kan noen gi meg den første linjen i pseudo du skrev for binære søk? Ja, Annie? STUDENT: Mens lengden på listen er større enn null. JASON Hirschhorn: Mens lengde av listen er større enn null. Og igjen ser vi noen C-jakt syntaktiske ting på her. Men det meste av dette er på engelsk. Hadde noen har noen linje de legger før dette i sin pseudo-kode? STUDENT: Få en matrise av sortert tall. JASON Hirschhorn: Du skrev "får en utvalg av sorterte tall. "Per funksjon erklæringen, vil vi være bestått en rekke sortert tall. STUDENT: [uhørbart]. JASON Hirschhorn: Så vi vil ha det. Men ja, hvis vi ikke har det, vi ville trenge for å sortere vår rekke tall, fordi binære søk fungerer bare på sortert arrays. Så mens lengden på listen er lik null, er jeg kommer til å sette i noen klammeparentes slik at den ser litt mer ut som C. Men samtidig, ser ut til å kartlegge på en mens loop, så inne i denne stund løkke hva trenger vi å gjøre for binære søk? Noen andre som ikke har gitt meg en svar ennå, men som skrev dette? STUDENT: Gå til midten av listen. JASON Hirschhorn: Tom. Gå til midten av listen. Og oppfølgingsspørsmål, hva gjør vi når vi er på midten av listen? STUDENT: Gjør en sjekk om det er nummeret du leter etter. JASON Hirschhorn: Excellent. Gå midten av listen og sjekke hvis vår verdi er der - fantastisk. Har noen har noe annet som var annerledes enn dette? Det er helt riktig. Det første vi gjør i binært søk er å gå til midten av listen og sjekk for å se om vår verdi er der. Så jeg antar at hvis vår verdi er det, hva gjør vi? STUDENT: Vi returnerer null [uhørbart]. JASON Hirschhorn: Ja, dersom vår Verdien er der, fant vi det. Så vi kan fortelle noen måte, men dette funksjonen er definert, forteller vi brukeren vi fant det. Hvis den ikke er der, skjønt, er at der dette blir vanskelig. Så hvis det ikke er det, noen andre som jobbet på binære søk eller har en idé nå, hva gjør vi? STUDENT: Spørsmål. JASON Hirschhorn: Ja? STUDENT: Er matrisen allerede sortert? JASON Hirschhorn: Ja, vi antar rekken allerede er sortert. STUDENT: Så da må du sjekke om verdien som du ser er større enn verdien som du ønsker, kan du flytte til midten av den andre halvdelen. JASON Hirschhorn: Så hvis midten av listen er større enn hva vi er på jakt etter, så vi vet hva? Vi flytter hvor? STUDENT: Du ønsker å flytte til halvparten av listen med tall lavere enn det. JASON Hirschhorn: Så får vi kaller det venstre. Så hvis midten er større, kan vi søke den venstre halvdelen av listen. Og så etter søk, hva mener jeg med søk? STUDENT: [uhørbart]. JASON Hirschhorn: Vi går til midten. Vi har faktisk gjenta denne tingen. Vi går tilbake gjennom vår mens loop. Jeg skal gi deg det siste - annet, hvis, i midten mindre enn hva vi, hva gjør vi her? STUDENT: Gå til høyre. JASON Hirschhorn: Søk i retten. Dette ser bra ut, men er det noen som har noe som vi kan være mangler eller noe annet som du putter i pseudo-kode? Så dette er hva vi har så langt. Mens lengden av listen er større enn null, skal vi gå til midten av listen og sjekke om vår verdi er der. Hvis midten er større, skal vi søke igjen, annet hvis midten er mindre, skal vi søke den rette. Så vi har alle hatt noen kjennskap til begrepene vi bruker i informatikk og de verktøyene vi har. Men vil du allerede merke vi var snakke på engelsk, men vi fant en mange ting som syntes å kartlegge om å verktøyene vi har i vår koding verktøysett. Så rett utenfor balltre, er vi ikke kommer til å faktisk kode ennå. Hva ser vi her på engelsk at kart på til ting vi kan skrive i C? STUDENT: Mens. JASON Hirschhorn: Mens. Så dette mens her kart på til hva? STUDENT: En stund loop. JASON Hirschhorn: En while-loop? Eller kanskje, mer generelt, en sløyfe. Vi ønsker å gjøre noe om og om igjen. Så vi kommer til å kode en loop. Og vi allerede vet, fordi vi har gjort dette et par ganger og vi har nok av eksempler der ute, hvordan faktisk å skrive denne indeksen for en loop. Så det burde være ganske enkelt. Vi bør være i stand til å få det startet ganske raskt. Hva annet skal vi se på her? Hvilke andre strukturer syntaxes, ting at vi er kjent med i C, gjør vi allerede har en følelse av naturbasert ut av de ordene vi brukte? Ja, Anna? [Uhørbart] bare tuller. Anna, gå videre. STUDENT: Hvis og annet. JASON Hirschhorn: Hvis og annet - akkurat her. Så hva gjør de ser ut? STUDENT: An hvis annet utsagn. JASON Hirschhorn: Yeah, forhold, ikke sant? Så vi må sikkert skrive noen tilstander. Og igjen, men kanskje forvirrende i første, vi har generelt en følelse nå om hvordan å skrive forhold og syntaksen for forholdene. Og hvis vi ikke gjør det, vi bare slå opp syntaks for forholdene, klipp og lim det, fordi vi vet vi trenger en tilstand her. Eventuelle andre ting vi ser at kartet på ting vi kanskje trenger å gjøre i C? Ja, Aleha? STUDENT: Dette kan være opplagt, ved å bare sjekke om en Verdien er lik noe. JASON Hirschhorn: Så hvordan skal vi sjekke og - for så å gå til midten av listen og sjekk om vår verdi er det? Hvordan skal vi gjøre det i C? Hva er syntaksen for det? STUDENT: lik, lik. JASON Hirschhorn: lik, lik. Så denne sjekken er trolig kommer å være et lik, lik. Så vi vet vi trenger at et sted. Og faktisk, bare i å skrive det, vi ser de andre tingene. Vi er nødt til å gjøre noen sammenligningsoperatorer i det - fantastisk. Så det faktisk ser ut, ved og store, har vi ikke skrevet en ord av C-kode ennå. Men vi fikk den mentale modellen ned via forelesninger og disse shorts. Vi skrev pseudo-kode som en gruppe. Og allerede har vi 80% hvis ikke 90% av hva vi trenger å gjøre. Nå trenger vi bare å kode den, som igjen, er en ikke-triviell problem å løse. Men minst er vi fast på logikk. Minst nå når vi går til kontortiden, Jeg kan si, jeg vet hva jeg trenger å gjøre, men kan du minne meg av syntaksen? Eller selv om kontortiden er overfylt, du kan google for syntaksen, heller enn å bli sittende fast på logikken. Og igjen, heller enn å prøve å løse logikken og syntaks problemer alle på en gang, er det ofte er bedre å bryte disse to vanskelige problemer ut i to mer håndterbare seg og gjøre det pseudo-kode først og deretter koden i C. Så la oss se hva jeg gjorde for pseudo-kode på forhånd. Mens lengden av listen er større enn null, ser på midten av listen. Hvis nummeret funnet returnert sant, ellers hvis antallet høyere, søk venstre. Else if nummer lavere, søk høyre, return false. Så det ser nesten identisk hvis ikke nesten identisk med hva vi skrev. Egentlig, Tom, hva du sa først, bryte midten av listen og hvis nummeret funnet i to uttalelser er faktisk det jeg gjorde. Jeg kombinerte dem der. Jeg skulle ha lyttet til du første gang. Så det er pseudo-kode har vi. Hvis du ønsker å nå, beklager, går tilbake til vår opprinnelige problemet. La oss kode binary.c. Så gjennomføre en iterativ versjon av binære søk ved hjelp av følgende funksjon erklæring. Og du trenger ikke å kopiere det ned ennå. Jeg er faktisk kommer til å åpne opp rett her binary.c. Så det er funksjonen erklæringen i midten av skjermen. Og du vil se jeg tok den pseudo-kode fra on mine sider, men nesten identiske til det vi skrev, og sette det inn for deg. Så nå, la oss ta fem minutter å kode denne funksjonen. Og igjen, hvis du har noen spørsmål, rekk opp hånden, gi meg beskjed, vil jeg komme rundt. STUDENT: [uhørbart]. JASON Hirschhorn: Så jeg tok den binære søk definisjon på toppen, på linje 12. Det er hva jeg fikk for min lysbilde. Og så all denne pseudo-kode jeg bare kopiere og limes fra raset, pseudo-kode lysbilde. Jeg er fortsatt ikke hørt [uhørbart]. Så hvis du er ferdig med din implementering, jeg ønsker å sjekke det. Jeg mailet deg helpers.h fil tidligere i denne klassen. Og det vil være tilgjengelig på nettet også for nedlasting for folk å se denne delen tid forsinket. Og jeg bare brukt den generiske distribusjon kode fra pset3. Så jeg tok find.C, bruke min helpers.h fil snarere enn helpers.h fil som er gitt i fordelingskode. Og jeg måtte gjøre en annen endring i find.C snarere enn å ringe bare rett og slett søk, ring binary_search. Så hvis du ønsker å teste koden din, vet at det er hvordan du gjør det. Faktisk, når vi skal kjøre denne koden akkurat nå, jeg bare laget en kopi av min pset3 katalog, igjen, byttet ut hjelperne filer og deretter gjort at endre seg i find.C å ringe binary_search snarere enn bare å søke. JASON Hirschhorn: Ja. Du har et spørsmål? STUDENT: Nevermind. JASON Hirschhorn: Ingen grunn til bekymring. Vel, la oss komme i gang. Vi vil kode dette som en gruppe. En annen kommentar. Igjen, dette er, kan lett byttes i for Problem Set Tre. Jeg har min helpers.h fil som, snarere enn helpers.h vi er gitt, erklærer binære søk, boble sortere og valg liksom. Og i find.c vil du merke på linjen, hva er det, linje 68, kaller vi binær søke snarere enn søk. Så igjen, den koden som er tilgjengelig online eller koden som du er skape akkurat nå enkelt kan byttes i for p satt tre for å sjekke det. Men først, la oss kode binære søk. Vår funksjon erklæring, vi tilbake en bool. Vi tar et heltall kalles verdi. Vi tar en matrise av heltall kalles verdier, og vi tar n være størrelsen av matrisen. På linje 10, akkurat her, har jeg skarp inkluderer stdbool.h. Er det noen som vet hvorfor det er det? Så hva betyr det kodelinje gjøre? STUDENT: Den lar deg bruke en bool returtype. JASON Hirschhorn: Nettopp. STUDENT: Eller det er et bibliotek som lar å bruke en bool returtype. JASON Hirschhorn: Så skarp inkluderer stdbool.h linjen gir meg noen definisjoner og erklæringer for ting at jeg får lov til å bruke i dette biblioteket. Så blant dem er å si at det er denne type kalles bool, og det kan være sant eller usant. Så det er det den linjen gjør. Og hvis jeg ikke har den linjen, ville jeg komme i trøbbel for å skrive dette ord akkurat her, bool, rett der. Helt riktig. Så jeg trenger det i denne koden. OK. Så dette, igjen, er en iterativ utgave, ikke en rekursiv en. Så la oss komme i gang. La oss starte med dette første linje av pseudo-kode. Og forhåpentligvis vil vi - eller ikke forhåpentligvis. Vi kommer til å gå rundt i rommet. Vi vil gå linje for linje, og jeg vil hjelpe du finne ut av linjen som vi trenger å skrive først. Så mens lengden på liste er større enn null. La oss starte i front. Hvilken linje skal jeg skrive her, i koden? STUDENT: Mens parentes n er større enn 0. JASON Hirschhorn: Mens n er stor enn 0. Så n er på størrelse med en liste, og vi sjekker om - [interposing VOICES] JASON Hirschhorn: - beklager? STUDENT: Hvordan vet vi at n er størrelsen av listen? JASON Hirschhorn: Beklager. Per PSett spesifikasjonen, søke og sortere funksjoner du trenger for å skrive, n er størrelsen av listen. Jeg glemte å forklare det her. Men ja. n er størrelsen listen, i dette tilfellet. Så mens n er større enn 0. OK. Det kan vise seg litt problematisk skjønt, hvis ting går på. Fordi vi vil fortsette å vite Størrelsen på listen i denne funksjon, men sier vi starter med et utvalg av fem heltall. Og vi går gjennom, og vi har nå snevret det ned til en rekke to heltall. Hvilke to heltall er det? Størrelsen er to nå som vi ønsker å se på, men som to er det? Betyr det fornuftig, det spørsmålet? OK. Jeg spør det igjen. Så vi starter med denne matrisen av 5 heltall, og n er lik 5, ikke sant? Vi skal kjøre gjennom her. vi vil sannsynligvis endre størrelse, høyre, så ting går videre. Hvilket er hva vi sier vi ønsker å gjøre. Vi ønsker ikke å søke hele greia igjen. Så sier vi endrer det til to. Vi tar halvparten av listen som er rart. Så bare plukke to. Så nå n er lik to. Jeg beklager dårlig tørr slette markører. Høyre? Og vi søker gjennom listen igjen med en liste over størrelse to. Vel, er vårt spekter fortsatt av størrelse 5. Vi sier at vi bare ønsker å søke 2 flekker i det. Så hvilke to stedene er de? Betyr det fornuftig? Er de de 2 venstre flekker? Er de de rette to stedene? Er de de midterste to stedene? Vi har brutt ned problemet, men vi faktisk vet ikke hvilken del av problemet vi fortsatt ser på, bare ved å ha disse to variablene. Så vi trenger litt mer da, mens n er større enn 0. Vi trenger å vite hvor det n er i vår faktiske array. Så er det noen som har en bytte til denne linjen? Det meste av denne linjen er helt riktig. Er det en annen tillegg? Kan vi bytte ut noe for n å gjøre denne linjen litt bedre? Mm-hm? STUDENT: Kan du initialisere en variabel som lengden til n som vil deretter bli brukt senere i funksjon? JASON Hirschhorn: Så initial en variabel lengde til n, og vi bruker det senere? Men da vi bare oppdatere lengde og vi fremdeles støte på dette problemet der vi kutte ned lengden på vårt problem, men vi vet aldri hvor, faktisk, at lengden kartene på. STUDENT: Er ikke det kommer til å skje senere når du sier, søke igjen, søke rett? Du kommer til å gå til en annen område av din - JASON Hirschhorn: Vi kommer til å gå til et område, men hvordan vet vi som er å gå til? Hvis vi bare har matrisen og dette n, hvordan vet vi hvor du skal gå til i matrisen. I ryggen, ja? STUDENT: Har du, i likhet, lavere grense og en øvre grense eller variabel noe sånt? JASON Hirschhorn: OK. Så dette er en annen idé. Snarere enn bare å holde orden på størrelse, holder vi oversikt over den nedre og øvre grense variabel. Så hvordan skal vi beregne størrelsen fra en nedre grense og øvre grense? [interposing VOICES] JASON Hirschhorn: subtraksjon. Og også å holde styr på den nedre bundet og øvre grense for å gi oss beskjed, er vi søker disse to? Er vi søker disse to over her? Søker vi midt to? Sannsynligvis ikke den midterste to, fordi dette, faktisk, er binært søk. Men nå vil vi være i stand til å få den størrelsen, men også grensene i tabellen. Kort sagt, hvis vi har vår giganten telefonboken, vi rive den i to. Vi vet nå hvor det mindre telefonboken er. Men vi er faktisk ikke ripping telefonboken i to. Vi trenger fortsatt å vite hvor nye grensene for vårt problem er. Er det noen som har noen spørsmål om det? Ja? STUDENT: Vil det fungere ved å skape en variabel, jeg, at du da bare skifte stilling i forhold til dens nåværende posisjon, og lengden, n? JASON Hirschhorn: Og hva er jeg? STUDENT: Som jeg være som liksom - Som du vil initial jeg å være den midtstilling av tabellen. Og så, hvis verdien i posisjon jeg i midten av matrisen i funnet være mindre enn verdien du trenger, jeg nå blir lengden av matrisen, samt verdien av i dividert med to. Som, se, du skiftet i - JASON Hirschhorn: Høyre. STUDENT: - opp til - JASON Hirschhorn: Så jeg er nesten positivt at vil fungere. Men poenget er, trenger du to biter av informasjon her. Du kan gjøre det med begynnelse og slutt, eller du kan gjøre det med størrelsen, og deretter noen markør. Men du trenger to stykker av informasjon her. Du kan ikke klare seg med bare én. Betyr det fornuftig? Så vi kommer til å gå gjennom, og vi kommer til å gjøre [uhørbart] og skape noen markører. Hva gjorde du skrive inn koden din? STUDENT: Jeg bare sa int bundet en er lik 0.. JASON Hirschhorn: La oss kalle som int, begynner. STUDENT: OK. JASON Hirschhorn: Det gjør mer fornuftig for meg. Og? STUDENT: Jeg sa, jeg gjette, int slutt. JASON Hirschhorn: int slutt. STUDENT: Jeg antar, n minus 1, eller noe sånt. Like, det siste elementet. JASON Hirschhorn: Så du skrev, int begynner lik 0, semikolon, og int ending lik n minus 1, semikolon. Så egentlig, hva vi gjør her, 0 den første posisjon. Og som vi vet i matriser, har de ikke gå opp til n, går de opp til n minus en. Så vi har noen grenser i vårt utvalg. Og disse innledende grenser skje for å være de første rammene av vårt problem. OK. Så det høres bra ut. Så hvis vi går tilbake til denne linjen, mens lengden av listen er større enn 0, det, i stedet for n, bør vi satt i her? STUDENT: Skriv ending minus begynnelsen. JASON Hirschhorn: Mens ending minus begynnelsen er større enn 0? OK. Og vi kunne, hvis vi ønsket å gjøre det litt hyggeligere, hva annet kan vi gjøre? Hvis vi ønsket å rengjøre denne koden opp litt? Hvordan kan vi bli kvitt den 0? Dette er bare en stil spørsmål. Det er riktig akkurat nå. STUDENT: Ending ikke lik begynnelsen? JASON Hirschhorn: Vi kan gjøre hva? [interposing VOICES] STUDENT: Ending er større? JASON Hirschhorn: Yeah. Vi kan bare gjøre mens slutt er større enn begynnelsen. Høyre. Vi har lagt til begynnelsen til den andre siden av det, og vi ble kvitt 0. Så dette ser bare en litt renere. OK. Så, mens lengden på listen er 0, vi skrev det, er større mens slutt enn begynnelsen. Vi kommer til å sette i vår nødvendig klammeparentes, og da det første vi ønsker å gjøre er å se på dem i en liten liste. Du? Kan du gi meg den - STUDENT: Hvis parentes verdi hakeparentes - JASON Hirschhorn: Hvis parentes verdi hakeparentes. STUDENT: ending delt på to. JASON Hirschhorn: Ending? STUDENT: Jeg ser et problem med - JASON Hirschhorn: OK. Vel, se på midten. Hvordan vet vi hva midten er? Yeah. Så la meg slette den koden. Hvordan vet vi hva midten er? I alt, når du har begynnelsen og til slutt, hvordan finner du midten? STUDENT: Du gjennomsnittet. STUDENT: Du legger dem sammen og deretter - JASON Hirschhorn: Legg dem sammen og da? STUDENT: Og du gjennomsnittlig. Dele det med to. JASON Hirschhorn: Legg dem sammen og dele på to. Så int midten lik? Tom, kan du gi den til meg? STUDENT: Begynnelsen pluss ending - JASON Hirschhorn: Begynnelsen pluss ending. STUDENT: Alle, bracket, delt på to. JASON Hirschhorn: Alle, i parentes, dividert med to. Så det gir meg midten av noe, korrigere? STUDENT: Du trenger også å runde det opp. JASON Hirschhorn: Hva gjør du mener, trenger jeg å runde det opp? [interposing VOICES] STUDENT: Fordi hvis det er en merkelig tall, så det er som - JASON Hirschhorn: Vel, OK. Så jeg kunne runde det opp. Men hvis det er et oddetall, en fem, kan jeg tar en bort fra midten. Eller hvis det er et partall, heller, det er en bedre sak. Hvis det er fire, vi har bare fire, kan jeg ta den første "midten", sitat, unquote eller den andre "midt" en. Enten ville arbeide for en binær søk, så jeg ikke egentlig trenger å runde det. Men det er en annen ting jeg må se på denne linjen. Vi kan ikke klar over det ennå, men vi vil komme tilbake til det. Fordi denne linjen faktisk fortsatt trenger en annen ting. Men så langt har vi skrevet fire linjer med kode. Vi har fått vår begynnelsen og slutter markører. Vi har vår mens loop, som kart på direkte til vår pseudo. Vi ser på midten som kart direkte på vår pseudo. Jeg vil si dette går til midten av listen, på linje med kode. Og så, når vi går til midten av listen, neste ting vi må gjøre er å sjekke om vår verdi er det for den pseudo vi skrev tidligere. Så hvordan skal vi sjekke om vår verdi er på midten av listen? Du. Hvorfor ikke gjøre dette? STUDENT: Hvis vår verdi er er på midten er lik uansett hva vi setter - Jeg mener lik lik - JASON Hirschhorn: It - OK. STUDENT: Jeg er ikke sikker på hva den variabel vi leter for selv, er fordi - [interposing VOICES] STUDENT: [uhørbart]. JASON Hirschhorn: Nettopp. Per funksjonen erklæringen, vi leter etter en verdi. Så vi søker etter en verdi i en matrise med verdier. Så du er helt riktig. Du vil gjøre, hvis åpen paren verdi brakett midten lukket vinkelen er lik verdi, og inni der hva trenger vi å gjøre? Hvis vår verdi er der, hva trenger vi å gjøre? [interposing VOICES] STUDENT: Return null. JASON Hirschhorn: Return sant. STUDENT: Return sant. JASON Hirschhorn: Michael, hva betyr denne linjen gjøre? STUDENT: [uhørbart] programmet har kjørt sin gang, og det er over, og du har det du trenger å gjøre? JASON Hirschhorn: Programmet eller hva? I dette tilfellet? STUDENT: Den funksjonen. JASON Hirschhorn: Funksjonen. Og så, for å gå tilbake til det som kalles den og gi den verdien, sant. Helt riktig. Main. Hva er returtypen av hoved, Michael? STUDENT: int, heltall? JASON Hirschhorn: int, akkurat. Et heltall. Det var bare et spørsmål for å være sikker dere har vært på toppen av det. Hva betyr det som regel tilbake, hvis alle ting fungerer bra? STUDENT: Zero. JASON Hirschhorn: Zero. Helt riktig. STUDENT: Hvis dette bare returnerer true, det er ingen informasjon som blir gitt om hva - Oh, er dette bare å si at det Verdien er inne i matrisen. JASON Hirschhorn: Nettopp. Dette programmet er ikke å gi informasjon av hvor verdien er. Det er bare å si, ja, fant vi det, eller nei, det gjorde vi ikke det. Så hvis nummeret funnet, returnere true. Vel, faktisk vi bare gjorde det virkelig hurtig med at en kodelinje. Så jeg skal flytte den linjen av pseudo. STUDENT: Trenger vi ikke å forandre rekken? Det bør være verdier, ikke verdi, ikke sant? JASON Hirschhorn: Beklager. Takk. STUDENT: Ja. JASON Hirschhorn: Denne linjen bør-verdier. Helt riktig. OK. Så vi har sett på den midterste listen. Hvis nummeret funnet avkastning sant. Fortsetter videre med vår pseudo, hvis midten er større, søk igjen. Så jeg hadde her, hvis antall høyere, søk igjen. Constantine, kan du gi meg denne linjen med kode? STUDENT: Hvis verdien av midten - JASON Hirschhorn: Så hvis verdi - hvis åpen paren verdier brakett midt tett brakett - STUDENT: Er mindre enn verdien? JASON Hirschhorn: Er mindre enn. STUDENT: Mindre enn verdien. JASON Hirschhorn: Verdi. Vel, faktisk, vil du sjekk om nummeret - Unnskyld. Dette er litt forvirrende. Men ellers hvis nummeret i midten av listen er større. STUDENT: Oh, OK. JASON Hirschhorn: Jeg kommer til å endre det. Else hvis midten er høyere, vi vil søke venstre, OK? Og hva gjør vi inne dette hvis tilstanden? STUDENT: Kan jeg gjøre en liten endring til tilstanden, endre den til annet hvis? JASON Hirschhorn: Else om? OK. Så denne koden vil kjøre omtrent det samme. Men det fine med å bruke if, else hvis, annet hvis eller hvis, annet hvis, annet betyr at bare en av dem skal skal kontrolleres, og ikke alle tre, potensielt. Og det gjør det litt finere på datamaskinen som er kjøre programmet. Så [? Constantine,?] vi er inne i denne linjen, annet hvis verdier, brakett midt tett brakett er større enn verdien. Hva trenger vi å gjøre? Vi trenger å søke venstre. Hvordan gjør vi det? Jeg kommer til å gi deg en start. Vi har disse to tingene kalles begynner og slutter. Så hva som må skje til begynnelsen? Hvis du ønsker å søke venstre for liste, vi får vår nåværende begynnelsen. Hva trenger vi å gjøre det? STUDENT: Vi satt i begynnelsen til midten pluss en. JASON Hirschhorn: Så hvis vi er søker venstre? STUDENT: Beklager, midt minus - så avslutningen ville være middel minus 1 og begynnelsen - JASON Hirschhorn: Og hva skjer til begynnelsen? STUDENT: Det forblir den samme. JASON Hirschhorn: Så Betydningen forblir den samme. Hvis vi søker venstre, er vi bruker samme begynnelsen - helt riktig. Og det slutter? Sorry, hva gjør ending lik igjen? STUDENT: Mellom minus en. JASON Hirschhorn: Mellom minus en. Nå, hvorfor minus en, ikke bare midten? STUDENT: Den midterste er ute av bilde allerede, fordi vi hadde sjekket at det er ute? JASON Hirschhorn: Det er helt riktig. Den midterste er ute av bildet. Vi har allerede sjekket midten. Så vi ikke ønsker "midten", sitat unquote, å fortsette å være i array som vi ser. Så dette er fantastisk. Else hvis verdier brakett midten er større enn verdien slutter likhets midten minus en. Jeff, hva om denne siste linjen? STUDENT: Else. Verdier midten er mindre enn verdien? JASON Hirschhorn: Vi vil du gir meg annet. Så hvis du ikke gir meg - STUDENT: Så da begynner ville være midt pluss en. JASON Hirschhorn: Begynnelsen likemenn midtre pluss 1, igjen, for den samme Grunnen til at Constantine ga oss tidligere. Og på slutten, har som ikke gitt meg en linje med kode ennå? Return false, Aleha, hva vi skriver her? STUDENT: return false. JASON Hirschhorn: return false. Og vi må gjøre det, fordi hvis vi ikke synes det, trenger vi å si at vi fant ikke det. Og vi sa at vi kommer til å returnere en bool, så vi definitivt må tilbake en bool sted. Så la oss kjøre denne koden. Jeg faktisk kommer til å - så vi er i terminalen. Vi vil fjerne vårt vindu. La oss gjøre alt. Vi fant det er en feil. Det er en feil på linje 15, forventet semikolon ved enden av erklæring. Så hva gjorde jeg glemme? STUDENT: Semicolon. JASON Hirschhorn: Semicolon rett opp her. Jeg tror det var Tom kode. Så Tom, [uhørbart]. Bare tuller. La oss ikke gjøre hele igjen. STUDENT: Hva Dropbox katalog bør vi være i for dette? JASON Hirschhorn: Så du kan bare se for denne biten. Men igjen, hvis du ønsket å flytte denne koden på pset3 katalogen for å prøve det ut, det var det jeg gjorde. Hvis du vil legge merke til her - sorry, godt spørsmål. [? LS,?] Jeg har her på find.c koden fra denne ukens distro kode. Jeg har helpers.h. Jeg har en Make-fil som jeg faktisk redigert litt for å inkludere disse nye filene vi skriver. Alt dette kode vil være tilgjengelig, ikke fordelingskode, men den nye Gjør fil, vil den nye helpers.h fil være tilgjengelig på nettet for nedlasting. Igjen, så de som er ekstra koder har vi. Så gjør alt, per denne linjen, gjør finne, binær, boble utvalg - merker alle tre av dem og kompilerer inn denne kjørbar kode finne. Så generelt, ønsker vi ikke til rett til check50. Vi ønsker å kjøre noen tester på vår egen. Men bare så vi kan fremskynde dette litt, check50 2013 pset3.find vil passere i helpers.c-- my bad. Jeg har ikke det akkurat nå. Så vi faktisk kommer til å kjøre koden på ordentlig. Usage.find /, vet du hva det betyr? STUDENT: Du trenger en andre kommandolinje på den. JASON Hirschhorn: Jeg trenger en andre kommandolinje. Og per spesifikasjonen, jeg trenger å gå inn på hva vi leter etter. Så la oss se for 42.. Vi vil holde det i sortert, fordi vi har ikke skrevet en slags funksjon ennå - 42, 43, 44. Og Kontroll D ikke fant nålen i høystakken. Det er ille. Det er definitivt der. La oss prøve noe annet. Kanskje det er fordi jeg satt det i begynnelsen. La oss gjøre 41, 42, 43. Det vi går. Den fant det. La oss sette det på slutten nå, bare slik at vi kan være grundig - 40, 41, 42. Fant du ikke nålen. Så jeg nevnte dette tidligere. Dessverre, jeg visste dette kom til å skje. Men for pedagogiske formål, det er godt å utforske det. Det fungerer ikke. For noen grunn, kan det ikke finne det. Vi vet hva som er der, men vi blir ikke å finne det. Så en ting vi kan gjøre er å gå gjennom GDB å finne det, men gjør noen, uten å gå gjennom GDB, har en følelse av hvor vi skrudd opp? [? Madu? ?] STUDENT: Jeg tror det kan bli når slutter er lik begynnelsen, og det er bare ett element listen. Da er det bare ignorerer det i stedet av faktisk sjekker det. JASON Hirschhorn: Det er helt riktig. Når ending tilsvarer begynnelsen, gjør vi fortsatt ha et element i vår liste? STUDENT: Ja. JASON Hirschhorn: Ja, faktisk, vi har ett og bare ett element. Og det vil mest sannsynlig skje når, per koden vi testet, er vi på forsiden av høystakken eller i slutten av høystakken. Det er der begynnelse og ending kommer til å like ett, med binære søk. Så i disse to tilfellene det ikke fungerte, fordi slutter var lik begynnelsen. Men hvis ender er lik begynnelsen betyr dette mens loop utføre? Det gjør ikke det. Og vi kunne ha sjekket som igjen gjennom GDB. Så hvordan kan vi løse denne koden, fordi når mens slutt er lik begynnelse, ønsker vi også dette mens sløyfen til å kjøre. Så hva fikse kan vi gjøre til linje 18? STUDENT: [uhørbart] er større enn eller lik. JASON Hirschhorn: Helt riktig. Mens ending er større enn eller lik begynnelsen. Så nå, sørger vi for å få det hjørne tilfellet på slutten. Og la oss se. La oss kjøre dette en gang til. La oss gjøre alt. Igjen, må du bare følge med her. Finn 41 denne gangen. Bare holde det konsekvent. Finn 42. La oss sette det i begynnelsen - 42, 43, 44. Vi fant det. Så det var faktisk endring vi trengte å gjøre. Det var en masse koding vi nettopp gjorde, binære søk. Er det noen som har noen spørsmål før Jeg går videre inn i linjene vi skrev i binære søk eller hvordan vi skjønte ut hva vi finne ut? Før vi går videre, jeg ønsker også å påpeke ut at av og store, vi kartlagt vår pseudo-kode ett til en på vår kode. Vi har at vanskelige ting å regne ut med begynner og slutter. Men hadde du ikke funnet det ut, du ville ha skrevet ganske mye identisk kode, lagre for de to øverste linjene. Og så ville du ha realisert når du har gjort det i kontroller og saker som du trenger noe annet. Så selv om du hadde fulgt vår pseudo-kode linje til linje, ville du har fått alle unntatt to linjer koden du trengte å skrive. Og jeg ville være villig til å satse på at dere ville ha alt funnet ut ganske raskt, at du trengte å sette en slags markør i det å regne ut hvor du var. Det igjen, er kraften til å gjøre pseudo-kode på forhånd. Så vi kan gjøre logikken først, og deretter vi kan bekymre seg om syntaks. Hadde vi vært forvirret om logikken mens du prøver å skrive denne koden i C, vi ville ha fått all messed opp. Og da ville vi stille spørsmål om logikk og syntaks og meshing dem sammen. Og vi ville ha fått tapt i det som raskt kan bli en svært vanskelig problem. Så la oss gå videre nå til valg liksom. Vi har 20 minutter igjen. Så jeg har en følelse vi vil ikke være i stand til å komme gjennom alle valg slags og boble slag. Men la oss i det minste forsøke å fullføre valget slag. Så implementere utvalg slags bruker Følgende funksjon erklæring. Igjen, dette er tatt fra oppgavesettet spesifikasjon. Int verdier er parentes, er en rekke heltall. Og int.n er størrelsen på denne matrisen. Utvalg sorter kommer å sortere denne tabellen. Så per vår mentale modell av utvalg sortere, trekker vi den - første, vi går gjennom listen den første tid, finner det minste tallet, sette den i begynnelsen, å finne den nest minste tallet, sette den i andre posisjon hvis vi ønsker å sortere i stigende rekkefølge. Jeg er ikke tvinge deg til å skrive pseudo-kode akkurat nå. Men før vi gjør koden som en klasse i fem minutter, har vi tenkt å skrive pseudo-kode, slik at vi har noen følelse av hvor vi skal. Så prøv å skrive pseudo-kode på egen hånd. Og deretter forsøke å snu det pseudo-koden inn kode. Vi vil gjøre det som en gruppe i fem minutter. Og selvfølgelig, la meg vite om du har noen spørsmål. STUDENT: At det? JASON Hirschhorn: Se hvor langt du kan komme i to minutter til. Jeg forstår at du ikke vil være i stand til å fullføre. Men vi vil gå over dette som en gruppe. Du er all koding så [uhørbart], så jeg er beklager å stoppe hva du gjør. Men la oss gå gjennom dette som en gruppe. Og igjen, binære søk, du alle gi meg en hvis ikke flere linjer med kode. Takk for det. Vi kommer til å gjøre det samme Herfra koden sammen som en gruppe. Så utvalg sort - la oss skrive noen raske pseudo-kode. Per mental modell, kan noen gi meg den første linjen av pseudo-kode, er du snill? Hva ønsker jeg å gjøre? STUDENT: Mens listen er ute av drift. JASON Hirschhorn: OK, mens listen er ute av drift. Og hva mener du med "ute av drift?" STUDENT: Mens [uhørbart] har ikke blitt sortert. JASON Hirschhorn: Mens listen er ute av drift, hva gjør vi? Gi meg den andre linjen, vær så snill, Marcus. STUDENT: Så finner den neste minste tallet. Dette vil bli innrykket. JASON Hirschhorn: Så finner den neste minste tallet. Og så noen andre? Når vi finner den nest minste nummer, hva gjør vi? Jeg kommer til å si finne det minste tallet. Det er det vi ønsker å gjøre. Så finn det minste tallet. Så hva gjør vi? STUDENT: [uhørbart] til begynnelsen. JASON Hirschhorn: Sorry? STUDENT: Plasser den i begynnelsen av listen. JASON Hirschhorn: Så legg den i begynnelsen av listen. Og hva gjør vi for å tingen som var i begynnelsen av listen, ikke sant? Vi overskriver noe. Så hvor skal vi sette det? Ja, Anna? STUDENT: Hvor den minste antallet var? JASON Hirshhorn: Så legg begynnelsen av listen hvor minste tallet var. Så mens listen er ute av drift, finne det minste tallet, plasser den i begynnelsen av listen, sett begynnelsen av listen der minste tallet var. Marcus, kan du omformulere denne linjen mens listen er ute av drift? STUDENT: Mens tallene har ikke blitt sortert? JASON Hirshhorn: OK, så for å at tallene ikke vært sorteres, hva trenger vi å gjøre? Hvor mye trenger vi å gå gjennom denne listen? STUDENT: Så jeg antar en for loop, eller samtidig, er mindre, mens tallene kontrolleres enn lengden av listen? JASON Hirshhorn: OK, det er bra. Jeg tror jeg misphrased spørsmålet mitt dårlig. Jeg prøvde bare å få på vi er nødt til å gå gjennom hele listen. Så mens listen er ute av drift, for meg, er vanskelig å kartlegge på. Men i utgangspunktet, det er hvordan Jeg tenker på dette. Gå gjennom hele listen, finner minste tallet, plasser den i begynner - faktisk, du har rett. La oss sette dem begge. Så mens listen er ute av drift, vi behov for å gå gjennom hele listen gang, finne det minste tallet, sted det i begynnelsen av listen, sette begynnelsen av listen hvor minste tallet var, og hvis det listen er fortsatt ute av drift, vi har må gå gjennom dette prosessen på nytt, ikke sant? Det er derfor valg sortere, Big-O runtime av utvalget sortere, anyone? STUDENT: n squared. JASON Hirshhorn: n squared. Fordi som Marcus og jeg innså her er vi nødt til å går gjennom listen listen antall ganger. Så går gjennom noe av lengde n n antall ganger er faktisk n squared. Så dette er vår pseudo. Dette ser veldig bra ut. Er det noen som har noen spørsmål om pseudo? Fordi faktisk utvalg sorter bør trolig komme 1-1, kode fra pseudo. Så noen spørsmål om logikken i pseudo? Spør den nå. Utvalg sort - mens listen er ute av orden, kommer vi til å gå gjennom det og finne den minste hver gang og legg den i fronten. Så mens listen er ute av drift, kan noen gi meg at kodelinje som har ikke gitt meg en linje av kode ennå, please? Det høres ut som en hva? STUDENT: Det er en for-løkke. JASON Hirshhorn: Det høres liker en for-løkke. OK, kan du gi meg for loop? For - STUDENT: i lik 0. JASON Hirshhorn: i eller - Hva er det vi mangler? Hva går rett her? STUDENT: Int. JASON Hirshhorn: Nettopp. (Int i = 0, - STUDENT: i