[Powered by Google Translate] [Afsnit 3] [mindre behagelig] [Nate Hardison] [Harvard University] [Dette er CS50.] [CS50.TV] Okay, lad os komme i gang. Velkommen til uge 4 af CS50. Hvis du fyre åbner en webbrowser og åbne op Pset 3, Scramble med CS50, vil vi begynde at gå gennem den del af spørgsmål her. Ligesom sidste uge, vil vi arbejde i CS50 Spaces, hvis du også vil trække det op så godt, og hvis du gå videre og besøge dette link, som jeg har fået heroppe på toppen. Det er tid til at komme i gang. Vi har fået vores lille hi-program her. Intet crazy. En af de første ting, jeg vil gøre med jer i dag er at gå over et par løsninger til Problem Set 1, type eksempel løsninger, bare så du kan få en fornemmelse for, hvilke former for kode personale skriver, hvad slags kode andre studerende skriver, og har du tage et kig på det, fordi jeg ved, det er underligt når du sender en løsning på et problem sæt og få kommentarer på din egen version, nogle gange, men det er nyttigt at se, hvordan andre mennesker gjorde det, især dem, der er flot. For det meste, jeg var virkelig imponeret over de løsninger, som du fyre produceret. Jeg har endnu ikke begyndt at se på dit problem Set 2s, men hvis de er noget som den første, det betyder noget men gode ting. Hvis du ser på mine ændringer, lad os starte helt ned på revision 1, og vi kommer til at tage et hurtigt kig på en Mario løsning. Hvis du trækker denne op, disse programmer som vi kommer til at præsentere, er korrekte. Der var ikke rigtighed problemer med disse problemer, men snarere, vi ønsker at tale lidt om de forskellige design spørgsmål , som bruges her. En af de ting, der var interessant om løsningen er, at den har anvendt denne nye konstruktion kaldet pund definere, undertiden også betegnet som en hash definere. Lad mig zoome ind på det her. A # define giver dig mulighed for at give navne til disse numre i din program. I dette tilfælde, den maksimale højde af en pyramide i Mario blev 23 og snarere end at lægge 23 i min kode- vi vil gerne henvise til, at så hård kodning 23 - i stedet dette giver navnet MAX_HEIGHT til dette nummer, så at hernede i min do-while-løkke du kan faktisk henvise til MAX_HEIGHT i stedet for at sætte nummer 23 i. [Student] Hvad er fordelen ved at gøre det? Det er et godt spørgsmål. Den ene er læsbarheden. En fordel ved at bruge denne # define er læsbarheden. Når jeg læser denne kode, kan jeg se, hvad der foregår. Jeg kan se i denne tilstand her, at vi tester for højden er <0, hvilket vi også kunne have defineret at være en minimumhøjde eller en min højde. Den anden fordel er, at jeg derefter kan læse resten af ​​linien for at se at vi også er kontrol for at sikre, at højden ikke er større end max højde, fordi vi kommer til at fortsætte, mens højden er større end max højde. Den anden fordel er, hvis jeg zoome ud en lille smule her- hvis jeg køre dette program, og jeg kører den, sige, med 23 lige nu, det vil udskrive alle 23 rækker ligesom det. Men sige jeg ønskede at ændre maks. højde, og nu vil jeg gerne begrænse den maksimale højde af pyramider at være kun sige, mand, det var funky. # Include , # define MAX_HEIGHT, og lad os sige, vi ønskede at indstille det lig med 10. Nu på dette punkt, var alt jeg havde at gøre ændre det i denne ene sted. Jeg kan genkompilere koden, og nu hvis jeg prøver og skrive i 12, Det vil tilskynde mig igen. I dette tilfælde er vi kun bruger MAX_HEIGHT gang. Det er ikke det store af en besvær at gå i og ændre det i while-løkken, hvis du har brug for. Men i programmer, hvor du refererer til det samme magiske tal igen og igen, denne # define mekanisme er virkelig praktisk fordi du bare ændre det en gang i toppen af ​​filen, det er typisk, hvor du lægger dem- og ændringen siver ned gennem resten af ​​filen. Andre ting, jeg ønskede at bemærke i denne opgave, som jeg troede kiggede virkelig rart, den ene var navngivningen af ​​variablerne. Du kan se her, at vi har fået heltalsvariabler kaldet række og kaldte højde. Spaces, hashes, det hjælper at gøre koden lidt mere læselig, gør det lidt mere forståeligt, hvad der rent faktisk sker. Dette er i modsætning til anvendelse af fx tilfældige bogstaver eller blot volapyk helt. En sidste ting jeg vil påpege, er, at der i for-løkker, ofte disse iterator variabler, disse tællere, du bruger i din for sløjfer, Det er standard og konventionelt at starte dem med enten i og derefter j og derefter k og går videre derfra, hvis du har brug for flere variabler, og dette er blot en konvention. Der er masser af konventioner. Det afhænger af programmeringssprog, du bruger. Men i C, vi starter typisk med i. Det giver ikke mening at bruge, siger, a eller b afhængigt af situationen. Det er det for denne ene. Hvis du nu trække op Revision 2, vil du se en anden Mario, og dette svarer til den anden, som vi lige har set, men det gør noget lidt sejt. Hvis vi ser på denne sektion lige her inde i den indre for-løkke, de bruger nogle skøre søger syntaks her til højre på denne linie. Dette kaldes en ternær operatør. Det er en hvis ellers erklæring kondenseret til én linje. Betingelsen er denne del i parentes. Det er svarer til at sige, om j > Sam. Sam. Ligesom Sam sagde, at lineær søgeproces vil være virkelig langsom, og i stedet med binær søgning, er den måde, det fungerer som hver gang vi går igennem en iteration af vores søgning algoritme, vi kommer til at opdele listen i halve, det væsentlige, i to mindre lister. Og så på den næste iteration af løkken, vil vi dele det igen i andre mindre lister. Som du kan se, holder problemet bliver mindre og mindre fordi vi holder kassere halvdel af listen hver eneste gang. Hvordan virker dette skille arbejde? Ligesom en påmindelse, hvad vi vil gøre, hvis vi var en computer og vi var, siger, at søge efter nummer 5 i denne liste er, at vi ville vælge et nummer i midten. I midten af ​​denne liste, fordi der er 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 numre, vi ville vælge det ønskede nummer enten ved den 4. position eller på 5th position, og vi ville kalde det midt i vores liste. Pick nummer i midten. Så, ligesom Sam sagde, vil vi prøve at se, hvis dette antal er lig til det antal, som vi ønsker at få eller vores ønskede nummer. Hvis det er lige, så vi har fundet det. Vi vinder. Hvis det ikke er ens, så er der et par tilfælde. De to sager er enten antallet skal være større end antallet, vi kigger på, eller det er mindre end. Hvis det er større, vi flytter til højre. Og hvis det er mindre, vi flytter til venstre. Og så har vi gentage hele processen igen på enten den højre halvdel eller den venstre halvdel af listen. Det første problem i dagens afsnit er at finde ud af hvordan vi rent faktisk kan begynde at udtrykke dette i C-kode. Vi har pseudokoden her. Hvad vi vil begynde at gøre er jeg vil trække op en helt ny plads, gemme denne revision, så vi har disse notater til senere, vi vil slette alt dette, og derefter kopiere og indsætte fra problemet indstillede denne information ind i vores rum, og forhåbentlig ikke går i stykker. Perfekt. Hvis du fyre alle gør det, kopiere og indsætte denne kode til din nye rum, i en tom én. Lad os prøve Daniel. Hvis du kompilere og køre dette program, virker det? Nej >> Hvad er det siger? Det siger den kontrol når til slutningen af ​​ikke-void funktion. Ja, så lad mig prøve at køre det. Har du fyre set det før? Ved du hvad det betyder? Okay, lad os dissekere det en lille smule. Det siger i file.c on line 9, kolonne 1 vi har en fejl, ligesom du sagde, og det siger, at det er som følge af fejlen advarsel og returtypen advarsel. Det ligner noget, der foregår med afkastet type, som giver mening. Vi har en non-void funktion, hvilket betyder, at vi har en funktion der ikke vender tilbage ugyldige. En void funktion er en, der ser sådan ud: void foo (), og det er ugyldig, fordi afkastet type er ugyldig, hvilket betyder, at hvis vi havde noget herinde ligesom tilbagevenden 1, ville vi få en compiler fejl for dette. Men vi har en ikke-void funktion. Vores non-void funktion i dette tilfælde er vores søgefunktion fordi den har en tilbagevenden type bool. Når det sige, at kontrollen når enden af ​​en ikke-void funktion, det er fordi søgning ikke har en return-sætning. Det er ikke returnere noget af typen bool. Vi kan ordne det, og hvad tror du fyre tror søgning bør vende tilbage som standard? Hvad skal være standard returværdien af ​​søgning? Fordi det er, hvad vi kan lægge i slutningen. Charlotte, har du nogen-? Sandt eller falsk? >> Sandt eller falsk. Hvilken en? Falsk. Det ved jeg ikke. False? Lad os prøve det. Hvorfor ville du sige return false? Det er godt intuition. [Charlotte] Jeg ved det ikke. Vi vil returnere falsk i dette tilfælde, fordi dette vil være vores standard hvis en eller anden grund listen er tom, eller nålen at vi leder efter findes ikke. Så til allersidst, hvis vi ikke returnere sandt tidligere i denne funktion, vi altid ved, at denne funktion vil sige nope, det er ikke i array. Det er ikke i høstakken. Nu, hvis vi kompilere og køre det, lad mig spare dette, så vi kan trække det op. Nu, hvis vi kompilere og køre vores program, det bygger. Vi får vores lille prompt. Hvis jeg ramte 4-uh-oh. Det gik ikke udskrive noget. Det ligner alt endte okay. Vi har fået at udfylde dette i. Vi talte om algoritmen i pseudokode lidt siden. Lad mig se, gemme dette, og jeg vil trække denne algoritme op igen. Lad os slå denne fyr. Nope. Der er det. Hvordan gør vi det? Hvad ville være en god strategi til at starte off denne kode? Du er nødt til at vælge et nummer i midten. Hvordan vi vælger et nummer midt i et array? Nogen forslag? [Student] strlen divideret med 2. Strlen divideret med 2. Det er en stor en. Strlen arbejder med særlige typer af arrays. Hvilke typer af arrays? String arrays, tegndatatabeller. Det er den samme slags koncept, som vi vil anvende, men vi kan ikke bruge strlen fordi vi ikke har en vifte af tegn. Vi har en bred vifte af int'er. Men hvad betyder strlen får for os? Ved du, hvad det får for os? [Student] strlen får os længden. Præcis, det får os længden. Strlen får længden af ​​array for os. Hvordan får vi det i vores binær søgning program? Hvordan ville du få længden af ​​et array? [Student] strlen? Du kan få længden af ​​en korrekt formateret C string array med strlen. Problemet er imidlertid, at vi ikke har en streng array. Hvis vi ser tilbage på denne kode, vi har denne integer array. Hvordan kan vi vide, hvor længe det er? [Student] Er der en tilsvarende én for endpoint, ligesom int l eller noget? Det viser sig, at der faktisk ikke er, og så på en måde, dette er en af ​​de ting, der er bare godt at vide om C, at der ikke er nogen måde at få længden af ​​et array hvis alt jeg give dig, er det array. Grunden til at det virker med strygere, årsagen strlen værker, er fordi, hvis en streng er formateret korrekt, det vil have, at særlige \ 0 tegn til allersidst. Du kan også forestille mig, hvis du har en forkert formateret streng og der er ingen \ 0 tegn der, så det hele ikke virker. [Student] Kan du tilføje \ 0? Vi kunne i dette tilfælde. Vi kunne tilføje nogle slags \ 0 eller anden form for tilkendegiver karakter og derefter bruge det. Men det er ikke helt kommer til at arbejde fordi \ 0 er for en char type, og her har vi int'er. Den anden ting er, hvis vi skulle bruge en speciel værdi ligesom -1 for at markere afslutningen på et array så kunne vi aldrig gemme en -1 i vores heltal arrays. Vi ville blive hængende. Det viser sig, at den eneste måde at få længden af et array i C er rent faktisk at huske det når du sætter den op, og derefter sende det rundt med array så at når jeg har en funktion, der kommer til at gøre noget arbejde på en bred vifte af heltal eller decimaltal eller fordobler eller hvad har du, Jeg er også nødt til at give den funktion array længde, og det er præcis, hvad vi har gjort her i søgefunktionen. Hvis du ser, hvad vi har gjort, når vi passerer i vores array her, vi også passere i længden, størrelsen. Det sker bare, at vi har kaldt denne variabel her, denne parameter eller argument. Dette kaldes en funktions argument liste eller parameterliste, og disse kaldes også argumenter eller parametre. Folk bruger forskellige udtryk på forskellige tidspunkter. Jeg har nogle gange interchange dem selv. Det bare så sker det, at denne variabel her er opkaldt lignende til dette # define op her. Men de er ikke de samme ting. Kapitaliseringen ligegyldigt. Hvis man ser på, hvad der sker her, vi erklærer vores int array, som vi har kaldt numre. Vi har givet det vores størrelse, der svarer til vores # definere op øverst. Det kommer til at være 8. Og så når vi så kalde vores søgefunktion dernede, passerer vi i det antal vi vil søge efter, og som vi har bedt om det, fået fra brugeren. Vi passerer i array, dette tal, og så har vi også nødt til at passere i størrelsen af ​​array, og så værdien af ​​størrelse 8 bliver gemt eller videregives til denne heltalsvariabel kaldet størrelse. Vi har størrelsen af ​​arrayet. Nu, hvis vi går tilbage til det, vi talte om tidligere, Jeg tror Missy opdraget det punkt, hvad vi skulle gøre, er at få længden af ​​array og dividere det med 2, og det vil give os midtpunktet. Lad os se. Kan jeg få nogen skriver dette, og gemme det i deres plads? Hvad med Leila? Kan jeg få dig skrive det i? Skriv den første linje, hvor du tager længden af ​​array og få midtpunktet og gemme det i en ny variabel. Jeg vil give dig et par sekunder. Er du klar? [Student lydløs] Sure, kunne jeg have dig med at beregne midtpunktet af høstakken arrayet inde i søgefunktionen ved hjælp af længden af ​​høstak matrix, som er den størrelse variabel? Intet tricky her. [Leila] Just størrelse / 2 og just- Og gemme den, og ramte knappen Gem heroppe på toppen, og vi vil trække det op. Perfekt. Der vi går. Awesome. Som det vil dette kompilere? [Leila] Nej, det skal være højere. [Nate] Yeah, så hvad skal vi gøre? [Leila] Ligesom int midtpunkt eller noget. Awesome. Ja, lad os gøre det, int midtpunkt = størrelse. Vil dette kompilere? Lad os slette denne kommentar og få det ud af vejen. Hvad vil ikke kompilere om dette? Vi laver ikke noget med heltal, så vi er nødt til at udskrive det eller noget lignende. Ja, præcis. Vi får en ubrugt variabel. Hvad andet er ikke til at arbejde her? Jeg tror, ​​du sagde noget, Sam. Semikoloner. Ja, jeg mangler disse semikoloner. Det kommer til at være en konstant ting under hele udtrykket. Den sidste ting, jeg vil gøre, er at jeg vil sætte nogle hvide plads på hver side af denne operatør her, da det er typisk hvordan vi gør det ifølge vores styleguide. Vi har midtpunktet af vores array. Nu, hvis vi husker tilbage til vores algoritme, hvad var det andet trin, at vi måtte gøre, når vi har midtpunktet? [Student] Hvis det er større [uhørlig]. Ja, så vi er nødt til at gøre en form for sammenligning, og hvad skal vi sammenligner her? Du sagde, at hvis det er større end. Hvad er det i denne sætning hentyder til? Det nummer, der kommer op, hvis det er større end midtpunktet og derefter gå op til array? Præcis, så antallet, der kommer op, når vi- Nålen, så vi sammenligne med nålen, og hvad skal vi sammenligne mod nålen? Fordi nålen er, hvad vi leder efter. Vi sammenligner det at komme til midtpunktet. Men giver det mening at kontrollere, hvis p = midtpunkt? Giver det mening? Er der nogen er uenige? Lad os give det en chance, hvis (nål == midtpunktet). [Student] Må printf du fandt den. [Nate] printf ("Vi fandt det \ n"); Ellers-Jeg kommer til at begynde at gøre noget anderledes her. Jeg har tænkt mig at begynde at sætte seler rundt, hvis udsagn hele tiden bare fordi hvis vi tilføje flere ting, så vi får ikke de compilere. Ja, Sam. Du har en pointe. Problemet er, at midtpunktet repræsenterer en position i arrayet, men du kan få det til at repræsentere den værdi i den position af array. Det er en stor punkt. Har alle høre, hvad Sam sagde? Han sagde, at midtpunktet som er udgør blot en position i array, men det er ikke den faktiske element i array. Hvis du tænker over koden som skrevet lige nu, hvis vi ser på dette array hernede, der har 8 elementer i det, Hvad er værdien af ​​midtpunktet vil være i denne funktion? [Student] 4. [Nate] 4. Hvis vi ser for antallet 4 - og vi kan bare køre denne kode og sætte lidt trist ansigt i her fordi vi ikke finde det, hvis vi køre denne kode som er lige nu, uploade det, bygning, lad mig rulle ned, og hvis vi ser for tallet 4, vi fandt det, men vi fik ikke dette til printf ja. En af grundene er, at vi ikke vendte tilbage sandt, men vi virkelig finde nummeret 4? Og Sam siger nej. Hvad har vi? Vi virkelig fundet midtpunktet, som hvis vi ser på arrayet hernede, det vil være det element ved indeks 4, at vi kigger på, der er 23. Hvordan får vi rent faktisk får det element ved midtpunktet og ikke bare midtpunktet selv? [Student] Vi ville træde char eller noget? Hvad ville det gøre, lige ud af nysgerrighed? Kan du uddybe lidt mere? Du er nødt til at omdanne position i nummeret, så du bliver nødt til at lave en forbindelse, jeg synes det er char, men det kan ikke være. Ja, det er en god pointe. Vi har gjort en masse af denne konvertering positioner i chars, disse tegn, i de første to problemområder sæt. Det viser sig, at her, det er næsten identisk med adgang til i'te tegn i en streng, hvis det giver mening. Her ønsker vi at få adgang til midtpunktet element. Hvordan gør vi det? Kevin, har du nogen forslag til, hvordan vi kan gøre det? Du kan gøre høstak, åben beslag, mid, lukket beslag. Kan du skrive det for os? Gem det i her, og vi vil trække det op. Vi ser på denne linje 9, og vi indse, at vi ikke ønsker at sammenligne nålen til midtpunktet, men i stedet ønsker vi at sammenligne nålen til elementet i position midtpunkt i vores høstak array. Cool. Der vi går. Ja, der ser temmelig godt, hvis (nål == høstak [midtpunkt]). Vi fandt det. Nu, hvis vi køre koden-vi tilbage op en lille smule, det kompilerer, det kører, og nu, hvis vi ser for 4, vi ikke finde det, fordi nu er vi rent faktisk får nummeret 23. Vi får værdien 23, og det er hvad vi sammenligne med vores nål. Men det er godt. Det er et skridt i den rigtige retning. Det er det, vi forsøger at gøre. Vi prøver ikke at sammenligne nålen mod positioner i array men snarere mod de faktiske elementer i arrayet. Hvis vi ser tilbage nu igen på det næste trin i vores algoritme, hvad er det næste skridt? Leila allerede nævnt det kort. [Student] Kontroller at se, om den er større eller mindre end, og derefter beslutte, hvilken måde at flytte. [Nate] Ja, det ville så hvordan gør vi det? Kan du sætte nogle-Jeg gemme denne revision, og derefter, hvis du lægger i nogle linier, der vil gøre det. Ja, Charlotte. >> Jeg har et spørgsmål. Skulle det ikke være midtpunktet - 1, fordi den første ting er det er 0 indekseret, så hvis vi sætter 4, det er faktisk ikke det tegn, vi leder efter? Ja, og det andet problem med at er- det er en stor fangst, fordi det kommer til at ende op sker muligvis hvis vi at bevæge os, og vi ikke nogensinde justere første omgang? Jeg gætte, hvad vi kan ende med at gøre forsøger at få adgang til elementet på 8. position af arrayet, som i dette tilfælde findes ikke. Vi ønsker at gøre en slags tegner sig for den kendsgerning at vi har nogle nul indeksering. [Charlotte] Undskyld, jeg mente midtpunkt - 1 i de firkantede parenteser. Vi kan gøre det. Vi vil vende tilbage til dette spørgsmål i bare en smule. Når vi begynder at komme til den faktiske looping, det er når vi virkelig se dette kommer i spil. I øjeblikket kan vi gøre det, men du er helt rigtigt. At nul indeksering vil have en effekt, at vi er nødt til at redegøre for. Lad os se. Hvordan er større end og mindre end-? [Student] Jeg får hvordan man gør det større end og mindre end en del. Jeg var bare ikke sikker på, hvad der skal udskrives, hvis du synes, at det er mindre end høstakken midtpunktet eller større end. Her kan jeg spare, hvad Det har jeg- [Nate] Yeah, hvis du gemmer hvad du har fået, og vi vil trække det op. Der vi går. [Student] Og jeg sætter spørgsmålstegn til hvad jeg ikke vidste. [Nate] Det ser flot ud. Her har vi spørgsmålstegn, fordi vi stadig ikke kender hvad vi vil helt gøre endnu. Hvad ville vi ønsker at gøre-oops, så har vi nogle seler alle funky på os. Vi vil rette op på disse seler. Der vi går. Og så hvad gør vi ønsker at gøre, ifølge vores algoritme, hvis vi ikke finde nålen? Sig i det tilfælde, at nålen er mindre end hvad vi ser på. Kevin. Kun se på den venstre halvdel. Right, så vi vil sætte en kommentar ind her, der siger "se på venstre halvdel." Og hvis nålen er større end høstak ved midtpunktet, hvad vi ønsker at gøre? [Student] Så man ser på den højre halvdel. Kig på den højre halvdel, "se på højre halvdel." Ikke for lurvet. Okay, så på dette punkt, er tingene ser temmelig godt. Problemet med koden som skrevet er hvad? [Student] Du har ikke endpoints for halvdele. Højre, har vi ikke endpoints for halvdele. Vi har også kun kommer til at gå igennem denne gang. Vi kun kommer til at se på en midtpunktet. Enten elementet er der, eller det er ikke. For at gennemføre dette, vil vi nødt til at gøre en form for gentagelse. Vi er nødt til at gentage, indtil vi finder, at enten elementet er derinde, fordi vi har indsnævret og endelig fundet det, eller det er ikke der, fordi vi har set gennem alle de ting i de relevante halvdele af arrayet og fandt, at der intet er derinde. Når vi har fået denne gentagelse foregår, hvad vi skal bruge? [Student] A loop. Nogle slags løkke. Ja. [Student] Kan vi gøre en gør-while-løkke og har det gør det, og derefter, mens nålen er ikke lig-Jeg er ikke sikker på, hvor jeg skulle med. Men lidt ligesom at gøre det, så længe det ikke er lig den værdi, som brugeren input. Ja, så lad os se, hvordan kan denne skrive sig selv? Du sagde lad os bruge et do-while-løkke. Hvor kommer do start? [Student] Lige efter størrelse / 2. [Nate] Okay, og hvad skal vi gøre? Vi udfylde tid senere. Hvad skal vi gøre? [Student] Må ikke vi ønsker at gøre alle de ting vi har i hvis portion? [Nate] Gør alle disse ting, stor. Kopier og indsæt. Åh, mand. Lad os se om det virker, hvis vi kan fane dette over. Smuk. Okay, og vi sparer dette, så du fyre har det. Okay, og vi vil gøre dette, mens- hvad var det så længe betingelse du var ude efter? [Student] Mens nålen ikke lige, så ligesom det udråbstegn. Men jeg er ikke sikker på præcis, hvad det er endnu. [Nate] Ja, det er en måde at gøre det på. Sam, har du en kommentar? [Sam] Jeg huskede, da jeg kiggede på de videoer, Jeg tog et screenshot af en af-lignende da vi gjorde pseudokoden for det, Der var en vis forbindelse mellem max og min. Jeg tror, ​​det var noget som hvis max er stadig mindre end min. Fik det. [Sam] Eller gerne, hvis max ikke er mindre end min eller sådan noget, fordi det ville betyde, at du har søgt alt. Ja, så hvad betyder det lyde som max og min henviste til? [Sam] Værdier, som-heltal, der vil ændre i forhold til hvor vi sætter midtpunktet. Præcis. [Sam] På det tidspunkt, går det til [uhørlig] beregne max og min. Midtpunkt er denne max og min idé. Giver det mening at folk? Hvis vi skulle begynde at kigge på, hvordan vi vil gøre det iteration, du er helt rigtigt, at vi ønsker at bruge en form for do-while-løkke. Men jeg gætte, hvis vi husker, hvad der foregår på stedet af dette array og hvad der rent faktisk sker-Jeg kommer til at skrive herovre- i det første iteration af binær søgning, har-vi Jeg har tænkt mig at bruge b og e til at betegne begyndelsen. Og så i slutningen af ​​vores array. Vi ved, at starten er på 4 lige over her, og vi ved, at enden er på 108. Siger, at vi leder efter nummeret 15. Første gang vi gør det, som vi så tidligere, midtpunktet er enten kommer til at være 16 eller 23 afhængigt af, hvordan vi beregner tingene ud. Siden jævnt dividere i midten ville give os denne plads mellem 16 og 23, kan vi ikke jævnt opdele det eller dele den og få fat i en ægte midtpunkt. Vi vil se på 16. Vi vil realisere "Hey, 16> 15, som vi leder efter." At derefter se på den venstre halvdel af grupperingen hvad vi vil ende med at gøre, er genudsætning hele denne øvre del og siger: "Okay, nu er vores endpoint vil være her." Den næste iteration af vores loop, vi nu kigger på dette array, effektivt at have fjernet denne del, fordi nu hvis vi tager midtpunktet at være forskellen mellem begyndelsen og enden, Vi finder vores midtpunkt at være 8, som vi kan derefter teste 8 for at se, hvor det er i forhold til det antal vi leder efter, 15, finder, at 15 er større, så vi er nødt til at flytte til den højre del af listen, som vi kender, fordi vi er mennesker, og vi kan se det. Vi ved, at den højre del vil være der, hvor vi finder det, men computeren ikke ved det, så hvad vi vil gøre, er at vi vil faktisk har dette gå op, og nu begyndelsen og enden er det samme sted, så midtpunktet bliver den eneste nummer på listen på det tidspunkt, som er 15, og vi har fundet det. Betyder det kaste lys over, hvor det hele max og min notation går, holde styr på de endepunkter af arrayet for at finde ud af hvordan man kan indsnævre tingene ned? Hvad ville der ske, hvis det ikke var lig med 15 nu? Hvad hvis vi ledte efter 15 og i stedet dette nummer var også 16? Vi ville sige: "Åh, det er større. Vi ønsker at gå tilbage til venstre. " Og vi ville flytte vores e til højre, på hvilket tidspunkt har vi et endepunkt, der ville være modstridende. Det ville ikke være i stand til at søge efter alle flere elementer fordi vi nu har vores endpoint og vores startpunkt, vores max og vor min, er nu vendt. Vi gennemsøge hele array. Vi kan ikke finde noget. Det er det punkt, hvor vi gerne vil sige, "Okay, vi kommer til at stoppe denne algoritme. Vi har ikke fundet noget. Vi ved, det er ikke her. " Hvordan skal det hen? [Student] Hvor præcis er computeren skifte ende? Hvordan ende ender inden begyndelsen? Enden ender inden begyndelsen på grund af den matematik, vi vil gøre hver gang vi gør det. Den måde, vi bytte er, hvis man ser på den allerførste gang vi gør dette swap hvor vi har begyndelsen på 4 og slutningen hele vejen ned ved 108 og vores midtpunktet, dvs, ved 16 - Jeg har tænkt mig at nulstille dette tilbage til 15-hvis vi leder efter den 15, vi vidste, at det, vi gjorde, da vi tjekkede 16 og så, at det var større og ønskede at skille sig af med hele den højre del af listen, så vi, at hvad vi ønskede at gøre, er at flytte denne e lige her. Effektivt, fik e flyttet til en før midtpunktet. Ligeledes når vi gjorde denne iteration af algoritmen og midtpunktet var 8, fandt vi, at 8 <15, så vi ønskede at flytte b en forbi midten. Nu, begyndelsen og enden er begge sammen på denne 15. Hvis vi havde været tilfældet at kigge efter en anden værdi, ikke 15, eller hvis denne 15 i stedet havde været 16, vi ville have fundet, at e vi ønsker at flytte en før midtpunktet. Nu e ville være der vendt mindre end b. Lad os gennemgå, hvordan vi rent faktisk ender kodning denne algoritme. Vi ved, at vi ønsker at have denne midtpunktet beregning. Vi ved også, at vi ønsker at spore begyndelsen og slutningen af ​​array af vores nuværende opstilling, så vi kan finde ud af hvor denne venstre halvdel af listen er, og hvor den højre halvdel af listen er. Det gør vi med enten begynder og slutter, eller vi kan kalde dem min og max. Jeg vil bruge begynder og ender denne gang. Når vi begynder, hvis vi ser tilbage på vores eksempel hernede, vores start var sat til begyndelsen af ​​array, som naturlige. Hvilken indeks var det? Hvad skal vores begynde være? Daniel. [Daniel] Haystack [0]. [Nate] Yeah, så vi kunne sætte det lig med høstak [0]. Problemet er dog, at dette giver os ikke positionen af ​​det første element. Det giver os indekset for det første element eller den faktiske værdi i den første position. [Student] Det vil konvertere til 0,20? [Nate] Hvad dette vil gøre, er-godt, vil det ikke gøre nogen konverteringen. Hvad det vil gøre, er at det vil gemme en 4 i begynder, og så vil det være svært at foretage sammenligninger mod begynde fordi begin vil holde værdi på 4, som er begyndelsen på vores array, men vi ønsker at spore de indeks i array i modsætning til værdierne. Vi vil faktisk bruge et 0, som. For enden af ​​array-Charlotte bragt dette op lidt tidligere. Det er her, vi vil tage hensyn til nul indeksering. Charlotte, hvad er slutningen af ​​array? Hvad er indekset enden? [Charlotte] Størrelse - 1. Ja, og hvilken størrelse skal vi bruge? Skal vi bruge kapital størrelse eller små bogstaver størrelse? Capital størrelse. I dette tilfælde kunne vi bruge kapital størrelse. Hvis vi ønskede denne funktion til at være bærbar og bruge denne funktion i andre programmer, vi rent faktisk kan bruge små bogstaver størrelse. Det er også fint. Men Charlotte er helt rigtigt, at vi gerne vil have størrelse - 1. På dette punkt- [Student] Hvordan er det at du kan bruge store bogstaver størrelse? Hvordan er det at vi kunne bruge store bogstaver størrelse? Det viser sig, at disse # definerer er virkelig, under kølerhjelmen, finde en tekst som og erstatte, hvis det giver mening. Når du kompilerer din kode, forbehandling fase af compileren går gennem filen, og det ser for overalt, at du har skrevet kapital størrelse, og det erstatter det ordret med en 8, ligesom det. I den forstand er det meget forskelligt fra en variabel. Det tager ikke nogen plads i hukommelsen. Det er en simpel tekst erstatte trick. I dette tilfælde vil vi bruge størrelse. Herfra vi ønsker at gøre en form for gentagelse, og vi er på rette spor med vores do-while-løkke. Vi ønsker at gøre noget, indtil en betingelse ikke holder længere, og som vi så tidligere, så vi, at denne betingelse var faktisk, at vi ikke ønsker enden at være mindre end begyndelsen. Det er vores standsning tilstand. Hvis dette sker, vil vi stoppe op og erklære lignende, "Hey, har vi ikke fundet noget." For at udtrykke dette, ønsker vi at bruge en form for løkke. I dette tilfælde ville det være en do-while-løkke, en for-løkke, en while-løkke? Vi har en do-while-løkke her. Har du fyre som denne fremgangsmåde? Tror du vi skal prøve en anden tilgang? Kevin, nogen tanker? Vi kunne have en while-løkke, fordi vi ved maksimal ville være større end min ved start anyways. Ja, så der er ingen initialisering, der skal ske. Disse gør-while-løkker er stor, når du er nødt til at initialisere noget , før derefter teste, mens her vi ved, at vi ikke kommer til at holde Reinitialisering både begynder og slutter hver runde af løkken. Vi ved, at vi ønsker at initialisere dem, så tjek vores tilstand. I dette tilfælde vil jeg faktisk gå med en simpel while-løkke. Det viser sig, at do-while-løkker bruges forholdsvis sjældent. En masse steder ikke engang underviser ikke mens sløjfer. De er gode til håndtering af bruger input, så vi har set en masse af dem hidtil. Men normalt for og while-løkker er en masse mere almindelige. Det viser sig, at denne betingelse som skrevet vil ikke rigtig gøre os meget godt, og hvorfor så det? Jeg er ked af, jeg ikke kender dit navn. Jeg er Jerry. >> Undskyld? Det er B-O-R-U-I. Oh, okay. Jeg kan ikke se dig på min liste. Åh, det er fordi, oh, det giver mening. Har du en idé om, hvorfor dette while-løkke fungerer muligvis ikke efter hensigten, som skrevet med den betingelse? [Jerry] Du mener ligesom du vil have alle de ting efter den ind i-? Ja, så det er en. Vi skal måske lægge alle disse ting ind i while-løkken, som er helt sandt. Den anden ting, der er lidt mere problematisk, er dog, at denne betingelse ikke virker. [Student] Du er nødt til at vende det. Right, så denne betingelse vil aldrig være sandt oprindeligt den måde, vi talte om det. Vi ønsker at gøre noget indtil udgangen > Plus begynde? [Student] Ved udgangen. Fordi det kun er beregnet halvdelen af ​​længden. Du er nødt til at tilføje begynde. [Nate] Hvad ville dette beregne for os? Hvis vi tænker over ende på dette allerførste iteration af løkken, ende vil være i position indeks 7. Begynd er i 0-stilling. Husk, vi leder efter enten position 3 eller 4-stillingen. Hvis vi ser på denne matematik, for bare at gøre det lidt mere håndgribeligt, sætte nogle numre her, har vi 7, 0, SO 7 - 0, og derefter / 2 er 3 i heltalsdivision, der er. Så skal vi derefter tilføje tilbage vores begynde? Det gør vi ikke i dette tilfælde. På den allerførste iteration, vil det være fint, fordi begin er 0. Men da vi fremskridt, har vi virkelig alle bare brug ende - begynder / 2. Der er en anden trick her, og det er nemlig en af ​​forrang. [Student] Har vi brug for parenteser? [Nate] Præcis, og det er fordi hvis vi ikke sætte disse parenteser, så denne linje vil blive fortolket i stedet som (slut) - (begynder / 2), som vi absolut ikke ønsker. Watch out for disse forrangsbestemmelserne. [Student] Hvorfor er det ikke ender + begynde? Hvorfor er det ikke ender + begynde? [Student] Hvorfor er det ikke det? Hvorfor ville det være +? Jeg tror, ​​du har ret. [Student] Fordi det er gennemsnittet? [Nate] End + begynde, du er helt rigtigt. Wow, jeg er helt goofed. Du har ret. Hvis vi gjorde det minus, ville vi vil tilføje begynde igen I dette tilfælde er du meget ret i, at vi ønsker at tage gennemsnittet af de to, så vi ønsker at tilføje dem, i modsætning til trække dem. [Student] Det ville også virke, hvis du gjorde ende - begynder / 2 + begynde. Det ville gøre, hvis vi gør-jeg tror det. For eksempel, hvis vi ledte på begynde og vi flyttet det over her til 15. Nu begynder er i position 2. End er i position 7. Hvis vi trækker dem, vi får 5. Divider at ved 2, vi får 2. Og så tilføjer vi 2 tilbage i, og der får os til den 4. plads, der er lige her, som er midtpunktet. [Student] Har vi brug for at tage sig af indpakning? I hvilken forstand har vi brug for at tage sig af indpakning? Hvis summen eller forskellen mellem afhængigt af, hvordan vi gør det, er ikke et lige tal. Så computeren bliver forvirret, om når det er 2,5; vil du flytte til venstre eller til højre for at afgøre, hvilket er midtpunktet? Fik det. Det viser sig, at med heltalsdivisioner, vi ikke nogensinde få disse kommatal. Vi har aldrig få decimal. Det er helt bortkastet. Hvis du har en computer dividere to int variabler, og man er 7, og den anden er 2, du vil ikke få 3,5 som følge heraf. Det vil få 3. Resten vil blive kasseret, så det er effektivt afrunding ikke en runde, men snarere et gulv, hvis du fyre kender det i matematik, hvor du helt kassere decimal, og så du hovedsageligt beskærer det ned til nærmeste Hele position, til det nærmeste hele tal. [Student] Men så er det problematisk, fordi hvis du har en vifte af 7 elementer så der automatisk tager 3. element ud af midtpunktet i stedet for den 4.. Hvordan håndterer vi det? Det er problematisk, fordi hvis vi havde en vifte af 7, Det ville vælge den 3. i stedet for 4.. Kan du forklare lidt mere? [Student] Fordi hvis du har 7 elementer så det 4. element ville være midtpunktet, right? Husk din kommentar om at være nul indekseret, selvom. [Student] Yeah, så i 3-stillingen. Det ville være midtpunktet. Yeah. Oh, okay. Jeg kan se hvad du mener. Det er lidt underligt, da vi vænner os til hele denne forestilling om at komme af decimaler. Det er en stor punkt. Lad os afslutte dette op. Vi har beregnet vores midtpunkt. Vi tester, om vores nålen er lig med middelværdien. Vi udskriver, at vi fandt det, men virkelig, hvad vi ønsker at gøre i denne situation? Vi har fundet det, så vi ønsker at lade den, der ringer vide, at vi fandt det. Vi har en funktion, der er en boolean maskinskrevet funktion. Den måde, vi signalere til den, der ringer på vores funktion, at vi er klar til at gå er vi siger, "Hey, det er sandt." Hvordan ville vi gøre det, Kevin? Du nikker hovedet. >> [Kevin] Tilføj afkast sandt. [Nate] Præcis, returnere sandt. Nu, hvis det ikke er lige, hvordan ville vi se på den venstre halvdel? Nogen ideer? Stella, nogen ideer? Du skal angive en ny position for enden. Yeah. Så vi er nødt til at gøre placeringen af ​​midtpunktet - enden. Great. Vi er nødt til at indstille en ny position for enden at se på den venstre halvdel. Det var, hvad vi talte om før, hvor Jeg holde gå tilbage til dette eksempel. Jeg har den begynde her, og så har jeg enden hele vejen herover. Igen, hvis vi leder efter 15, og vores midtpunkt er på 16, og vi er klar over, "Ups, 16 er større. Vi ønsker at flytte til den venstre halvdel. " Vi ville derefter flytte ende til 15, og vi gør det ved at tage en væk fra midtpunktet og indstilling, der som ny ende. Ligeledes, hvis vi ønsker at se på den højre halvdel, hvordan ville vi gøre det? Har du en idé? [Student] Du skal bare indstille begynde at Midtpunkt + 1. [Nate] Great. Og nu i tilfælde af, at vi ikke finder noget, betyder det får taget sig af for os? Daniel, betyder det får taget sig af for os? [Daniel] Nej. [Nate] Hvis vi gør det gennem hele systemet, og vi ikke kan finde noget, hvor ville det blive taget sig af, eller skal vi tage os af det? [Daniel] The længe betingelse. [Nate] Yeah, imens tilstand, præcis. Det vil tage sig af at gå gennem hele systemet, hvis vi ikke finder noget. Denne while-løkke vil ende. Vi vil aldrig har mødt denne betingelse, og vi kan returnere falsk. Vi kan også lade dette hvis i sådan her fordi hvis dette, hvis udsagn er sandt, og vores funktion vil vende tilbage, og så vil vi hovedsageligt afbryde denne funktion på dette punkt når vi vender tilbage sandt. Men hvad sker der med denne struktur her? Vil dette arbejde helt, eller er der nogle logiske fejl derinde? Der er nogle logiske fejl derinde, med den måde det er sat op. Hvad kan det være? [Student] Hvorfor har du brug for - og + 1s? Det sætter vores array op til at være vores nye venstre halvdel og højre halvdel. [Student] Men hvorfor kunne du ikke gøre det uden - 1s og + 1s? [Nate] Vi kunne sætte det lig med midtpunktet? Hvad kan være problematisk ved det? [Student] Jeg tror det er ineffektiv, fordi du tjekker en værdi, der allerede er blevet kontrolleret. [Nate] Præcis, så Sam er helt rigtigt. Hvis du indstiller ende og begynde lig midtpunktet i stedet for - 1 og + 1 refleksivt, på et tidspunkt i fremtiden vil vi ende med at kontrollere midtpunktet igen. [Student] Jeg startede Pset, og så havde jeg noget lignende hvor jeg glemte + 1, og det fik stukket i en uendelig løkke. Ret, fordi på et tidspunkt, du aldrig kommer til at få begynder og slutter til faktisk overlappe. Cool. Der er en mere logisk fejl, og det er, at dette absolut bør være en else if. Hvad kan det skyldes? Årsagen er, hvis det ikke er en ellers hvis-har du se det, Kevin? [Kevin] Ja, fordi du ændrer slutpunktet. [Nate] Præcis. Vi er ved at ændre endpoint, og hvis det er skrevet på denne måde-vi gøre mellemrum mellem- Det vil kontrollere denne sag. Denne sag, hvis det lykkes, vil afbryde ud af funktionen. Så vil det kontrollere dette næste sag, og hvis det lykkes, vil det justere endpoint, og så vil det fortsætte og tjek denne sag. Men på dette punkt, vi ikke ønsker, at fortsætte kontrollen. Heldigvis har vi ikke nulstille midtpunktet her, og vi ved, at denne sag ikke vil lykkes. Men vi vil helt sikkert sætte else if derinde selv om dette kunne, i dette tilfælde da vi ikke er at justere midtpunktet, ville det gøre en forskel? Nej, fordi disse sager er alle eksklusive. Igen, mit dårlige. Vi har ikke, tror jeg, har brug for dette andet, hvis. Vi kan give det en chance og køre det og se hvad der sker. Bygning, der opstod en fejl. Det er nok fordi jeg forlod disse B og e s herinde. Har jeg nogen flere af dem op på toppen? Det ligner ikke det. Vi zoome ud, bygge, der det går, så nu, hvis vi søger efter 15, Ja. Lad mig zoome ind 15, ja. Vi kan køre det igen. Uploading kildekode, bygning, der kører. Vi kan søge efter noget i retning af 13, og vi får ikke noget at udskrive, så det er ikke konstateret, at for os. Det er godt, fordi det ikke er i vores liste. Vi er nu ude af tid. Det kommer til at være det for denne uge. Tak for sammenføjning, og se dig senere. [CS50.TV]