[Powered by Google Translate] [§ 3] [mindre komfortable]
>> [Nate Hardison] [Harvard University]
>> [Dette er CS50.] [CS50.TV]
>> Greit, la oss komme i gang.
Velkommen til uke 4 i CS50.
Hvis dere åpner opp en nettleser og åpne opp pset 3,
Rykke ut med CS50, vi kommer til å begynne å gå
gjennom den delen av spørsmålene der.
Akkurat som forrige uke, vil vi arbeide i CS50 Spaces,
hvis du vil også trekke det opp så godt,
og hvis du går videre og gå til denne linken som jeg har fått her oppe på toppen.
Det er på tide å komme i gang.
Vi har fått vår lille hi programmet her. Ingenting gale.
En av de første tingene jeg ønsker å gjøre med dere i dag er å gå over noen løsninger
til Problem Set 1, type eksempel løsninger,
bare så du kan få en følelse for hva slags kode ansatte skriver,
hva slags kode andre studenter skriver,
og må ta deg en titt på det fordi jeg vet det er rart
når du sender en løsning på et problem sett og få kommentarer
på din egen versjon, men noen ganger er det nyttig å se hvordan andre mennesker gjorde det,
særlig de som er hyggelig ser.
For det meste, ble jeg virkelig imponert over løsningene som dere produsert.
Jeg har ennå ikke begynt å se på problemet ditt Set 2s, men hvis de er noe som den første,
det betyr ingenting, men gode ting.
>> Hvis du ser på mine revisjoner, la oss starte helt nede på Revisjon 1,
og vi kommer til å ta en rask titt på en Mario løsning.
Hvis du trekker dette opp, disse programmene som vi skal presentere er riktige.
Det var ikke korrekthet problemer med disse problemene, men snarere
Vi ønsker å snakke litt om de forskjellige utforming
som ble brukt her.
En av de tingene som var interessant om løsningen
er at det brukes denne nye konstruksjon kalt pund definere,
noen ganger også referert til som en hash definere.
La meg zoome inn på det her.
En # define kan du gi navn til disse tallene i programmet.
I dette tilfellet, den maksimale høyde av en pyramide i Mario
ble 23 og heller enn å sette 23 i min kode-
Vi vil referere til det som vanskelig koding 23 -
stedet gir dette navnet MAX_HEIGHT til det nummeret,
slik at her nede i min do-mens loop
du kan faktisk se MAX_HEIGHT
stedet for å sette nummer 23 i.
[Student] Hva er fordelen med å gjøre det?
Det er et stort spørsmål.
En er lesbarheten.
En fordel med å bruke dette # define er lesbarheten.
Når jeg leser denne koden, kan jeg se hva som skjer.
>> Jeg kan se i denne tilstanden her som vi tester
for høyden blir <0, som vi kunne ha også definert
å være en minimumshøyde eller min høyde.
Den andre fordelen er at jeg kan da lese resten av linjen for å se
at vi også sjekke for å være sikker på at høyden ikke er større enn maks høyde,
fordi vi kommer til å fortsette mens høyden er større enn maks høyde.
Den andre fordelen er-hvis jeg zoome ut litt her-
hvis jeg kjører dette programmet og kjører jeg det, si, med 23 akkurat nå,
det vil skrive ut alle 23 p bare sånn.
Men si jeg ønsket å endre maks høyde,
og nå vil jeg begrense den maksimale høyden pyramidene
å være bare si-mann, som var funky.
# Include , # define MAX_HEIGHT,
og la oss si at vi ønsket å sette den lik 10.
Nå på dette punktet, var alt jeg hadde å gjøre endre den i dette ett sted.
Jeg kan rekompilere koden, og nå hvis jeg prøver og skrive 12,
det vil be meg igjen.
I dette tilfellet er vi bare bruker MAX_HEIGHT gang.
Det er ikke så stor av en hassle å gå i
og endre den i mens loop hvis du må.
Men i programmer der du refererer samme magiske tallet
om og om igjen, denne # define mekanismen er veldig praktisk
fordi du bare endre det en gang på toppen av filen-det er typisk der du setter dem-
og endringen siler gjennom resten av filen.
>> Andre ting jeg ønsket å merke seg i denne oppgaven som jeg trodde så veldig fin,
var navngiving av variablene.
Du ser her at vi har fått heltall variabler kalles rad og såkalte høyde.
Mellomrom, hasher, hjelper det gjøre koden litt mer lesbar,
gjør det litt mer forståelig hva som faktisk skjer.
Dette er i motsetning til ved hjelp, si, tilfeldige bokstaver
eller bare gobbledygook helt.
En siste ting jeg vil påpeke er at i for looper,
ofte disse iterator variabler, disse tellere som du bruker i din for looper,
det er standard og konvensjonelle å starte dem med enten i og deretter j og deretter k
og går videre derfra hvis du trenger flere variabler,
og dette er bare en konvensjon.
Det er mange konvensjoner.
Det avhenger av programmeringsspråk du bruker.
Men i C, vi vanligvis begynne med jeg.
Det gjør ikke fornuftig å bruke, sier a eller b
avhengig av situasjonen.
Det er det for denne.
Hvis du nå trekker opp Revisjon 2, vil du se en annen Mario,
og dette er lik den andre en som vi nettopp så,
men det gjør noe slags cool.
Hvis vi ser på denne delen her inne i indre for loop,
de bruker noen sprø jakt syntaks her rett i denne linjen.
Dette kalles en trefoldig operatøren.
Det er en hvis andre setningen kondenseres til en linje.
Tilstanden er denne delen i parentes.
Det er samme som å si hvis j <høyde - i - 1.
Og hva innholdet i den hvis blokken ville være er plass
og deretter innholdet av hva den ellers ville være er denne #.
Det er i hovedsak tildele en plass til denne variabelen.
Det å sette en plass i innholdet i blokken variabel,
hvis denne betingelsen er oppfylt, og hvis tilstanden ikke er oppfylt,
da blokken variable får denne #.
Og så, selvfølgelig, i stedet for å bygge opp en hel streng
og skrive alt ut på slutten denne løsningen skrives det ut ett tegn om gangen.
Ganske kult.
>> Et annet par ting å se på. Vi vil gå videre til grådige.
Hvis vi nå ser på grådige, denne første løsningen
bruker disse # definerer ganske mye.
Vi har fått en konstant definert for hver av de ulike tallene i dette programmet.
Vi har fått en for cent per dollar, en for kvartalene, dimes, nickels, og penninger,
og nå hvis vi bla ned og lese koden,
Vi kan se en standard gjør-mens loop utskrift alt ut.
Slags crux av dette problemet ble innser at
du trengte å konvertere flottøren som du leser i fra brukeren til et heltall
nøyaktig gjøre regnestykket, og dette er fordi
med flyttall, som vi snakket om i foredraget kort,
det er ikke mulig å nøyaktig representere hver enkelt verdi på tallinja
fordi det er uendelig mange verdier mellom 3 og si, 3,1 enda.
Du kan ha 3.01 og 3.001 og 3.0001, og du kan holde det gående.
Det viser seg når du arbeider med penger, du ofte vil konvertere den
inn heltall format, slik at du ikke mister pennies og den slags ting.
Gjør det og avrunding var nøkkelen.
Denne løsningen brukes en perfekt grei, stor algoritme,
som dekrementeres antall cent igjen, først av kvartalene,
deretter ved dimes, deretter ved nickels, så av pennies,
og legge til antall mynter hver gang.
>> En annen løsning som vi vil se, som jeg zoome ut og gå til Revisjon 4,
hadde en veldig lignende begynnelsen, men i stedet brukt div og mod
rett over her for å beregne antall cent.
Dette, er det antall kvartal lik antall cent dividert 25,
og grunnen til dette fungerer er fordi vi gjør heltallsdivisjon,
så det er forkaster enhver rest.
[Student] Har vi å kommentere søket?
Det avhenger egentlig.
[Student] Du kommenterer mer enn kode her.
Ja, og så er det en haug med varierende filosofier på dette.
Min personlige filosofi er at koden er virkelig sannheten,
som koden din er hva som faktisk er oppfylt på datamaskinen,
og slik at koden skal være så lesbar som mulig for å ikke kreve så mange kommentarer.
Når det er sagt, når du gjør ting som er slags vanskelig matematisk
eller algoritmer, er det godt å kommentere de, slik at du kan
legge til en ekstra dimensjon, et ekstra lag til den som leser koden din.
I disse løsningene, ofte er de kommentert mer tungt bare fordi
vi ønsker å være i stand til å distribuere dem, og har folk plukke dem opp
og lese dem ganske enkelt.
Men definitivt, jeg er enig at dette er tung.
[Student] Men når du er i tvil, gå tyngre?
Når du er i tvil, gå tyngre.
Noen mennesker vil noen ganger si return 0 eller noe sånt.
Jeg tror det er en latterlig kommentar.
Klart det er det som skjer.
Jeg trenger ikke engelsk for å fortelle meg det.
Noen ganger vil folk skrive ting som "kthxbai!"
Det er slags søt, men også ikke-
som ikke gjør forskjell mellom kommentering poeng eller ikke.
Slike kommentarer er bare ha, ha.
Cool.
>> På dette punktet, la oss begynne å jobbe på oppgavesettet § 3 spørsmål.
Hvis dere trekke dette opp igjen,
som med forrige uke, vi kommer ikke til å se shorts i denne delen.
Vi skal la dere gjøre det på din egen tid og snakke om spørsmålene.
Men nå i denne delen skal vi bruke litt mer tid
snakker om mindre av koding grunnleggende
som vi gjorde i forrige uke, og i stedet, vi kommer til å fokusere mer på
litt mer av teorien, så snakker om binære søk og deretter sortere.
Fra de av dere som har fulgt med forelesningen,
kan noen gi meg en oppsummering av hva forskjellen er
mellom binære søk og lineær søk?
Hva skjer? Sure.
Lineære søker blant alle element i den sorterte listen
en etter en etter en etter en etter en,
og binære søk deler listen i to grupper,
Sjekker om tastene verdi som du søker etter er større eller mindre enn midtpunktet verdi
at du nettopp har funnet, og hvis det er mindre enn, går det med den nederste listen
og deretter deler det igjen, gjør det samme funksjon
helt ned til den finner midtpunktet til å være lik selve verdien.
Høyre.
>> Hvorfor bryr vi oss?
Hvorfor snakker vi om binære søk versus lineær søk?
Ja.
Binary er mye raskere, så hvis du doble størrelsen på problemet
det tar ett trinn i stedet for dobbelt så mange.
Akkurat.
Det er et godt svar.
Lineær søk er veldig mye sjekker ett element om gangen,
og som vi så på den aller første dagen av foredrag
da David gikk gjennom hans telefonboken eksempel
og dratt ut én side av telefonen bok om gangen
og holdt gjør at over og over og over igjen,
det kommer til å ta ham veldig lang tid å finne noen i telefonboken,
med mindre, selvfølgelig, ble han leter etter noen helt i begynnelsen av alfabetet.
Med binær søk, kan du gå mye raskere,
og det er ikke bare dobbelt så rask eller tre ganger så rask eller 4 ganger så fort.
Men problemet blir mindre og mindre og mindre mye raskere.
For å illustrere dette, vil vi begynne å snakke om hva som skjer
når vi skriver binære søk.
Problemet på hånden er at hvis jeg har en rekke tall,
si, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
og deretter 9 med et tonn 0s etter det,
vi ønsker å være i stand til å finne ut veldig raskt hva som er i
Denne rekken av tall.
Jeg vet dette virker litt dumt og litt contrived,
fordi akkurat nå er det.
Vi har en matrise som ikke har veldig mange elementer i den,
og hvis jeg spør en av dere til å finne ut hvorvidt
23 er i matrisen, kan du gjøre det ganske raskt
bare ved skotter på dette og fortelle meg ja eller nei.
Den analoge å vurdere er tenk om dette var, sier
et Excel-regneark med 10.000 rader, 20.000 rader.
Selvfølgelig kan du gjøre kommandoen F eller kontroll F og se noe opp.
Du kan også bruke filtre og søk ting,
men hvis du måtte se gjennom denne filen linje for linje for linje,
det vil ta deg lang tid å finne den.
Det er typen som i telefonboken eksempel, også der
ingen ser gjennom en telefonbok én side om gangen.
Vanligvis, åpner de den til midten,
eller i tilfelle av en rekke telefon bøker og ordbøker hvor
du faktisk har det tastet på den første bokstaven,
du slå til det første brevet og åpne og begynne å gå gjennom det.
>> Minner meg om navnet ditt igjen. >> Sam.
Sam.
Som Sam sa, er at lineær søkeprosessen kommer til å bli veldig treg,
og i stedet med binære søk, er måten dette fungerer som
hver gang vi går gjennom en gjentakelse av vår søke algoritme,
vi kommer til å dele listen i to, i hovedsak,
i to mindre lister.
Og så på neste iterasjon av loopen, vil vi dele det på nytt
i andre mindre lister.
Som du kan se, holder problemet blir mindre og mindre
fordi vi holder kaste halvparten av listen hver eneste gang.
Hvordan fungerer dette forkast arbeid?
Akkurat som en påminnelse, hva vi skal gjøre hvis vi var en datamaskin
og vi var, sier, søker etter nummer 5 i denne listen
er at vi vil plukke et tall i midten.
I midten av denne listen, fordi det er en, to, tre, fire, fem, seks, syv, åtte, ni, 10 tall,
vi vil velge nummeret enten på 4. plass eller på 5th posisjon,
og vi vil kalle det midt på vår liste.
Plukk nummer i midten.
Deretter, akkurat som Sam sagt, vil vi teste for å se om det nummeret er lik
til nummeret som vi ønsker å få eller våre ønsket nummer.
Hvis det er lik, så vi har funnet det. Vi vinner.
Hvis det ikke er like, så er det et par tilfeller.
De to tilfellene er enten antallet må være større enn antallet vi ser på,
eller det er mindre enn.
Hvis den er større, flytter vi til høyre.
Og hvis det er mindre, beveger vi oss til venstre.
Og da vi gjenta hele prosessen på nytt
på høyre halvdel eller venstre halvdel av listen.
>> Det første problemet i dagens delen er å finne ut
hvordan vi kan faktisk begynne å uttrykke dette i C-kode.
Vi har fått pseudokode her.
Hva vi vil begynne å gjøre er jeg trekke opp en splitter ny plass,
lagre denne revisjonen, slik at vi har disse notatene for senere,
vi vil slette alt dette, og deretter kopiere og lime inn fra oppgavesettet
denne informasjonen i våre områder, og forhåpentligvis dette ikke bryte.
Perfekt.
Hvis dere alle gjør det, kopiere og lime inn denne koden på ny plass,
inn et blankt.
La oss prøve Daniel. Hvis du kompilere og kjøre dette programmet, virker det?
Nei >> Hva er det å si?
Det sier kontrollen når slutten av ikke-void funksjon.
Ja, så la meg prøve å kjøre den.
Har dere sett dette før? Vet du hva dette betyr?
Ok, la oss dissekere dette litt.
Det sier at file.c på linje 9, kolonne 1 har vi en feil, akkurat som du sa,
og det står at det er stammer fra advarsel om feil og returtypen advarsel.
Det ser ut som noe som skjer med avkastningen type, som er fornuftig.
Vi har et ikke-void funksjon, som betyr at vi har en funksjon
som returnerer ikke ugyldig.
En ugyldig funksjon er en som ser slik ut:
void foo (), og det er ugyldig fordi returtypen er ugyldig,
noe som betyr at hvis vi hadde noe her
som avkastning 1, vil vi få en kompilator feil for dette.
Vi har imidlertid en ikke-void funksjon.
Våre ikke-void funksjon i dette tilfelle er vårt søkefunksjon
fordi den har en avkastning type bool.
Når det er å si at kontrollen når slutten av en ikke-void funksjon,
det er fordi søket ikke har en avkastning uttalelse.
Det er ikke returnerer noe av typen bool.
>> Vi kan fikse det, og hva tror dere
søk skal returneres som standard?
Hva bør være standard returverdien søk?
Fordi det er det vi kan sette på slutten.
Charlotte, har du noen-?
Sant eller usant? >> Sant eller usant.
Hvilken?
False. Jeg vet ikke.
Falsk? La oss prøve det.
Hvorfor sier du return false? Det er stor intuisjon.
[Charlotte] Jeg vet ikke.
Vi kommer til å returnere falsk i dette tilfellet, fordi dette vil være vår standard
hvis noen grunn listen er tom eller nålen
at vi leter etter finnes ikke.
Så helt til slutt, hvis vi ikke return true tidligere i denne funksjonen,
Vi vet alltid at denne funksjonen vil si nope, det er ikke i tabellen.
Det er ikke i høystakken.
Nå hvis vi kompilere og kjøre den, la meg lagre dette så vi kan dra det opp.
Nå hvis vi kompilere og kjøre programmet vårt, bygger det.
Vi får vår lille spørsmål.
Hvis jeg treffer 4-uh-oh.
Det gjorde ikke skrive ut noe. Det ser ut som alt endte bra.
Vi er nødt til å fylle dette i.
Vi snakket om algoritmen i pseudokode litt siden.
La meg se, lagre dette,
og jeg vil trekke det algoritmen opp igjen.
La oss treffer denne fyren. Nope.
Det er det.
Hvordan gjør vi dette?
Hva ville være en god strategi for å starte på denne koden?
Du må velge et tall i midten.
Hvordan plukke vi et nummer i midten av en matrise?
Noen forslag?
[Student] strlen delt på to.
Strlen delt på to. Det er en stor en.
Strlen arbeider med spesielle typer matriser.
Hva slags arrays?
String arrays, karakter matriser.
Det er det samme slags konsept som vi vil bruke,
men vi kan ikke bruke strlen fordi vi ikke har en rekke tegn.
Vi har en rekke ints.
Men hva får strlen for oss?
Vet du hva det blir for oss?
[Student] strlen får oss lengden.
Akkurat, får det oss lengden.
Strlen får lengden på matrisen for oss.
>> Hvordan får vi det i vår binære søk programmet?
Hvordan ville du få lengden av en matrise?
[Student] strlen?
Du kan få lengden på en riktig formatert C string array med strlen.
Problemet er imidlertid at vi ikke har en streng array.
Hvis vi ser tilbake på denne koden, har vi denne heltall array.
Hvordan vet vi hvor lenge det er?
[Student] Er det en tilsvarende en for endepunkt, som int l eller noe?
Det viser seg at det faktisk ikke er det, og det på en måte, er dette
en av de tingene det er bare godt å vite om C,
at det er ingen måte å få lengden av en matrise
hvis alt jeg gir deg er tabellen.
Grunnen til at det fungerer med strenger, grunnen strlen verk,
er fordi hvis en streng er riktig formatert,
det vil ha den spesielle \ 0 tegn på slutten.
>> Du kan også forestille seg hvis du har en feil formatert streng
og det er ingen \ 0 tegn der, så hele greia virker ikke.
[Student] Kan du legge til \ 0?
Vi kunne i dette tilfellet.
Vi kunne legge til noen slags \ 0
eller noen form for betegner karakter og deretter bruke det.
Men det er ikke helt til å fungere
fordi \ 0 er for en char attraksjon,
og her har vi ints.
Den andre tingen er hvis vi skulle bruke en spesiell verdi
som -1 å markere slutten av en matrise
så vi aldri kunne lagre en -1 i våre heltall arrays.
Vi ville bli sittende fast.
Det viser seg at den eneste måten å få lengden
av en rekke i C er å faktisk huske det
når du setter den opp og deretter sende den rundt med array
slik at når jeg har en funksjon som kommer til å gjøre noe arbeid
på en rekke heltall eller flyter eller dobler eller hva har du,
Jeg må også gi funksjonen tabellens lengde,
og det er akkurat hva vi har gjort her i søkefunksjonen.
Hvis du ser, hva vi har gjort når vi passerer i array vår her,
vi også passere i lengden, størrelsen.
Det skjer bare det at vi har kalt denne variabelen her,
denne parameteren eller argument.
Dette kalles en funksjon argument liste eller parameter liste,
og disse kalles også argumenter eller parametere.
Folk bruker ulike begreper på ulike tidspunkter.
Jeg har noen ganger utveksle dem selv.
Det bare så skjer at denne variabelen her er oppkalt tilsvarende
til dette # define opp her.
Men de er ikke det samme.
Kapitaliseringen gjør saken.
>> Hvis du ser på hva som skjer her, erklærer vi
vår int array, som vi har kalt tall.
Vi har gitt det vår størrelse, som tilsvarer vår # define opp på toppen.
Det kommer til å være 8.
Og så når vi da kalle vår søkefunksjon der nede,
vi passerer i antall vi ønsker å søke etter, som vi har bedt om det,
fått fra brukeren.
Vi passerer i rekken, dette tall,
og da må vi også passere i størrelsen på tabellen,
og da verdien av størrelse 8 blir lagret
eller sendes til denne heltallsvariabel kalt størrelse.
Vi har størrelsen på matrisen.
Nå går vi tilbake til det vi snakket om tidligere,
Jeg tror Missy tok opp poenget at det vi trengte å gjøre er å få lengden av tabellen
og dele det med 2, og som vil gi oss midtpunktet.
La oss se.
Kan jeg ha noen skrive dette og lagre det i sin stilling?
Hva med Leila?
Kan jeg ha du skrive dette i?
Skriv den første linjen der du tar lengden på rekke og få midtpunktet
og lagre den i en ny variabel.
Jeg skal gi deg et par sekunder. Er du klar?
[Student uhørlig]
Jada, jeg kunne ha deg å beregne midtpunktet
av høystakken rekke inne i søkefunksjonen
bruke lengden av høystakken matrise, som er den størrelse variabel?
Ikke noe vanskelig her.
[Leila] Bare størrelse / 2 og just-
Og lagre den, og traff på Lagre-knappen her oppe på toppen,
og vi vil trekke det opp.
Perfekt.
Det vi går. Awesome.
>> Som er, vil dette kompilere?
[Leila] Nei, det må være høyere.
[Nate] Yeah, så hva trenger vi å gjøre?
[Leila] Like int midtpunktet eller noe.
Awesome. Ja, la oss gjøre det, int midtpunktet = størrelse.
Vil dette kompilere?
La oss slette denne kommentaren og få det ut av veien.
Hva vil ikke kompilere om dette?
Vi gjør ikke noe med heltall,
så vi må skrive det ut eller noe sånt.
Ja, akkurat.
Vi får en ubrukt variabel.
Hva annet er ikke til å fungere om dette?
Jeg tror du sa noe, Sam. Semikolon.
Ja, jeg mangler de semikolon.
Det kommer til å være en konstant ting i løpet av semesteret.
Den siste tingen jeg vil gjøre er jeg skal sette inn mellomrom på hver side
av denne operatør her, siden det er typisk hvordan vi gjør det
i henhold til vår stil guide.
Vi har fått midtpunktet av array vår.
Nå hvis vi husker tilbake til algoritmen vår,
hva var det andre trinnet at vi måtte gjøre når vi har midtpunktet?
[Student] Hvis den er større [hørbar].
Ja, så vi må gjøre noen form for sammenligning, og hva vi sammenligner her?
Du sa at hvis det er større enn. Hva er det i den setningen refererer til?
Nummeret som kommer opp, hvis det er større enn midtpunktet, og deretter gå opp til array?
Nøyaktig, så antallet som kommer opp når vi-
Nålen, så vi sammenligne med nålen,
og hva er vi sammenligne mot nålen?
Fordi nålen er hva vi leter etter.
Vi sammenligner det å komme til midtpunktet.
>> Men gjør det fornuftig å sjekke for å se
hvis p = midtpunktet?
Gjør det fornuftig?
Ikke uenig noen?
La oss gi det et forsøk, hvis (nål == midtpunkt).
[Student] Har printf du fant det.
[Nate] printf ("Vi fant det \ n");
Ellers-Jeg kommer til å begynne å gjøre noe annerledes her.
Jeg kommer til å begynne å sette tannregulering rundt hvis uttalelser hele tiden
bare fordi hvis vi legger flere ting, så
Vi får ikke kompilatorer.
Ja, Sam. Du har et poeng.
Problemet er at midtpunktet representerer en posisjon i matrisen,
men du kan få det til å representere verdien i den posisjonen i matrisen.
Det er et stort poeng.
Visste alle høre hva Sam sa?
Han sa at midtpunktet som er
representerer bare en posisjon i tabellen, men det er ikke den faktiske element i matrisen.
Hvis du tenker på koden som er skrevet akkurat nå,
hvis vi ser på denne tabellen her nede, som har 8 elementer i den,
hva er verdien av midtpunktet kommer til å være i denne funksjonen?
[Student] 4.
[Nate] 4.
Hvis vi ser etter nummer 4 -
og vi kan bare kjøre denne koden og sette litt trist ansikt her
fordi vi ikke fant det-hvis vi kjører denne koden
som er akkurat nå, laster den, bygg, la meg bla nedover,
og hvis vi ser etter nummer 4,
vi fant det, men vi fikk ikke dette til printf ja.
En grunn er at vi ikke kom tilbake sant,
men vi virkelig finne nummeret 4?
Og Sam sier nei.
Hva fant vi?
Vi har virkelig funnet midtpunktet, som hvis vi ser på tabellen her nede,
det kommer til å være element i indeksen 4 som vi ser på,
som er 23.
>> Hvordan gjør vi faktisk får det elementet på midtpunktet
og ikke bare midtpunktet selv?
[Student] Vi ville gå inn røye eller noe?
Hva ville det gjøre, bare ut av nysgjerrighet?
Kan du utdype litt mer?
Du må transformere posisjon inn nummeret,
så du har å gjøre noen forbindelse-Jeg tror det er røye, men det kan ikke være.
Ja, det er et godt poeng.
Vi har gjort mye av dette konvertere posisjoner til chars, disse tegnene,
i de to første oppgavesett.
Det viser seg at her, dette er nesten lik
tilgang til ITH tegnet i en streng, hvis det er fornuftig.
Her ønsker vi å få tilgang til midtpunktet element.
Hvordan gjør vi det?
Kevin, har du noen forslag til hvordan vi kan gjøre det?
Du kan gjøre høystakken, lukket åpen brakett, mid, brakett.
Kan du skrive det for oss?
Lagre det i her, og vi vil trekke det opp.
Vi ser på denne linjen 9,
og vi innser at vi ikke ønsker å sammenligne nålen til midtpunktet,
men i stedet ønsker vi å sammenligne nålen
til elementet i posisjon midtpunktet innenfor vår høystakk array.
Cool.
Det vi går.
Ja, ser det ganske bra, hvis (nål == høystakk [midtpunktet]).
Vi fant det.
Nå hvis vi kjører koden-vi tilbake opp litt-
det kompilerer, det går, og nå hvis vi ser for 4,
Vi fant ikke det fordi vi er nå faktisk får nummer 23.
Vi får verdien 23, og det er det vi sammenligner til p vår.
Men det er bra. Det er et skritt i riktig retning.
>> Det er det vi prøver å gjøre.
Vi prøver ikke å sammenligne nålen mot posisjoner i rekken
men heller mot selve elementene i matrisen.
Hvis vi ser tilbake igjen nå på det neste trinnet i algoritmen vår,
hva er neste steg?
Leila allerede nevnt det kort.
[Student] Sjekk om den er større eller mindre enn, og deretter bestemme hvilken vei å gå.
[Nate] Yeah, ville så hvordan vi gjør det?
Kan du legge på noen-Jeg sparer denne revisjonen,
og hvis du putter i noen linjer som vil gjøre det.
Ja, Charlotte. >> Jeg har et spørsmål.
Burde det ikke være midtpunktet - 1 fordi det første er
det er 0 indeksert, så hvis vi legger 4, det er faktisk ikke tegnet vi leter etter?
Ja, og det andre problemet med det er-
det er en stor fangst, fordi det kommer til å ende opp som skjer muligens
hvis vi holder bevegelse og vi ikke alltid justere i utgangspunktet?
Jeg antar det vi kan ende opp med å gjøre er å prøve å få tilgang til
elementet på den åttende stilling i matrisen,
som i dette tilfellet ikke.
Vi ønsker å gjøre noen form for regnskap for det faktum
at vi har noen null indeksering.
[Charlotte] Beklager, jeg mente midtpunktet - 1 i hakeparenteser.
Vi kan gjøre det.
Vi vil komme tilbake til denne saken i bare litt.
Når vi begynner å komme til den faktiske looping,
det er da vi vil virkelig se dette kommer inn i bildet.
For tiden kan vi gjøre dette, men du er helt rett.
At null indeksering vil ha en effekt som vi trenger å ta hensyn til.
La oss se.
>> Hvordan er større enn og mindre enn-?
[Student] Jeg får hvordan du gjør det større enn og mindre enn en del.
Jeg var ikke sikker på hva du skal skrive ut hvis du finner ut at det er mindre enn høystakken midtpunktet eller større enn.
Her kan jeg redde det I've-
[Nate] Ja, hvis du lagrer det du har, og vi vil trekke det opp.
Det vi går.
[Student] Og jeg setter spørsmålstegn for hva jeg ikke vet.
[Nate] Det ser flott ut.
Her har vi spørsmålstegn fordi vi fortsatt ikke vet
hva vi skal ganske gjøre ennå.
Hva ville vi ønsker å gjøre, oops, vi har noen bukseseler alle funky på oss.
Vi vil rette disse bukseseler.
Det vi går.
Og så hva vi ønsker å gjøre, ifølge algoritmen vår,
hvis vi ikke finne nålen?
Si i saken at nålen er mindre enn hva vi ser på. Kevin.
Bare se på den venstre halvdelen.
Rett, så vil vi sette en kommentar her som sier "se på venstre halvdel."
Og hvis nålen er større enn høystakken på midtpunktet, hva vi ønsker å gjøre?
[Student] Så du ser på høyre halvdel.
Se på høyre halvdel, "se på høyre halvdel."
Not too shabby.
Ok, så på dette punktet, er ting ser ganske bra.
Problemet med koden som er skrevet er hva?
[Student] Du har ikke endepunktene halvdelene.
Høyre, har vi ikke endepunktene halvdelene.
Vi er også bare kommer til å gå gjennom dette en gang.
Vi kommer bare til å se på en midtpunktet.
Enten elementet er der, eller er det ikke.
For å fullføre dette, må vi gjøre noen form for repetisjon.
Vi trenger å terpe før vi finner ut at
enten elementet er der fordi vi har snevret ned og endelig funnet den,
eller det er ikke der fordi vi har sett gjennom alle de tingene
i de aktuelle halvdelene av matrisen og fant at ingenting er der.
>> Når vi har fått denne repetisjonen skjer, hva vi kommer til å bruke?
[Student] En løkke.
Noen slags loop. Ja.
[Student] Kan vi gjøre en gjør-mens loop og få den gjøre det og deretter mens
nålen ikke lik-Jeg er ikke sikker på hvor jeg skulle med det.
Men typen som gjør at så lenge det ikke lik verdien som brukeren input.
Ja, så la oss se, hvordan kan dette skrive seg selv?
Du sa la oss bruke en gjør-mens loop.
Hvor gjør starten?
[Student] Rett etter størrelse / 2.
[Nate] Ok, og hva skal vi gjøre?
Vi vil fylle på stund senere.
Hva skal vi gjøre?
[Student] Ikke ønsker vi å gjøre alle ting har vi i hvis del?
[Nate] Gjør alt dette, flott.
Kopier og lim inn.
Oh, mann.
La oss se om dette fungerer, hvis vi kan kategorien dette over.
Vakker.
Greit, og vi sparer dette så dere har det.
Greit, og vi kommer til å gjøre dette mens-
hva var mens tilstanden du var ute etter?
[Student] Mens nålen ikke lik, så som utropstegn.
Men jeg er ikke sikker på nøyaktig hva det er ennå.
[Nate] Yeah, dette er en måte å gjøre det.
Sam, har du en kommentar?
[Sam] Jeg husket da jeg så på videoer,
Jeg tok en skjermdump av en av-lignende når vi gjorde pseudokode for det,
det var noen sammenheng mellom maks og min.
Jeg tror det var noe sånt som om max er stadig mindre enn min.
Fikk den.
[Sam] Eller som om max er ikke mindre enn min eller noe sånt,
fordi det ville bety at du har søkt alt.
>> Ja, så hva høres det ut som max og min var henviser til?
[Sam] verdier som-heltall som kommer til å endre
i forhold til der vi satt midtpunktet.
Akkurat.
[Sam] På dette tidspunktet, det kommer til [uhørbart] beregne maks og min.
Midtpunkt er dette maks og min idé.
Gjør det fornuftig for folk?
Hvis vi skulle begynne å se på hvordan vi skal gjøre dette iterasjon,
du er helt riktig at vi ønsker å bruke noen form for do-mens loop.
Men jeg antar at hvis vi husker hva som skjer på stedet av denne tabellen
og hva som faktisk skjer-Jeg kommer til å skrive over her-
på den aller første iterasjon av binære søk, har-vi
Jeg kommer til å bruke b og e for å betegne begynnelsen.
Og så skal enden av tabellen vår.
Vi vet at begynnelsen er på 4 rett over her,
og vi vet at slutten er på 108.
Si at vi søker etter nummer 15.
Den første gangen vi gjør dette, som vi så tidligere,
midtpunktet er enten kommer til å være 16 eller 23
avhengig av hvordan vi beregner ting.
Siden jevnt dele i midten ville gi oss denne plassen
mellom 16 og 23, kan vi ikke jevnt dele det
eller dele det og få på en sann midtpunktet.
Vi skal se på 16 år.
Vi vil realisere "Hey, 16> 15 som vi leter etter."
Å deretter se på venstre halvdel av tabellen
hva vi vil ende opp med å gjøre forkaster
hele denne øvre delen
og sier: "Ok, nå vår endepunkt skal være her."
Den neste iterasjon av loop, er vi nå ser på denne tabellen,
effektivt å ha forkastet dette delen fordi nå
hvis vi tar midtpunktet å være forskjellen mellom begynnelsen og slutten,
vi finner vår midtpunktet å være 8,
som vi kan så teste 8 for å se hvor den er i forhold til antall vi leter etter,
15, finner ut at 15 er større,
så vi må flytte til høyre del av listen,
som vi vet, fordi vi er mennesker, og vi kan se det.
Vi vet at den høyre delen kommer til å være der vi finner det,
men datamaskinen ikke vet det, så hva vi vil gjøre er at vi vil faktisk
har dette gå opp, og nå i begynnelsen og slutten
er det samme stedet, så midtpunktet blir det eneste nummeret i listen på det punktet,
som er 15, og vi har funnet det.
Betyr det kaste lys over hvor hele denne max og min notasjon går,
holde orden på endepunktene i tabellen for å finne ut
hvordan å begrense ting ned?
>> Hva ville skje hvis dette ikke var lik 15 nå?
Hva hvis vi var ute etter 15 og i stedet var dette tallet også 16?
Vi vil si, "Å, det er større.
Vi ønsker å gå tilbake til venstre. "
Og vi ville flytte vår e til høyre,
på hvilket punkt har vi et endepunkt som ville være i konflikt.
Det ville ikke være i stand til å søke etter eventuelle flere elementer
fordi nå har vi vår endepunkt og vår startpunkt,
vår max og vår min, er nå snudd.
Vi søker gjennom hele matrisen. Vi kan ikke finne noe.
Det er punktet der vi ønsker å si, "Ok, vi kommer til å stoppe denne algoritmen.
Vi har ikke funnet noe. Vi vet det er ikke her. "
Hvordan dette kommer?
[Student] Hvor nøyaktig slår maskinen slutten?
Hvordan ender til slutt opp før begynnelsen?
Slutten ender opp før begynnelsen
på grunn av det matte som vi kommer til å gjøre hver gang vi gjør dette.
Måten vi bytte er hvis du ser på den aller første gangen vi gjør dette swap
hvor vi har begynnelsen ved 4 og enden
hele veien ned på 108 og vår midtpunktet, sier at 16 -
Jeg kommer til å tilbakestille dette tilbake til 15-hvis vi leter etter de 15,
vi visste at det vi gjorde da vi sjekket 16 og så at det var større
og ønsket å forkaste hele høyre del av listen,
Vi så at det vi ønsket å gjøre er å flytte denne e her.
Effektivt, fikk e flyttet til en før midtpunktet.
Likeledes når vi gjorde dette iterasjon av algoritmen
og midtpunktet var på 8,
Vi fant at 8 <15, så vi ønsket å flytte b
en forbi midtpunktet.
Nå, begynnelsen og enden er begge sammen på denne 15.
>> Hvis vi hadde hatt det slik lete etter en annen verdi, ikke 15,
eller hvis denne 15 hadde i stedet blitt en 16,
vi ville ha funnet ut at e vi ønsker å flytte en før midtpunktet.
Nå e ville være der venda mindre enn b.
La oss gå gjennom hvordan vi faktisk ende opp koding denne algoritmen.
Vi vet at vi ønsker å ha denne midtpunktet beregningen.
Vi vet også at vi ønsker å spore begynnelsen og slutten av tabellen
av vår nåværende utvalg, slik at vi kan finne ut
hvor denne venstre halvdel av listen er og hvor den høyre halvdel av listen er.
Vi gjør det med enten begynner og slutter,
eller vi kan kalle dem min og maks.
Jeg skal bruke begynner og slutter denne gangen.
Når vi begynner, hvis vi ser tilbake på vårt eksempel her nede,
våre begynnelsen ble satt til begynnelsen av tabellen, som naturlig.
Hva indeksen var dette? Hva skal vår begynne bli?
Daniel.
[Daniel] Haystack [0].
[Nate] Yeah, slik at vi kunne sette den lik høystakken [0].
Problemet, er imidlertid at det gir oss ikke posisjonen av det første elementet.
Det gir oss indeksen av det første elementet eller det faktiske verdi på det første posisjon.
[Student] Det vil konvertere til 0,20?
[Nate] Hva dette vil gjøre er-vel, vil det ikke gjøre noe konvertering.
Hva det vil gjøre det vil lagre en 4 i begynne,
og da vil det være vanskelig å foreta sammenlikninger mot begynne
fordi Begin skal disponere verdi på 4,
som er begynnelsen av array vår,
men vi ønsker å spore indeksene i rekken
i motsetning til de verdier.
Vi vil faktisk bruke en 0, sånn.
For enden av tabellen-Charlotte tok dette opp litt tidligere.
Dette er hvor vi tar hensyn til null indeksering.
>> Charlotte, hva er slutten av tabellen?
Hva er indeksen på slutten?
[Charlotte] Størrelse - 1.
Ja, og hvilken størrelse bør vi bruke?
Skal vi bruke egenkapital eller små størrelser?
Egenkapital.
I dette tilfellet kan vi bruke egenkapital.
Hvis vi ønsket at denne funksjonen skal være bærbare
og bruke denne funksjonen i andre programmer,
Vi kan faktisk bruke små størrelse.
Det er greit også.
Men Charlotte er helt riktig at vi ønsker å ha størrelse - 1.
På dette punkt-
[Student] Hvordan har det seg at du kan bruke store størrelse?
Hvordan har det seg at vi kunne bruke store størrelse?
Det viser seg at disse # definerer er virkelig,
under panseret, en tekst som finne og erstatte, hvis det er fornuftig.
Når du kompilere koden, forbehandling fase
av kompilatoren går gjennom filen,
og det ser for overalt at du har skrevet egenkapital,
og det erstatter den teksten bokstavelig talt med en 8, akkurat sånn.
I den forstand er dette veldig forskjellig fra en variabel.
Det tar ikke opp noe plass i minnet.
Det er en enkel tekst replace triks.
I dette tilfellet skal vi bruke størrelse.
Herfra vil vi gjøre noen form for repetisjon,
og vi er på rett spor med vår do-while-løkke.
Vi ønsker å gjøre noe før en tilstand ikke holder lenger,
og som vi så tidligere, så vi at den tilstanden
var faktisk at vi ikke vil til slutt
å være mindre enn den begynne.
>> Dette er vår stoppe tilstand.
Hvis dette skjer, vil vi stoppe og erklære som "Hei, vi har ikke funnet noe."
For å uttrykke dette, ønsker vi å bruke noen form for loop.
I dette tilfellet ville det være en gjør-mens loop, en for løkke, en stund loop?
Vi har en do-while løkke her.
Har dere liker at tilnærmingen?
Tror du vi bør prøve en annen tilnærming?
Kevin, noen tanker?
Vi kunne ha en stund loop fordi vi vet maksimal
ville være større enn min i starten anyways.
Ja, så det er ingen initialisering som må skje.
De gjør-mens sløyfer er stor når du har å initialisere noe
før så teste, mens her
Vi vet at vi ikke kommer til å holde reinitializing både begynner og slutter
hver runde av loopen.
Vi vet at vi ønsker å initialisere dem, så sjekk vår tilstand.
I dette tilfellet vil jeg faktisk gå med en enkel stund loop.
Det viser seg at gjør-mens sløyfer brukes ganske sjelden.
En rekke steder ikke engang undervise gjøre mens sløyfer.
De er bra for håndtering brukerens input, så vi har sett mange av dem så langt.
Men normalt for og mens sløyfer er mye mer vanlig.
Det viser seg at denne tilstanden som skrevet
vil egentlig ikke gjøre oss mye godt, og hvorfor er det?
Jeg beklager, jeg vet ikke navnet ditt.
Jeg er Jerry. >> Beklager?
Det er B-O-R-U-I.
Oh, okay.
Jeg ser ikke deg på listen min.
Åh, det er fordi-oh, det er fornuftig.
Har du en idé om hvorfor dette mens loop ikke kan fungere som tiltenkt,
som skrevet med tilstanden?
[Jerry] Mener du som du vil at alle ting etter den i-?
Ja, slik at man.
Vi må kanskje sette alt dette ting i mens loop, som er helt sant.
Den andre tingen som er litt mer problematisk, skjønt, er at denne tilstanden ikke fungerer.
[Student] Du må snu den.
Rett, så denne tilstanden vil aldri være sant i utgangspunktet den måten vi snakket om det.
Vi ønsker å gjøre noe før slutten <begynne,
men vi ønsker å gjøre noe mens
begynne ≤ slutt.
>> Det er det reversering av logikken der.
Jeg er skyldig i å lage disse feilene hele tiden.
[Student] Hvorfor må det være mindre enn eller lik?
Fordi husker du det slik at vi fikk
hvor det var bare ett element, og vi var nede,
og vi var ute på akkurat 15 i matrisen vårt?
Og vår begynnelse og vår ende var de samme element.
Vi ønsker å sørge for at vi håndterer den saken.
Hvis vi gjorde en rett mindre enn,
vi ville bare være i stand til å komme ned til en 2-element array.
Når vi kom ned til det siste elementet, hvis det var vår element, ville vi aldri finne det.
Nå her, kan vi gjøre akkurat som du sa.
Vi kan begynne plopping ting rett inn i midten av vår mens loop.
Vi kan plop i midtpunktet vår.
Vi kan ta alle disse hvis uttalelser,
trekke dem ut av denne gjør-mens loop,
plop dem i,
rydde ting opp litt,
og jeg skal gå videre og lagre denne revisjonen.
Og på dette punktet, vi får ganske nær.
Sam.
Jeg tror du må også ha int midtpunktet = størrelse - 1/2.
Fikk den, størrelse - 1/2.
Er det noe annet vi trenger å endre om den linjen?
Det var en god fangst.
>> Hva gjør størrelse? Er vi stadig skiftende størrelse?
For å holde linjen som dette, må vi endre størrelsen.
Vi må endre størrelsen hver gang vi går rundt for loop.
Men husk når vi skulle gjennom vårt eksempel bare litt tidligere,
og vi hadde i begynnelsen på 4
og slutten helt over på 108?
Hvordan gjorde vi beregner midtpunktet?
Brukte vi størrelsen?
Eller vi brukte begynner og slutter i stedet?
Det er forskjellen mellom slutten og begynnelsen.
Nøyaktig, og hvordan akkurat skal jeg skrive det, Charlotte?
Bare ende - begynne.
Du trenger ikke å gjøre det - en
fordi - 1 har blitt tatt i slutten og begynnelsen allerede.
[Nate] Flott, er du helt rett.
Vi trenger ikke å gjøre det - 1 fordi det - en er tatt
og sto for når vi initialisere slutten variabel.
>> Er det noe annet jeg trenger å gjøre syntaktisk å ha denne linjen fornuftig?
[Student] Plus begynne. >> Plus begynne?
[Student] På slutten.
Fordi det er bare beregnet halve lengden.
Du må legge til begynne.
[Nate] Hva ville dette beregne for oss?
Hvis vi tenker slutten på denne aller første iterasjon av loopen,
end kommer til å være i posisjon indeks 7.
Begynne er i posisjon 0.
Husk, vi leter etter enten
posisjon 3 eller posisjon 4.
Hvis vi ser på dette regnestykket, bare gjøre det litt mer konkret,
sette noen tall her, har vi 7, 0,
så 7-0, og deretter / 2
er 3 i heltallsdivisjon, altså.
Deretter trenger vi å deretter legge tilbake vår begynne?
Vi gjør ikke i dette tilfellet.
På den aller første iterasjon, vil det være fint fordi begynne er 0.
Men som vi fremgang, gjør vi egentlig alt bare trenger
end - begynner / 2.
Det er en annen triks her, og det er nemlig en av forrang.
[Student] Trenger vi parentes?
[Nate] Nettopp, og det er fordi hvis vi ikke sette disse parentes,
så denne linjen vil bli tolket i stedet
som (slutten) - (begynne / 2), som vi definitivt ikke ønsker.
Se opp for disse prioriteringsregler.
[Student] Hvorfor er ikke ender det + begynne?
Hvorfor er ikke det ende + begynne?
[Student] Hvorfor er det ikke det?
Hvorfor skulle det være +?
Jeg tror du har rett.
[Student] Fordi det er gjennomsnittet?
[Nate] End + begynne, er du helt rett.
Wow, jeg helt goofed. Du har rett.
Hvis vi gjorde minus, ville vi ønsker å legge til begynne tilbake igjen
I dette tilfellet, du er veldig riktig at vi ønsker å ta gjennomsnittet av de to,
så vi ønsker å legge dem, i motsetning til å trekke dem.
[Student] Det vil også fungere hvis du gjorde ende - begynner / 2 + begynne.
Det ville gjort hvis vi gjør-Jeg tror det.
>> For eksempel, hvis vi var ute på begynne,
og vi flyttet det over her
til 15.
Nå begynne er i 2-stilling.
End er ved posisjon 7.
Hvis vi trekker dem, får vi 5.
Dele det med 2, får vi to.
Og så legger vi til 2 tilbake i,
og som får oss til 4. plass,
som er rett her, som er midtpunktet.
[Student] Trenger vi å ta vare på emballasjen?
I hvilken forstand trenger vi å ta vare på innpakning?
Hvis summen eller forskjellen mellom
avhengig av hvordan vi gjør det er ikke et partall.
Deretter datamaskinen blir forvirret om når det er 2,5;
flytter du til venstre eller til høyre for å avgjøre hva som er midtpunktet?
Fikk den.
Det viser seg at med heltallsdivisjon,
vi ikke noen gang får disse flyttall.
Vi får aldri desimal.
Det er helt forkastet.
Hvis du har dele en datamaskin to int variabler,
og en er 7, og den andre er 2,
du vil ikke få 3,5 som resultat.
Det vil få 3.
Resten vil bli forkastet, så det er effektivt avrunding-
ikke en runde, men snarere en etasje, hvis dere er kjent med at det i matematikk,
hvor du helt forkaste desimal,
og så du egentlig avkorting det ned til nærmeste
Hele posisjon, til nærmeste hele tall.
[Student] Men så det er problematisk fordi hvis du har en rekke av 7 elementer
deretter som tar automatisk den tredje elementet ut av midtpunktet istedenfor 4..
Hvordan håndterer vi det?
Det er problematisk fordi hvis vi hadde en rekke 7,
det skulle plukke den 3. i stedet for fjerde.
Kan du forklare litt mer?
[Student] Fordi hvis du har 7 elementer deretter fjerde element
ville være midtpunktet, ikke sant?
Husk din kommentar om å være null indeksert, skjønt.
[Student] Yeah, så i posisjon 3. Det ville være midtpunktet.
Ja.
Oh, okay. Jeg ser hva du mener.
Det er litt rart, som vi blir vant til dette hele oppfatningen av
bli kvitt desimaler.
Det er et stort poeng.
La oss avslutte dette.
Vi har beregnet vår midtpunktet.
>> Vi tester for å se om vår nålen er lik den midterste verdien.
Vi skriver at vi fant det, men egentlig, hva vi ønsker å gjøre i denne situasjonen?
Vi har funnet det, så vi ønsker å la den som ringer vet at vi fant det.
Vi har fått en funksjon som er en boolean skrevet funksjon.
Måten vi signalisere til den som ringer av vår funksjon som vi er klar til å gå
er vi sier, "Hei, dette er sant."
Hvordan ville vi gjøre det, Kevin?
Du nikker hodet. >> [Kevin] Legg return true.
[Nate] Akkurat, return true.
Nå, hvis det ikke er like, hvordan ville vi ser på den venstre halvdelen?
Noen ideer?
Stella, noen ideer?
Du trenger for å sette en ny posisjon for slutten.
Ja.
Så vi må gjøre stilling midtpunktet - slutten.
Flott.
Vi trenger å sette en ny stilling for slutten
å se på den venstre halvdelen.
Dette var hva vi snakket om før der
Jeg holde går tilbake til dette eksemplet.
Jeg har den begynner her, og da har jeg til slutt hele veien hit.
>> Igjen, hvis vi leter etter 15, og vår midtpunktet er på 16,
og vi innser, "Oops, er 16 større.
Vi ønsker å flytte til venstre halvdel. "
Vi vil deretter flytte slutt på 15,
og vi gjør det ved å ta en bort fra midtpunktet
og innstillingen som ny slutt.
Likeledes, hvis vi ønsker å se på høyre halvdel, hvordan ville vi gjøre det?
Har du en idé?
[Student] Du har nettopp satt begynne å midtpunktet + 1.
[Nate] Great.
Og nå i tilfelle at vi ikke finner noe,
får det tatt vare på for oss?
Daniel, betyr det bli tatt vare på for oss?
[Daniel] Nei
[Nate] Hvis vi gjør det gjennom hele matrisen, og vi finner ikke noe,
hvor ville det bli tatt vare på, eller skal vi ta vare på den?
[Daniel] while tilstand.
[Nate] Yeah, mens tilstanden, akkurat.
Det vil ta vare på å gå gjennom hele matrisen hvis vi ikke finner noe.
Dette mens loop vil ende.
Vi vil aldri møtt denne tilstanden,
og vi kan returnere falsk.
Vi kan også la dette hvis du er i her som dette
fordi hvis dette hvis setningen er sann,
og vår funksjon kommer tilbake,
og så vi vil i hovedsak avbryte denne funksjonen på dette punktet
når vi kommer tilbake sant.
Men hva skjer med denne strukturen her?
Vil dette fungere helt, eller er det noen logisk brist i det?
>> Det er noen logisk brist i det, med måten det er satt opp.
Hva kan det være?
[Student] Hvorfor trenger du det - og + 1s?
Som setter vår rekke opp til å bli vår nye venstre halvdel og høyre halvdel.
[Student] Men hvorfor kunne ikke du gjøre det uten - 1s og + 1s?
[Nate] Vi kunne sette den lik midtpunktet?
Hva kan være problematisk om det?
[Student] Jeg antar det er ineffektivt fordi du sjekker en verdi som allerede er kontrollert.
[Nate] Akkurat, så Sam er helt riktig.
Hvis du setter enden og begynner lik midtpunktet
i stedet for - 1 og + 1 reflektert,
på et tidspunkt i fremtiden vil vi ende opp med å sjekke midtpunktet igjen.
[Student] Jeg startet pset, og da jeg hadde noe sånt
hvor jeg glemte + 1, og det ble sittende fast i en uendelig loop.
Høyre, fordi på et tidspunkt du aldri kommer til å få begynne og slutte
å faktisk overlappe.
Cool.
Det er enda en logisk brist, og det er at dette bør definitivt være
en else if.
Hvorfor kan det være?
>> Grunnen er hvis det ikke er en annen hvis-så du det, Kevin?
[Kevin] Yeah, fordi du endrer endepunktet.
[Nate] Nettopp.
Vi endrer endepunktet,
og hvis det er skrevet slik-vi gjør mellomrom mellom-
det vil sjekke denne saken.
Dette tilfellet, hvis det lykkes, vil den avbryte ut av funksjon.
Da vil det se dette neste sak,
og dersom dette lykkes, vil den justere endepunktet,
og da vil det fortsette og sjekke dette tilfellet.
Men på dette punktet, vet vi ikke vil at den skal fortsette å kontrollere.
Heldigvis har vi ikke tilbakestille midtpunktet her,
og vi vet at denne saken ikke vil lykkes.
Men vi definitivt ønsker å sette annet hvis i det
selv om det kanskje i dette tilfellet
siden vi ikke justerer midtpunktet, ville det gjøre en forskjell?
Nei, fordi disse sakene er alle eksklusive.
Igjen, min feil.
Vi har ikke, tror jeg, trenger dette else if.
Vi kan gi det en sjanse og kjøre den og se hva som skjer.
Building, det oppstod en feil.
Det er nok fordi jeg forlot disse b-og e er her.
Har jeg noe mer av dem opp på toppen?
Det ser ikke ut som det.
Vi zoome ut, bygge,
der det går, så nå hvis vi søker etter 15,
Ja.
La meg zoome inn
15, ja. Vi kan kjøre den på nytt.
Opplasting kildekode, bygge, kjøre.
Vi kan søke etter noe sånt 13,
og vi ikke får noe å skrive ut, så det er ikke å finne det for oss.
Det er flott, fordi det ikke er i vår liste.
>> Vi er nå ute av tiden.
Det kommer til å være det for denne uken.
Takk for at du deltar, og se deg senere.
>> [CS50.TV]