[Powered by Google Translate] [Avsnitt 3] [mindre bekväm] [Nate Hardison] [Harvard University] [Detta är CS50.] [CS50.TV] Okej, låt oss komma igång. Välkommen till vecka 4 av CS50. Om ni öppnar en webbläsare och öppna upp pset 3, Scramble med CS50, kommer vi att börja gå genom den del av frågorna där. Precis som förra veckan, kommer vi att arbeta i CS50 utrymmen, Om du också dra upp det också, och om du gå vidare och besöka denna länk som jag har här uppe i toppen. Det är dags att komma igång. Vi har vår lilla hi programmet här. Inget galen. En av de första saker jag vill göra med er idag är att gå över några lösningar till problem Set 1, typ av exempelvis lösningar, bara så du kan få en känsla för vilka typer av kod personal skriver, vilka typer av kod andra elever skriver, och har du ta en titt på det eftersom jag vet att det är konstigt när du skickar en lösning på ett problem set och få kommentarer på din egen version, men ibland är det bra att se hur andra människor gjorde det, särskilt de som är snygg. För det mesta, jag var verkligen imponerad av de lösningar som ni producerat. Jag har ännu inte börjat titta på dina 2s problembild, men om de är något liknande den första, det betyder ingenting annat än bra saker. Om du tittar på mina ändringar, låt oss börja hela vägen ner på Revision 1, och vi kommer att ta en snabb titt på en Mario-lösning. Om du drar upp detta, dessa program som vi kommer att presentera är korrekta. Det var inte korrekthet problem med dessa problem, utan snarare, Vi vill tala lite om de olika utformning frågor som används här. En av de saker som var intressant om lösningen är att det använde denna nya konstruktion som kallas pund definiera, ibland även kallad en hash definierar. Låt mig zooma in på det här. En # define kan du ge namn till dessa nummer i ditt program. I detta fall, den maximala höjden av en pyramid i Mario var 23 och i stället sätta 23 i min kod- Vi hänvisar till den så hårt kodning 23 - istället detta ger namnet MAX_HEIGHT till det numret, så att här nere i min do-while-slinga kan du faktiskt hänvisa till MAX_HEIGHT istället för att sätta numret 23 tum [Student] Vad är fördelen med att göra det? Det är en stor fråga. En är läsbarheten. En fördel med att använda denna # define är läsbarheten. När jag läser denna kod kan jag se vad som händer. Jag kan se i detta tillstånd här att vi testar för höjden är <0, vilket vi kunde också ha definierat att vara en minsta höjd eller en höjd min. Den andra fördelen är att jag sedan kan läsa resten av raden för att se att vi också kontrollera att se till att höjden inte är större än max höjd, eftersom vi kommer att fortsätta medan höjden är större än max höjd. Den andra fördelen är-om jag zoomar ut lite här- Om jag kör det här programmet och jag kör den, säga med 23 just nu, Det kommer att skriva ut alla 23 rader precis som det. Men att jag ville ändra max höjd, och nu vill jag att begränsa den maximala höjden av pyramiderna att vara bara säga-man, som var funky. # Include , # define MAX_HEIGHT, och låt oss säga att vi ville ställa in den lika med 10. Nu vid denna tidpunkt, var allt jag hade att göra ändra det i detta en plats. Jag kan kompilera koden och nu om jag försöker och skriva in 12, Det kommer att fråga mig igen. I det här fallet använder vi bara MAX_HEIGHT gång. Det är inte så stor av ett besvär att gå i och ändra det i while-slingan om du behöver. Men i program där du refererar till samma magiska nummer om och om igen, det # define mekanism är verkligen praktiskt eftersom du byter bara det en gång högst upp i filen, det är oftast där du placerar dem- och förändringen perkolerar genom resten av filen. Andra saker som jag ville att notera i detta uppdrag som jag tyckte såg riktigt nice, en var namngivning av variabler. Du ser här att vi har heltalsvariabler kallas rad och kallas höjd. Utrymmen, hashar, hjälper det att göra koden lite mer lättläst, gör det lite mer förståeligt vad som faktiskt händer. Detta är i motsats till användning säga, slumpmässiga bokstäver eller bara rappakalja helt. En sista sak jag påpeka är att i för slingor, ofta dessa iterator variabler, dessa räknare som du använder i din för loopar, Det är standard och konventionellt att starta dem med antingen i och sedan j och sedan k och går vidare därifrån om du behöver fler variabler, och detta är bara en konvention. Det finns massor av konventioner. Det beror på programmeringsspråket du använder. Men i C börjar vi oftast med jag. Det är inte meningsfullt att använda, säger a eller b beroende på situationen. Det var allt för den här. Om du nu dra upp Revision 2, kommer du att se en annan Mario, och detta är liknar den andra en som vi just såg, men det gör något slags cool. Om vi ​​tittar på det här avsnittet här innanför inre for-slingan, de använder några galna ser syntaxen här rätt i denna linje. Detta kallas en ternär operatör. Det är en om annat uttalande kondenseras till en rad. Villkoret är denna del inom parentes. Det är detsamma som att säga om j > Sam. Sam. Som Sam sa, är att linjär sökprocess kommer att bli riktigt långsam, och i stället med binär sökning, är hur det fungerar att varje gång vi går igenom en iteration av vår sökning algoritm, vi kommer att dela upp listan i halv huvudsak i två mindre listor. Och sedan på nästa iteration i slingan, vi dela upp det igen i andra mindre listor. Som ni kan se, håller problem att få mindre och mindre eftersom vi håller kasta hälften av listan varje gång. Hur fungerar kasta arbete? Precis som en påminnelse, vad vi ska göra om vi var en dator och vi var, säg, söka efter nummer 5 i den här listan är att vi skulle plocka ett nummer i mitten. I mitten av denna lista, eftersom det finns 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 siffror, vi skulle plocka numret antingen vid 4: e eller 5: e positionen, och vi skulle kalla det i mitten av vår lista. Välj antal i mitten. Sedan, precis som Sam sa, vi testar för att se om detta antal är lika till det nummer vi vill få eller vår önskat nummer. Om det är lika, då vi har hittat den. Vi vinner. Om det inte är lika, så finns det ett par fall. De två fallen är antingen antalet måste vara större än antalet som vi tittar på, eller det är mindre än. Om det är större, flyttar vi till höger. Och om det är mindre går vi till vänster. Och vi upprepa hela processen igen på antingen den högra halvan eller den vänstra halvan av listan. Det första problemet i dagens avsnitt är att räkna ut hur vi kan faktiskt börja att uttrycka detta i C-kod. Vi har fått pseudokoden här. Vad vi börja göra är jag dra upp en helt ny plats, Spara denna översyn så att vi har dessa anteckningar för senare, Vi kommer att radera allt detta, och sedan kopiera och klistra in från problemet inställda denna information i våra utrymmen och förhoppningsvis inte går sönder. Perfekt. Om ni alla gör det, kopiera och klistra in den här koden i ditt nya rum, till ett som är tomt. Låt oss försöka Daniel. Om du kompilera och köra programmet, fungerar det? Nej >> Vad är det säger? Det säger kontrollen når slutet av icke-tomma funktion. Ja, så låt mig försöka köra det. Har ni sett det här förut? Vet du vad det här betyder? Okej, låt oss dissekera detta lite. Det säger i file.c på linje 9, kolumn 1 har vi ett fel, precis som du sa, och det säger att det är till följd av felet varning och returtyp varning. Det ser ut som något som händer med avkastningen typ, som är vettigt. Vi har en icke-void funktion, vilket innebär att vi har en funktion som inte återvänder ogiltig. En ogiltig funktion är en som ser ut så här: void foo (), och det är ogiltigt på grund av avkastningen typ är ogiltigt, vilket innebär att om vi hade något här Liksom retur 1, skulle vi få ett kompileringsfel för detta. Men vi har en icke-void funktion. Vår icke-void funktion i det här fallet är vår sökfunktion eftersom det har en avkastning typ bool. När det säger att kontrollen når slutet av en icke-void funktion, det är för att sökningen inte har return. Det är inte returnera någonting av typen bool. Vi kan fixa det, och vad tycker ni sök skulle återvända som standard? Vad bör vara standard returvärdet sökning? Eftersom det är vad vi kan lägga till i slutet. Charlotte, har du några-? Sant eller falskt? >> Sant eller falskt. Vilken? Falskt. Jag vet inte. Falskt? Låt oss försöka det. Varför skulle du säga avkastning falskt? Det är bra intuition. [Charlotte] Jag vet inte. Vi kommer att returnera false i detta fall eftersom det kommer att vara vår standard om det av någon anledning är tom eller nålen att vi letar efter finns inte. Sedan i slutet, om vi inte tillbaka riktigt tidigare i denna funktion, Vi vet alltid att denna funktion kommer att säga Nej, det är inte i arrayen. Det är inte i höstacken. Om vi ​​nu kompilera och köra det, låt mig spara så att vi kan dra upp den. Om vi ​​nu kompilera och köra vårt program, bygger det. Vi får vår lilla snabb. Om jag slog 4-uh-oh. Det tog inte skriva ut något. Det ser ut som allt slutade bra. Vi måste fylla i. Vi pratade om algoritmen i pseudokod lite sen. Låt mig se, spara, och jag ska dra det algoritm upp igen. Låt oss slå den här killen. Nix. Där är det. Hur gör vi det? Vad skulle vara en bra strategi för start denna kod? Du måste välja ett nummer i mitten. Hur väljer vi ett antal i mitten av en array? Några förslag? [Student] strlen delat med 2. Strlen delat med 2. Det är en stor en. Strlen arbetar med särskilda typer av arrayer. Vilka typer av arrayer? String arrayer, tecken kedjor. Det är samma typ av koncept som vi vill tillämpa, men vi kan inte använda strlen eftersom vi inte har en mängd tecken. Vi har en mängd Ints. Men vad får strlen för oss? Vet du vad det blir för oss? [Student] strlen får oss längden. Exakt, det blir vi längden. Strlen får längden av uppsättningen för oss. Hur får vi det i vår binära sökprogram? Hur skulle du få längden på en array? [Student] strlen? Du kan få längden på ett korrekt formaterad C string array med strlen. Problemet är dock att vi inte har en sträng array. Om vi ​​ser tillbaka på den här koden, har vi denna heltal array. Hur vet vi hur lång tid det är? [Student] Finns det en motsvarande en för endpoint, som int l eller något? Det visar sig att det faktiskt inte, och det på ett sätt, det är en av de saker som är bara bra att veta om C, att det inte finns något sätt att få längden på en matris om allt jag ger dig är matrisen. Anledningen till att det fungerar med strängar, anledningen strlen verk, är att om en sträng är felaktigt formaterad, det kommer att ha den där speciella \ 0 tecken i slutet. Du kan också tänka sig om man har en felaktigt formaterad sträng och det finns ingen \ 0 tecken där, så det hela inte fungerar. [Student] kan du lägga till \ 0? Vi kunde i detta fall. Vi skulle kunna lägga någon form av \ 0 eller någon form av betecknar karaktär och sedan använda det. Men det är inte riktigt kommer att fungera eftersom \ 0 är en röding typ, och här har vi Ints. Den andra saken är att vi skulle använda ett speciellt värde Liksom -1 för att markera slutet av en array då vi aldrig kunde lagra en -1 i våra heltal matriser. Vi skulle vara fast. Det visar sig att det enda sättet att få längden av en array i C är att faktiskt komma ihåg det när du ställer upp och sedan skicka den runt med matrisen så att när jag har en funktion som kommer att göra en del arbete på en rad heltal eller flöten eller dubbel eller vad har du, Jag måste också ge funktionen arrayen längd, och det är precis vad vi har gjort här i sökfunktionen. Om man tittar, vad vi har gjort när vi passerar i vår grupp här, passerar vi också i längd, storlek. Det händer bara att vi har kallat denna variabel här, denna parameter eller argument. Detta kallas en funktion argument lista eller parameterlistan och dessa kallas även argument eller parametrar. Människor använder olika termer vid olika tidpunkter. Jag utbyta Ibland dem själv. Det råkar vara så att denna variabel här heter liknande till detta definiera # upp här. Men de är inte samma sak. Aktiveringen spelar roll. Om man tittar på vad som händer här, förklarar vi vår int array, som vi har kallat nummer. Vi har gett det vår storlek, vilket motsvarar vår # define upp på toppen. Det kommer att vara 8. Och sedan när vi kallar då vår sökfunktion nere, vi passerar i antalet vi vill söka, som vi har uppmanas fått från användaren. Vi passerar i arrayen, detta nummer, och sedan har vi också passera i storleken av arrayen, och sedan värdet på storlek 8 får lagras eller skickas till denna heltalsvariabel kallas storlek. Vi har storleken på matrisen. Nu om vi går tillbaka till vad vi talade om tidigare, Jag tror Missy tog upp den punkt som vad vi behövde göra är att få längden på arrayen och dela det med 2, och det kommer att ge oss mittpunkten. Låt oss se. Kan jag ha någon skriver detta och spara det i rymden? Vad sägs om Leila? Kan jag få dig att skriva detta i? Skriv den första raden där du tar längden på arrayen och få mittpunkten och förvara den i en ny variabel. Jag ska ge er ett par sekunder. Är du redo? [Student ohörbart] Visst, jag kunde ha dig att beräkna mittpunkten av höstack arrayen inne i sökfunktionen använda längden av höstack arrayen, vilket är storleken variabeln? Inget knepigt här. [Leila] Bara storlek / 2 och just- Och spara den, och tryck på knappen Spara upp här i toppen, och vi kommer dra upp den. Perfekt. Där kör vi. Toppen. Som kommer detta sammanställa? [Leila] Nej, den måste vara högre. [Nate] Ja, så vad behöver vi göra? [Leila] Liksom int mittpunkt eller något. Toppen. Ja, låt oss göra det, int mittpunkt = storlek. Kommer detta sammanställa? Låt oss ta bort denna kommentar och få det ur vägen. Vad kommer inte kompilera om detta? Vi gör inget med heltal, så vi måste skriva ut det eller nåt sånt. Ja, exakt. Vi får en oanvänd variabel. Vad kommer inte att fungera om det här? Jag tror att du sa något, Sam. Semikolon. Ja, jag saknar dem semikolon. Det kommer att vara en konstant sak under hela mandatperioden. Det sista jag gör är att jag sätter lite tomt utrymme på båda sidor av denna aktör här, eftersom det är oftast hur vi gör det enligt vår stilguide. Vi har mittpunkten av vår grupp. Nu om vi minns tillbaka till vår algoritm, vad var det andra steget som vi var tvungna att göra när vi har mittpunkten? [Student] Om det är större [ohörbart]. Ja, så vi måste göra någon form av jämförelse, och vad är det vi jämför här? Du sa att om den är större än. Vad är det i den meningen hänvisar till? Antalet som kommer upp, om det är större än mittpunkten och sedan gå upp till arrayen? Exakt, så antalet som kommer upp när vi- Nålen, så vi jämföra med nålen, och vad vi jämför mot nålen? Eftersom nålen är vad vi letar efter. Vi jämför det att komma till mittpunkten. Men gör det meningsfullt att kontrollera Om st = mittpunkten? Verkar det vettigt? Har oense någon? Låt oss ge det ett försök, om (nål == mittpunkten). [Student] Har printf du hittat den. [Nate] printf ("Vi fann det \ n"); Annars-Jag kommer att börja göra något annat här. Jag ska börja sätta hängslen runt om uttalanden hela tiden bara för att om vi lägger mer grejer, sedan Vi får inte kompilatorer. Ja, Sam. Du har en poäng. Problemet är att mittpunkten representerar en position i matrisen, men du kan få det att representera värdet i den positionen i matrisen. Det är en bra plats. Har alla höra vad Sam sa? Han sade att mittpunkten som är representerar bara en position i arrayen, men det är inte själva elementet i arrayen. Om du tänker på koden som skrivits just nu, om vi ser på denna array här nere, som har 8 element i den, Vad är värdet av mittpunkten kommer att vara i denna funktion? [Student] 4. [Nate] 4. Om vi ​​ser till antalet 4 - och vi kan bara köra denna kod och sätta lite sorgset ansikte här eftersom vi inte tycker att det-om vi kör den här koden som är just nu, ladda upp den, byggnad, låt mig scrolla ner, och om vi ser till antalet 4, vi fann det, men vi fick inte detta att printf ja. En anledning är att vi inte tillbaka riktigt, men vi hittade verkligen nummer 4? Och Sam säger nej. Vad hittade vi? Vi hittade verkligen mittpunkten, som om vi tittar på matrisen här nere, det kommer att bli elementet vid index 4 som vi tittar på, vilket är 23. Hur får vi faktiskt det elementet vid mittpunkten och inte bara mittpunkten själv? [Student] Vi skulle komma in röding eller något? Vad skulle det göra, bara av nyfikenhet? Kan du utveckla lite mer? Du måste omvandla läget i antal, så du har att göra ett samband, jag tycker det är röding, men det kanske inte. Ja, det är en bra sak. Vi har gjort en hel del av detta omvandla positioner i tecken, dessa tecken, i de första två problemområden uppsättningar. Det visar sig att här är det nästan lika tillgång till te tecknet i en sträng, om det är vettigt. Här vill vi komma åt mittpunkten elementet. Hur gör vi det? Kevin, har du några förslag hur vi kan göra det? Du kan göra höstack, sluten öppen konsol, mitten, hållare. Kan du skriva det för oss? Spara den här, och vi kommer dra upp det. Vi tittar på den här raden 9, och vi inser att vi inte vill jämföra nålen till mittpunkten, men i stället vill vi jämföra nålen till elementet i position mittpunkt i vår höstack matris. Cool. Där kör vi. Ja, det ser det ganska bra, om (nål == höstack [mittpunkt]). Vi hittade det. Om vi ​​nu kör koden-Vi säkerhetskopiera lite- Det sammanställer, det går, och nu när vi letar efter 4, Vi hittade inte det för nu är vi faktiskt få numret 23. Vi får värdet 23, och det är vad vi jämför med vår nål. Men det är bra. Det är ett steg i rätt riktning. Det är vad vi försöker göra. Vi försöker inte jämföra nålen mot positioner i arrayen utan snarare mot de faktiska elementen i arrayen. Om vi ​​ser tillbaka nu på nästa steg i vår algoritm, vad är nästa steg? Leila redan nämnt det kort. [Student] Kontrollera om det är större än eller mindre än och sedan bestämma vilken väg att flytta. [Nate] Ja, så skulle hur vi gör det? Kan du sätta i några-Jag sparar denna översyn, och sedan om du sätter i några rader som kommer att göra det. Ja, Charlotte. >> Jag har en fråga. Borde det inte vara mittpunkten - 1 eftersom det första är det är 0 indexeras, så om vi sätter 4, det är faktiskt inte det tecken vi letar efter? Ja, och det andra problemet med det är- Det är en stor fångst, eftersom det kommer att sluta upp händer eventuellt om vi hålla rörliga och vi inte någonsin ändra början? Jag antar att vad vi kan sluta göra försöker komma åt elementet vid den 8: e positionen av arrayen, som i detta fall inte existerar. Vi kommer att vilja göra någon form av redovisning av det faktum att vi har några noll indexering. [Charlotte] Tyvärr, jag menade mittpunkten - 1 i hakparenteser. Vi kan göra det. Vi ska återkomma till denna fråga i bara lite. När vi börjar komma till den faktiska looping, det är då vi får verkligen se detta spelar in. För närvarande kan vi göra det, men du är helt rätt. Att noll indexering kommer att ha en effekt som vi måste ta hänsyn till. Låt oss se. Hur är det större än och mindre än? [Student] Jag får hur man gör det större än och mindre än en del. Jag var bara inte säker på vad du vill skriva ut om du tycker att det är mindre än höstacken mittpunkten eller större än. Här kan jag spara det I've- [Nate] Ja, om du sparar det du har, och vi kommer att dra upp den. Där kör vi. [Student] Och jag satte frågetecken för vad jag inte visste. [Nate] Det ser bra ut. Här har vi frågetecken eftersom vi fortfarande inte vet vad vi ska riktigt göra ännu. Vad skulle vi vilja göra-oops, vi har några hängslen alla funky på oss. Vi kommer korrigera dessa hängslen. Där kör vi. Och så vad vill vi göra, enligt vår algoritm, Om vi ​​inte hittar nålen? Säg i det fall att nålen är mindre än vad vi tittar på. Kevin. Bara titta på den vänstra halvan. Just det, så vi sätter en kommentar här som säger "titta på vänstra halvan." Och om nålen är större än höstacken vid mittpunkten, vad vi vill göra? [Student] om du tittar på den högra halvan. Titta på den högra halvan, "titta på högra halvan." Inte så illa. Okej, så på denna punkt, saker ser ganska bra ut. Problemet med koden som skrivs är vad? [Student] Du har inte slutpunkterna för halvorna. Rätt, vi har inte slutpunkter för halvorna. Vi är också bara kommer att gå igenom detta en gång. Vi kommer bara att titta på en mittpunkt. Antingen elementet är där, eller är det inte. För att slutföra detta behöver vi göra någon form av upprepning. Vi måste fortsätta att upprepa tills vi finner att antingen elementet är där eftersom vi har minskat ner och äntligen hittat det, eller det är inte där för att vi har tittat igenom alla de saker i lämpliga halvorna av gruppen och fann att ingenting finns i det. När vi har fått denna upprepning pågår, vad ska vi använda? [Student] En slinga. Någon sorts loop. Ja. [Student] Kan vi göra en gör-while-slinga och få det göra det och sedan när nålen inte lika-Jag är inte säker på var jag skulle med. Men ungefär som gör att så länge det inte är lika med värdet som användaren indata. Ja, så låt oss se, hur kan detta skriver själv? Du sa låt oss använda en gör-while-slinga. Var gör starten? [Student] Direkt efter storlek / 2. [Nate] Okej, och vad ska vi göra? Vi ska fylla i medan senare. Vad ska vi göra? [Student] Gör inte vi vill göra alla grejer vi har i om delen? [Nate] Gör allt det här, bra. Kopiera och klistra in. Åh, mannen. Låt oss se om detta fungerar, om vi kan fliken här över. Vacker. Okej, och vi sparar detta så ni har det. Okej, och vi kommer att göra detta samtidigt, vad var tag skick du var ute efter? [Student] Medan nålen inte är lika, så som utropstecken. Men jag är inte säker på exakt vad det är ännu. [Nate] Ja, det här är ett sätt att göra det. Sam, har du en kommentar? [Sam] Jag minns när jag tittade på filmerna, Jag tog en skärmdump av en av-som när vi gjorde pseudokod för det, fanns ett visst samband mellan max och min. Jag tror det var något som om max är allt mindre än min. Fick det. [Sam] Eller som om max är inte mindre än min eller något liknande, eftersom det skulle innebära att du har sökt allt. Ja, så vad låter det som max och min syftade på? [Sam] Värden som-heltal som kommer att förändra i förhållande till där vi sätter mittpunkten. Exakt. [Sam] Vid denna tidpunkt kommer det att [ohörbart] beräkna max och min. Mittpunkt är max och min idé. Gör det meningsfullt att folk? Om vi ​​skulle börja titta på hur vi ska göra det här iteration, du är helt rätt att vi vill använda någon form av gör-while-slinga. Men jag antar att om vi kommer ihåg vad som händer på plats i denna array och vad som faktiskt händer-Jag ska skriva hit- vid första iteration av binärsökning har-vi Jag kommer att använda B och E för att beteckna början. Och sedan i slutet av vår grupp. Vi vet att i början är på 4 rätt över här, och vi vet att slutet är 108. Säg att vi söker efter numret 15. Första gången vi gör detta, som vi såg tidigare, mittpunkten antingen kommer att vara 16 eller 23 beroende på hur vi beräknar saker. Sedan jämnt dela i mitten skulle ge oss detta utrymme mellan 16 och 23, kan vi inte jämnt dela den eller dela den och få på en sann mittpunkt. Vi ska titta på 16. Vi kommer att inse "Hej, 16> 15 som vi letar efter." Att sedan titta på den vänstra halvan av matrisen vad vi ska sluta göra är kasta hela denna övre del och sade: "Okej, nu vår slutpunkt kommer att vara här." Nästa iteration av vår slinga, vi nu tittar på detta array, effektivt har kasseras denna del eftersom nu Om vi ​​tar mittpunkten är skillnaden mellan början och slutet, finner vi vår mittpunkt är 8, som vi kan testa 8 för att se var den är i förhållande till antalet vi letar efter, 15, tycker att 15 är större, så vi måste flytta till den högra delen av listan, som vi vet att vi är människor och vi kan se det. Vi vet att den högra delen kommer att vara där vi finner den, men datorn känner inte det, så vad vi ska göra är att vi kommer faktiskt ha det gå upp, och nu i början och slutet är samma plats, så mittpunkten blir den enda numret i listan på den punkten, som är 15, och vi har hittat den. Betyder det belysa var det hela max och min notation går, hålla reda på ändpunkterna i uppsättningen för att räkna ut hur man kan minska ner saker? Vad skulle hända om det inte var lika med 15 nu? Tänk om vi letade efter 15 och i stället var denna siffra också 16? Vi skulle säga "Åh, det är större. Vi vill gå tillbaka till vänster. " Och vi skulle flytta vår e till höger, då vi har en slutpunkt som skulle vara motstridiga. Det skulle inte kunna söka några fler element för nu har vi vår slutpunkt och vår startpunkt, vår max och vår min nu vänt. Vi söker igenom hela matrisen. Vi kan inte hitta något. Det är den punkt där vi skulle vilja säga: "Okej, vi kommer att stoppa denna algoritm. Vi har inte hittat något. Vi vet att det inte här. " Hur kommer detta? [Student] Hur exakt kan byta datorn slutet? Hur avslutar hamnar före början? Slutet hamnar före början på grund av den matematik som vi ska göra varje gång vi gör detta. Det sätt vi byter är om man tittar på den allra första gången vi gör det här swap där vi har början vid 4 och slutet hela vägen ned vid 108 och vår mittpunkt, säg, vid 16 - Jag ska återställa den tillbaka till 15-om vi letar efter 15, Vi visste att det vi gjorde när vi kontrollerat 16 och såg att det var större och ville kassera hela högra delen av listan, Vi såg att vad vi ville göra är att flytta denna e här. Effektivt, fick e flyttas till en före mittpunkten. Likaså när vi gjorde denna iteration av algoritmen och mittpunkten var 8, fann vi att 8 <15, så vi ville flytta b en förbi mittpunkten. Nu, i början och slutet är båda tillsammans i denna 15. Om vi ​​hade hänt för att leta efter något annat värde, inte 15, eller om denna 15 istället hade varit en 16, vi skulle ha funnit att e vi vill flytta en före mittpunkten. Nu e skulle vara där vänt lägre än miljarder. Låt oss gå igenom hur vi faktiskt hamna kodning denna algoritm. Vi vet att vi vill ha denna mittpunkt beräkning. Vi vet också att vi vill följa början och slutet av arrayen ur vårt nuvarande utbud så att vi kan räkna ut där denna vänstra halvan av listan är och var den högra halvan av listan är. Vi gör det med antingen börja och sluta, eller vi kan kalla dem min och max. Jag använder börjar och slutar denna gång. När vi börjar, om vi ser tillbaka på vårt exempel här nere, vår början sattes till början av arrayen, som naturligt. Vilken index var detta? Vad ska vi börja vara? Daniel. [Daniel] Haystack [0]. [Nate] Ja, så vi kunde ställa in den lika med höstack [0]. Problemet är dock att detta ger oss inte läget för den första elementet. Det ger oss index för första elementet eller det verkliga värdet på den första positionen. [Student] Det kommer att konvertera till 0,20? [Nate] Vad det kommer att göra är-bra kommer det inte att göra någon konvertering. Vad det kommer att göra är det att lagra en 4 i början, och då blir det svårt att göra jämförelser mot att börja eftersom Begin kommer att hålla värdet 4, vilket är början på vår array, men vi vill spåra indexen i matrisen i motsats till värdena. Vi kommer faktiskt använda en 0, så. Till slutet av arrayen-Charlotte tog upp lite tidigare. Det är där vi tar hänsyn till noll indexering. Charlotte, vad är slutet av arrayen? Vad är index till slutet? [Charlotte] Storlek - 1. Ja, och vilken storlek ska vi använda? Ska vi använda kapitalet storlek eller gemener storlek? Kapital storlek. I detta fall kan vi använda kapitalet storlek. Om vi ​​ville denna funktion för att vara portabel och använda den här funktionen i andra program, Vi kan faktiskt använda gemener storlek. Det är också bra. Men Charlotte är helt rätt att vi vill ha storlek - 1. Vid denna punkt- [Student] Hur kommer det sig att du kan använda versaler storlek? Hur kommer det sig att vi kunde använda versaler storlek? Det visar sig att dessa # definierar verkligen, under huven, en text som sök och ersätt, om det är vettigt. När du bygger din kod, förbehandlingen fasen av kompilatorn går igenom filen, och det ser för överallt att du har skrivit kapital storlek, och det ersätter det bokstavligen med en 8, precis så. I det avseendet är det mycket annorlunda från en variabel. Det tar inte upp någon plats i minnet. Det är en enkel text ersätta trick. I det här fallet kommer vi att använda storlek. Härifrån vi vill göra någon form av upprepning, och vi är på rätt väg med vår do-while-slinga. Vi vill göra något tills ett tillstånd håller inte längre, och som vi såg tidigare, såg vi att detta villkor var verkligen att vi inte vill att slutet att vara mindre än den börja. Detta är vår stoppa skick. Om detta inträffar vill vi stanna upp och förklara som, "Hej, vi har inte hittat något." För att uttrycka det, vi vill använda någon form av slingan. I det här fallet skulle det vara en gör-while-slinga, en for-slinga, en while-slinga? Vi har en gör-while-slinga här. Har ni såna tillvägagångssätt? Tror du att vi bör försöka en annan strategi? Kevin, några tankar? Vi skulle kunna ha en while-slinga eftersom vi vet maximal skulle vara större än min vid start ändå. Ja, så det finns ingen initiering som måste ske. De gör-while-slingor är bra när man måste initiera något innan dess testar, medan här Vi vet att vi inte kommer att hålla återinitialisera både börjar och slutar varje omgång av slingan. Vi vet att vi vill initiera dem, så kolla vår kondition. I det här fallet kommer jag faktiskt gå med en enkel while-slinga. Det visar sig att göra-while-slingor används ganska sällan. Många platser inte ens lär göra medan slingor. De är bra för att hantera användardata, så vi har sett en hel del av dem hittills. Men normalt för och medan slingor är mycket vanligare. Det visar sig att detta villkor som skrivits kommer inte riktigt att göra oss mycket bra, och varför är det? Jag är ledsen, jag vet inte ditt namn. Jag är Jerry. >> Ursäkta? Det är B-O-R-U-I. Åh, okej. Jag kan inte se dig på min lista. Åh, är det för att-OH, det är vettigt. Har du en idé om varför denna while-slinga kanske inte fungerar som avsett, som skrivs med villkoret? [Jerry] Du menar som du vill att alla grejer efter den i-? Ja, det är så att en. Vi kanske måste lägga allt det här i while-slingan, som är helt sant. Den andra saken som är lite mer problematiskt är dock att detta villkor inte fungerar. [Student] Du behöver vända den. Rätt, så detta villkor kommer aldrig att vara sant början hur vi pratade om det. Vi vill göra något till slutet > Plus börja? [Student] i slutet. Eftersom det är bara beräknat halv längd. Du måste lägga till börja. [Nate] Vad skulle detta räkna för oss? Om vi ​​tänker på slutet på denna första iteration av slingan, slut kommer att vara på plats index 7. Börja i läge 0. Kom ihåg, vi letar efter något läge 3 eller position 4. Om vi ​​tittar på den här matte, att bara göra det lite mer konkret, sätta några siffror här, vi har 7, 0, så från 7 till 0, och sedan / 2 är 3 i heltalsdivision, dvs. Då behöver vi sedan lägga tillbaka vår börja? Vi vill inte i detta fall. På den allra första iterationen kommer det att vara bra eftersom börja är 0. Men när vi framsteg gör vi egentligen alla bara behöver slut - börjar / 2. Det finns en annan trick här, och det är nämligen en av företräde. [Student] Behöver vi parentes? [Nate] Exakt, och det beror på om vi inte sätta dessa parenteser, då denna linje kommer att tolkas i stället som (slut) - (börjar / 2), som vi absolut inte vill ha. Se upp för dessa prioritetsregler regler. [Student] Varför inte avsluta det + börja? Varför är det inte slut + börja? [Student] Varför är det inte det? Varför skulle det vara +? Jag tror du har rätt. [Student] Därför att det är i genomsnitt? [Nate] Slut + börjar du helt rätt. Wow, goofed jag helt. Du har rätt. Om vi ​​gjorde på minus, skulle vi vilja lägga till att börja igen I det här fallet, är du väldigt rätt i att vi vill ta ett genomsnitt av de två, så vi vill lägga till dem, i motsats till subtrahera dem. [Student] Det skulle också fungera om du gjorde slut - börjar / 2 + börja. Det skulle om vi gör-Jag tror det. Till exempel, om vi tittar på början, och vi flyttas den hit till 15. Nu börjar är i position 2. End är i position 7. Om vi ​​subtraherar dem, får vi 5. Dividera det med 2, får vi 2. Och då lägger vi till 2 tillbaka, och som får oss att den 4: e positionen, vilket är just här, vilket är mittpunkten. [Student] Behöver vi ta hand om emballage? I vilken mening behöver vi ta hand om omslag? Om summan eller skillnaden mellan beroende på hur vi gör det inte är ett jämnt tal. Då datorn blir förvirrad om när det är 2,5; behöver du flytta till vänster eller till höger för att avgöra vilken som är mittpunkten? Fick det. Det visar sig att med heltalsdivision, vi inte någonsin få dessa flyttal. Vi får aldrig decimal. Det är helt kasseras. Om du har en dator dela två int variabler, och en är 7, och den andra är 2, du kommer inte få 3,5 som följd. Det kommer att bli 3. Resten kommer att kasseras, så det är faktiskt avrundning inte en runda utan ett golv, om ni känner till att det i matematik, där du slänger helt decimal, och så att du i huvudsak trunkering ner till närmaste Sammanlagt positioner, till närmaste heltal. [Student] Men så är det problematiskt eftersom om du har en uppsättning av 7 element då tar automatiskt den 3: e delen ur mittpunkten istället för 4th. Hur hanterar vi det? Det är problematiskt eftersom om vi hade en matris med 7, Det skulle plocka den 3: e istället för 4th. Kan du förklara lite mer? [Student] För om du har 7 element då den 4: e elementet skulle vara mittpunkten, eller hur? Kom ihåg din kommentar om att vara noll indexerade, dock. [Student] Ja, så i position 3. Det skulle vara mittpunkten. Ja. Åh, okej. Jag förstår vad du menar. Det är lite konstigt, eftersom vi vänjer hela denna föreställning om att bli av med decimaler. Det är en bra plats. Låt oss avsluta det här. Vi har beräknat vår mittpunkt. Vi testar för att se om vårt nål är lika med det mittersta värdet. Vi skriver att vi hittat det, men egentligen, vad vi vill göra i denna situation? Vi har hittat det, så vi vill låta den som ringer vet att vi hittat den. Vi har en funktion som är ett booleskt skrivit funktion. Hur vi signalerar till den som ringer på vår funktion som vi är redo att gå är vi säger, "Hej, det är sant." Hur skulle vi göra det, Kevin? Du nickar huvudet. >> [Kevin] Lägg tillbaka sant. [Nate] Exakt, return true. Nu, om det inte är lika, hur skulle vi se på den vänstra halvan? Några idéer? Stella, några idéer? Du måste ange en ny position för slutet. Ja. Så vi måste göra läge mittpunkt - slutet. Jättebra. Vi måste ställa en ny position för slutet att titta på den vänstra halvan. Det var vad vi pratade om innan där Jag hålla gå tillbaka till detta exempel. Jag har börja här och så har jag slut hela vägen hit. Återigen, om vi letar efter 15, och vår mittpunkt är 16, och vi inser, "Oj, är 16 större. Vi vill flytta till den vänstra halvan. " Vi skulle då flytta slut på 15, och vi gör det genom att ta en från mittpunkten och ställa in det som vår nya ände. Likaså om vi vill titta på den högra, hur skulle vi göra det? Har du en idé? [Student] Du anger bara att börja mittpunkten + 1. [Nate] Great. Och nu när det gäller att vi inte hittar något, blir det tas om hand för oss? Daniel, det som får tas om hand för oss? [Daniel] Nej [Nate] Om vi ​​gör det genom hela matrisen och vi inte hitta något, där skulle det tas om hand, eller ska vi ta hand om det? [Daniel] Den tag skick. [Nate] Ja, tiden skick, exakt. Det kommer att ta hand om att gå igenom hela arrayen om vi inte hittar något. Denna while-slinga kommer att sluta. Vi kommer aldrig stött på detta villkor, och vi kan returnera false. Vi kan också lämna detta om här så här för om detta om påståendet är sant, och vår funktion kommer tillbaka, och så vi i huvudsak avbryta denna funktion på denna punkt när vi kommer tillbaka sant. Men vad händer med denna struktur här? Kommer detta att fungera helt, eller finns det någon logisk brist i det? Det finns vissa logiska fel i det, med hur det inrättas. Vad kan det vara? [Student] Varför du behöver - och + 1s? Som sätter vår grupp för att vara vår nya vänstra och högra halvan. [Student] Men varför kunde du inte göra det utan - 1s och + 1s? [Nate] Vi kan ställa in den lika med mittpunkten? Vad kan vara problematiskt om det? [Student] Jag antar att det är ineffektivt eftersom du kollar ett värde som redan har kontrollerats. [Nate] Exakt, så Sam är helt rätt. Om du ställer in slutet och börjar lika mittpunkten istället för - 1 och + 1 eftertänksamt, någon gång i framtiden kommer vi att hamna kontrollera mittpunkten igen. [Student] Jag började pset, och sedan hade jag något liknande där jag glömde + 1, och det fastnade i en oändlig loop. Rätt, för någon gång att du aldrig kommer att få börja och sluta att faktiskt överlappar. Cool. Det finns en mer logisk brist, och det är att det definitivt bör vara en annan om. Varför kan det vara? Anledningen är om det inte är en annan om-såg du det, Kevin? [Kevin] Ja, eftersom du ändrar slutpunkten. [Nate] Exakt. Vi ändrar slutpunkten, och om den är skriven så här-Vi gör utrymmena mellan- Det kommer att kontrollera det här fallet. Detta fall, om den lyckas, avbryter ur funktion. Sedan kommer det att kontrollera detta nästa fall, och om det lyckas, kommer det att justera slutpunkt, och så kommer det att fortsätta på och kolla det här fallet. Men på denna punkt, vill vi inte att fortsätta att kontrollera. Lyckligtvis har återställt vi inte mittpunkten här, och vi vet att detta fall inte kommer att lyckas. Men vi vill absolut sätta else if där även om det kanske i det här fallet eftersom vi inte justerar mittpunkten, skulle det göra någon skillnad? Nej, eftersom dessa fall är alla exklusiva. Återigen, min dåliga. Vi inte, tror jag, behöver detta annars om. Vi kan ge det ett försök och köra den och se vad som händer. Byggnad, inträffade ett fel. Det är förmodligen därför jag lämnade dessa B och E: s här. Har jag några fler av dem upp på toppen? Det ser inte ut som det. Vi zoomar ut, bygga, där det går, så nu när vi söker efter 15, Ja. Låt mig zooma in 15, ja. Vi kan köra den igen. Uppladdning källkod, bygga, löpning. Vi kan söka efter något som 13, och vi får ingenting skrivs ut, så det är inte att hitta det för oss. Det är bra, för det är inte i vår lista. Vi är nu för sent. Det kommer att vara det för den här veckan. Tack för sammanfogning och ses senare. [CS50.TV]