[Powered by Google Translate] [Sectie 3] [minder comfortabel]
>> [Nate Hardison] [Harvard University]
>> [Dit is CS50.] [CS50.TV]
>> Oke, laten we beginnen.
Welkom bij Week 4 van CS50.
Als jullie het openen van een web browser en open te stellen PSET 3,
Scramble met CS50, we gaan om te beginnen gaan
via de rubriek van vragen daar.
Net als vorige week, we werken in CS50 Spaces,
als je ook trek die omhoog als goed,
en als je verder gaan en bezoek deze link die ik heb hier op naar de top.
Het is tijd om te beginnen.
We hebben onze kleine hi programma hier. Niets gek.
Een van de eerste dingen die ik wil doen met jullie vandaag gaan over een paar oplossingen
naar Problem Set 1, een soort van voorbeeld oplossingen,
zodat je kunt krijgen een gevoel voor welke soorten code personeel is het schrijven,
wat voor soort code andere studenten schrijven,
en heb je een kijkje nemen op het omdat ik weet dat het raar is
wanneer u een oplossing voor een probleem set en krijgt commentaar
op uw eigen versie, maar soms is het handig om te zien hoe andere mensen het deed,
met name degenen die zijn mooi ogende.
Voor het grootste deel, was ik echt onder de indruk van de oplossingen die jullie gemaakt.
Ik ben nog niet begonnen met te kijken naar uw probleem Set 2s, maar als ze iets als de eerste,
het betekent niets dan goede dingen.
>> Als je kijkt naar mijn revisies, laten we beginnen helemaal naar beneden op Revisie 1,
en we gaan een snelle blik op een Mario-oplossing te nemen.
Als je trek deze omhoog, deze programma's dat we gaan presenteren correct zijn.
Er waren niet juistheid problemen met deze problemen, maar eerder,
willen we een beetje praten over de verschillende ontwerpaspecten
die werden hier gebruikt.
Een van de dingen die interessant was over de oplossing
is dat het dit nieuwe construct genaamd pond te definiëren gebruikt,
soms ook aangeduid als een hash definiëren.
Laat me hier inzoomen op.
Een # define kunt u een naam geven deze nummers in uw programma.
In dit geval is de maximale hoogte van een piramide in Mario
werd 23 en in plaats van dat 23 in mijn code-
wij verwijzen naar dat zo hard codering 23 -
in plaats daarvan geeft dit de naam MAX_HEIGHT naar dat nummer,
zodat hier in mijn do-while-lus
je kunt eigenlijk verwijzen naar MAX_HEIGHT
in plaats van dat het nummer 23 inch
[Student] Wat is het voordeel om dat te doen?
Dat is een grote vraag.
Een daarvan is de leesbaarheid.
Een voordeel van deze # define is leesbaarheid.
Als ik deze code te lezen, kan ik zien wat er gaande is.
>> Ik zie hier in deze toestand dat we testen
voor de hoogte wordt <0, wat we ook zouden kunnen hebben gedefinieerd
, een minimum of min hoog zijn.
Het andere voordeel is dat ik dan kan de rest van de regel te lezen om te zien
dat we ook controleren om ervoor te zorgen dat de hoogte niet groter is dan de maximale hoogte,
want we gaan verder terwijl de hoogte groter is dan de maximale hoogte.
Het andere voordeel is, als ik uit te zoomen een beetje hier-
als ik zonder dit programma en ik voer het uit, zeg, met 23 op dit moment,
zal het afdrukken alle 23 rijen zomaar.
Maar zeggen dat ik wilde de max. hoogte te veranderen,
en nu wil ik de maximale hoogte van piramides te beperken
om alleen maar zeggen-man, dat was funky zijn.
# Include , # define MAX_HEIGHT,
en laten we zeggen dat we wilden het gelijk is aan 10.
Nu op dit moment, alles wat ik moest doen was wijzigen in dit ene locatie.
Ik kan opnieuw compileren van de code, en nu als ik probeer en typ in 12,
Het zal u vragen me weer.
In dit geval zijn we alleen met behulp van MAX_HEIGHT een keer.
Het is niet zo groot van een gedoe om in te gaan
en verander het in de while-lus als dat nodig is.
Maar in programma's waar je verwijzen naar de zelfde magische getal
over en weer, deze # define mechanisme is erg handig
omdat je gewoon veranderen het een keer aan de top van het bestand, het is meestal waar je ze-
en de verandering sijpelt door de rest van het bestand.
>> Andere dingen die ik wilde om op te merken in deze opdracht, dat ik dacht dat zag er erg leuk,
was de naamgeving van de variabelen.
Je ziet hier dat we integer variabelen genoemd rij en zogenaamde hoogtepunt.
Spaces, hashes, het helpt om de code een beetje meer leesbaar,
maakt het een beetje begrijpelijker wat er werkelijk aan de hand is.
Dit in tegenstelling tot het gebruik van bijvoorbeeld willekeurige letters
of gewoon gobbledygook helemaal.
Een laatste ding dat ik wel opmerken is dat in voor lussen,
vaak deze iterator variabelen, deze tellers die je in je gebruiken voor loops,
het is standaard en conventionele te beginnen met i en dan j en dan k
en gaan van daar als u meer variabelen,
en dit is slechts een conventie.
Er zijn veel overeenkomsten.
Het hangt af van de programmeertaal die u gebruikt.
Maar in C, we meestal beginnen met i.
Het heeft geen zin om te gebruiken, laten we zeggen, op a of b
afhankelijk van de situatie.
Dat is het voor deze ene.
Als u nu trek Revisie 2, zie je een andere Mario,
en dit is gelijk aan de andere die we zagen,
maar het doet iets wel cool.
Als we kijken naar deze sectie hier binnen de binnenste for-lus,
ze gebruiken wat gekke zoek syntax hier rechts in deze lijn.
Dit wordt een ternaire operator.
Het is een if else gecondenseerd in een lijn.
De conditie is dit deel tussen haakjes.
Het is als zeggen als j <hoogte - i - 1.
En dan wat de inhoud van dat als blok zou zijn, zijn de ruimte
en dan de inhoud van wat de ander zou zijn zijn deze #.
Het is in wezen het toewijzen van een ruimte om deze variabele.
Het Een spatie in de inhoud van het blok variabele
Als deze voorwaarde is voldaan, en als de voorwaarde niet is voldaan,
vervolgens het blok variabele krijgt deze #.
En, natuurlijk, in plaats van het opbouwen van een gehele reeks
en printen alles aan het eind van deze oplossing drukt het uit een karakter per keer.
Pretty cool.
>> Nog een paar van de dingen om naar te kijken. We gaan naar hebberig.
Als we nu kijken naar hebberig, deze eerste oplossing
gebruikt deze # definieert nogal wat.
We hebben een constante gedefinieerd voor elk van de verschillende nummers in dit programma.
We hebben een voor cent per dollar, een voor kwartalen, dubbeltjes, stuivers en centen,
en nu als we scroll naar beneden en lees de code,
zien we een standaard do-while-lus afdrukken alles uit.
Kind van de kern van dit probleem is het besef dat
u nodig om de vlotter te zetten die je leest in van de gebruiker naar een geheel getal
om nauwkeurig do the math, en dit is omdat
met floating point getallen, zoals we besproken in college kort,
het is niet mogelijk om nauwkeurig te vertegenwoordigen elke waarde op de getallenlijn
want er zijn oneindig veel waarden tussen 3 en, zeg, 3,1 zelfs.
U kunt 3,01 en 3,001 en 3,0001, en je kunt blijven gaan.
Het blijkt wanneer je werkt met geld, je vaak wilt converteren
in integer formaat, zodat je niet verliest centen en dat soort dingen.
Dat te doen en afronding was de sleutel.
Deze oplossing gebruikt een perfect eenvoudige, goed algoritme,
die verlaagd het aantal centen blijven, eerst door kwartalen,
vervolgens door dubbeltjes, vervolgens door stuivers, vervolgens door centen,
en toevoegen aan het aantal munten per keer.
>> Een andere oplossing die we zullen zien, zoals ik uit te zoomen en ga naar Herziening 4,
had een zeer vergelijkbaar begin, maar in plaats daarvan gebruikt div en mod
rechts over hier om het aantal centen te berekenen.
Dit is het aantal kwarten gelijk is aan het aantal cents gedeeld door 25,
en de reden dat dit werkt is omdat we doen integer deling,
dus het is waarbij een eventueel restant.
[Student] Moeten we de zoektocht commentaar geven?
Het hangt echt.
[Student] Je commentaar meer dan code hier.
Ja, en zo zijn er een heleboel verschillende filosofieën op dit punt.
Mijn persoonlijke filosofie is dat je code echt de waarheid,
als uw code is wat er feitelijk niet uitgevoerd op de computer,
en dus de code moet zo leesbaar mogelijk te niet noodzakelijk zo veel commentaar.
Dat gezegd hebbende, als je dingen die soort doen mathematisch van lastige
of algoritmisch, het is goed om te reageren degenen, zodat u kunt
een extra dimensie, een extra laag aan wie het lezen van uw code.
In deze oplossingen, vaak worden ze zwaarder, alleen maar omdat commentaar
We willen in staat zijn om ze te distribueren en er mensen ophalen
en lees ze vrij gemakkelijk.
Maar zeker, ik ben het eens dat dit zwaar is.
[Student] Maar als je twijfelt, ga dan zwaarder?
Als je twijfelt, ga zwaarder.
Sommige mensen zullen zeggen soms return 0 of iets dergelijks.
Ik denk dat het een belachelijke opmerking.
Het is duidelijk dat dat is wat er gebeurt.
Ik hoef niet Engels om me te vertellen dat.
Soms zullen mensen schrijven dingen als "kthxbai!"
Dat is wel leuk, maar ook niet-
dat is niet het maken van het verschil tussen commentaar punten of niet.
Dat soort opmerkingen zijn gewoon ha, ha.
Cool.
>> Op dit punt, laten we beginnen werken aan het probleem Set 3 deel van de vragen.
Als jullie trek deze weer op,
zoals met vorige week, we niet van plan om de korte broek te kijken in dit hoofdstuk.
We laten jullie dat doen op uw eigen tijd en praten over de vragen.
Maar nu in deze paragraaf gaan we wat meer tijd door te brengen
praten over minder van de coderende basics
zoals wij deden vorige week, en in plaats daarvan, gaan we meer focussen op
een beetje meer van de theorie, zodat het over binary search en dan sorteren.
Van degenen onder u die zijn samen volgt met de lezing,
kan iemand mij een samenvatting van wat het verschil is
tussen binair zoeken en lineaire zoeken?
Wat is er aan de hand? Tuurlijk.
Lineair zoeken doorzoekt elk element in de gesorteerde lijst
een voor een door een voor een een,
en binair zoeken verdeelt de lijst in 2 groepen,
controleert of de sleutels waarde die u zoekt is groter dan of kleiner dan het midden-waarde
dat je net gevonden, en als het minder dan, het gaat met de onderste lijst
en dan verdeelt dat opnieuw, doet dezelfde functie
helemaal naar beneden tot hij het midden gelijk aan de waarde zelf.
Juist.
>> Waarom hebben we schelen?
Waarom praten we over binary search versus lineair zoeken?
Ja.
Binaire is een stuk sneller, dus als je het dubbele van de omvang van het probleem
duurt een stap dan tweemaal zoveel.
Precies.
Dat is een geweldig antwoord.
Lineair zoeken is zeer controleert een element tegelijk,
en zoals we zagen op de eerste dag van de lezing
toen David ging door zijn telefoonboek voorbeeld
en scheurde uit een pagina van het telefoonboek op een moment
en bleef dat te doen over en over en weer,
het gaat om hem een ​​hele lange tijd voor iedereen in het telefoonboek te vinden,
tenzij, natuurlijk, werd hij op zoek naar iemand aan het begin van het alfabet.
Met binair zoeken, kunt u een stuk sneller,
en het is niet alleen twee keer zo snel of 3 keer zo snel of 4 keer zo snel.
Maar het probleem kleiner en kleiner veel sneller.
Om dit te illustreren, zullen we praten beginnen over wat er aan de hand
wanneer we binair zoeken schrijven.
Het probleem bij de hand is, dat als ik een array van getallen,
bijvoorbeeld 1, 2, 3, 5, 7, 23, 45, 78, 12,323,
en dan 9 met een ton van 0s na,
We willen in staat zijn om erachter te komen heel snel wat er in
Deze reeks getallen.
Ik weet dat dit lijkt een beetje dom en een beetje gekunsteld,
want nu is het.
We hebben een array die niet zeer veel elementen in,
en als ik een van jullie vragen om erachter te komen of
23 is in de array, dan kunt u dat doen vrij snel
gewoon door een blik op deze en vertelde me ja of nee.
De analoge om te overwegen is denken als dit, laten we zeggen,
een Excel-spreadsheet met 10.000 rijen, 20.000 rijen.
Natuurlijk, kunt u de opdracht F of de controle F en iets opzoeken.
U kunt ook gebruik maken van de filters en de zoektocht spul,
maar als je moest door die bestand regel zien door regel voor regel,
het zou je een lange tijd om het te vinden.
Het is een beetje zoals in het telefoonboek bijvoorbeeld, ook, waar
niemand kijkt door een telefoonboek een pagina per keer.
Typisch, ze openen naar het midden,
of in het geval van veel van de telefoon boeken en woordenboeken, waar
u daadwerkelijk hebt ingetoetst op de eerste letter,
je klep om die eerste brief en openen en doorlopen daar.
>> Doet me denken aan je naam weer. >> Sam.
Sam.
Zoals Sam zegt, is dat lineaire zoekproces gaat om echt traag,
en in plaats daarvan met binair zoeken, de manier waarop dit werkt is dat
elke keer als we gaan door een iteratie van onze zoeken algoritme,
we gaan naar de lijst te verdelen in de helft, in wezen,
in twee kleinere lijsten.
En dan op de volgende iteratie van de lus, zullen we weer verdelen
in andere kleinere lijsten.
Zoals u kunt zien, blijft het probleem steeds kleiner en kleiner
omdat we houden weggooien helft van de lijst elke keer weer.
Hoe werkt deze aftrek zijn werk?
Even ter herinnering, wat we gaan doen als we een computer
en we waren, zeggen, op zoek naar de nummer 5 in deze lijst
is dat we zouden kies een nummer in het midden.
In het midden van deze lijst, omdat er 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 nummers,
we halen het nummer tijdens de 4e positie of op de 5e positie,
en noemen we dat het midden van onze lijst.
Kies aantal in het midden.
Dan, net zoals Sam zei, zullen we testen om te zien of dat aantal is gelijk
om het nummer dat we willen krijgen of onze gewenste nummer.
Als het gelijk, dan hebben we het gevonden. We winnen.
Als het niet gelijk zijn, dan zijn er een paar gevallen.
De twee gevallen zijn ofwel het aantal moet groter zijn dan het aantal waar we naar kijken,
of het is minder dan.
Als het groter is, gaan we naar rechts.
En als het minder, gaan we naar links.
En dan hebben we herhalen het hele proces
op de rechtse helft of de linkerhelft van de lijst.
>> Het eerste probleem in rubriek van vandaag is om erachter te komen
hoe kunnen we daadwerkelijk beginnen om dit uit te drukken in C-code.
We hebben de pseudocode hier.
Wat we gaan doen is Ik trek een gloednieuwe ruimte,
bewaar deze herziening, zodat we deze notities voor later,
we verwijderen dit alles, en dan kopiëren en plakken vanuit het probleem set
deze informatie in onze ruimtes, en hopelijk niet breekt.
Perfect.
Als jullie allemaal doen, kopiëren en plak deze code in uw nieuwe ruimte,
in een blanco kaart.
Laten we proberen Daniel. Als je compileren en uitvoeren van dit programma, werkt het?
Nee. >> Wat zegt het?
Het zegt dat de controle bereikt einde van niet-void functie.
Ja, dus laat me proberen het runnen van het.
Hebben jullie dit eerder gezien? Weet je wat dit betekent?
Oke, laten we ontleden dit een beetje.
Het zegt op file.c op lijn 9, kolom 1 hebben we een fout hebben, net zoals je zei,
en het zegt dat het is als gevolg van de fout waarschuwing en de return type waarschuwing.
Het lijkt erop dat er iets aan de hand is met de terugkeer type, wat logisch is.
We hebben een niet-leegte functie gekregen, wat betekent dat we een functie hebben
dat niet ledig terugkeren.
Een leegte functie is er een die er zo uitziet:
leegte foo (), en het is nietig omdat de return type is nietig,
wat betekent dat als we hier iets
zoals return 1, zouden we een compiler error voor.
We hebben echter een niet-void functie.
Onze niet-void functie is in dit geval onze zoekfunctie
omdat het een return type van de bool.
Wanneer het zegt dat de controle na een non-void functie bereikt,
het is omdat zoekopdracht heeft geen return-statement.
Het is niet wat terugstuurt van het type bool.
>> We kunnen vaststellen dat, en wat doen jullie denken
zoek moeten terugkeren standaard?
Wat moet de standaard return waarde van search zijn?
Want dat is wat we kunnen aan het eind.
Charlotte, heeft u-?
Waar of niet waar? >> Waar of niet waar.
Welke?
False. Ik weet het niet.
False? Laten we het eens proberen.
Waarom zeg je return false? Dat is geweldig intuïtie.
[Charlotte] Ik weet het niet.
We gaan valse terug te keren in dit geval, want dit zal onze verzuim
als om wat voor reden dan ook de lijst leeg is of de naald
dat we op zoek naar bestaat niet.
Dan aan het einde, als we niet echt eerder terug in deze functie,
we altijd weten dat deze functie zal zeggen nope, het is niet in de array.
Het is niet in de hooiberg.
Als we nu samen te stellen en voer het uit-laat me bewaar deze zodat we kunnen trek het omhoog.
Als we nu samen te stellen en uit te voeren ons programma, het bouwt.
We krijgen onze kleine prompt.
Als ik sloeg 4-uh-oh.
Het zag er niet uit te printen niets. Het lijkt erop dat alles eindigde in orde.
We moeten dit in te vullen inch
We spraken over het algoritme in pseudocode een beetje geleden.
Laat me eens kijken, sla dit,
en Ik trek dat algoritme weer omhoog.
Laten we gaan deze kerel. Nope.
Daar is het.
Hoe gaan we dit doen?
Wat zou een goede strategie bij het wegrijden deze code zijn?
Je moet een nummer in het midden te kiezen.
Hoe kunnen we een aantal plukken in het midden van een array?
Eventuele suggesties?
[Student] strlen gedeeld door 2.
Strlen gedeeld door 2. Dat is een goeie.
Strlen werkt met speciale soorten arrays.
Welke soorten arrays?
String arrays, karakter arrays.
Het is dat dezelfde soort concept dat we willen toepassen,
maar we kunnen geen gebruik maken van strlen omdat we niet beschikken over een array van karakters.
We hebben een scala aan ints.
Maar wat betekent strlen krijgen voor ons?
Weet je wat het wordt voor ons?
[Student] strlen brengt ons de lengte.
Precies, het wordt ons de lengte.
Strlen krijgt de lengte van de array voor ons.
>> Hoe krijgen we dat in onze binary search programma?
Hoe zou je de lengte van een array?
[Student] strlen?
U kunt de lengte van een juist geformatteerd C snaar array met strlen.
Het probleem is echter dat we niet beschikken over een string array.
Als we terugkijken naar deze code, hebben we dit integer array.
Hoe weten we hoe lang het is?
[Student] Is er een equivalent een voor eindpunt, zoals int l of zo?
Het blijkt dat er eigenlijk niet is, en dus in zekere zin is dit
een van die dingen die gewoon goed om te weten over C,
dat er geen manier om de lengte van een array te krijgen
Als alles wat ik geven is de array.
De reden dat het werkt met strijkers, de reden strlen werken,
is omdat als een string is juist geformatteerd,
zal hebben dat de speciale \ 0 karakter helemaal aan het eind.
>> U kunt ook voorstellen dat als u een onjuist opgemaakte tekenreeks
en er is er geen \ 0 karakter, dan is het hele ding werkt niet.
[Student] kunt u de \ 0?
We kunnen in dit geval.
We kunnen toevoegen een soort van \ 0
of een soort van betekenende karakter en gebruik die.
Maar dat is niet helemaal gaat werken
omdat de \ 0 is voor een char type,
en hier hebben we ints.
Het andere ding is als we een speciale waarde te gebruiken
zoals -1 tot het einde van een array markeren
dan kunnen we slaan nooit een -1 in onze integer arrays.
We zouden worden geplakt.
Het blijkt dat de enige manier om de lengte te krijgen
van een array in C daadwerkelijk onthouden
wanneer u het op en leid deze rond met de array
zodat wanneer ik een functie die gaat wat werk te doen
op een array van gehele getallen of vlotters of dubbelspel of wat dan ook,
Ik moet ook de functie geven array lengte,
en dat is precies wat we hier hebben gedaan in de zoekfunctie.
Als je kijkt, wat we gedaan hebben toen we langs in ons aanbod hier,
we ook langs de lengte, de grootte.
Het gebeurt gewoon dat we deze variabele hier genoemd,
deze parameter of argument.
Dit heet een functie het argument van lijst of lijst met parameters,
en deze worden ook wel argumenten of parameters.
Mensen gebruiken verschillende termen op verschillende tijdstippen.
Ik heb soms verwisselen ze zelf.
Het is gewoon zo gebeurt het dat deze variabele hier eveneens wordt genoemd
deze # hier te definiëren op.
Maar ze zijn niet hetzelfde.
De kapitalisatie er wel toe doet.
>> Als je kijkt naar wat hier gebeurt, verklaren wij
onze int array, die we hebben nummers.
We hebben gezien dat onze omvang, wat overeenkomt met onze # up definiëren aan de top.
Het gaat worden 8.
En dan, als we dan contact op met onze zoekfunctie beneden,
passeren we het aantal willen we zoeken, die we hebben gevraagd,
gekregen van de gebruiker.
We geven in het array, deze getallen,
en dan ook geschieden in de grootte van de array,
en dan de waarde van de maat 8 wordt opgeslagen
of doorgegeven aan deze integer variabele genaamd grootte.
Wij hebben de grootte van de matrix.
Als we nu terug gaan naar waar we het over vroeger,
Ik denk dat Missy bracht het punt dat wat we moesten doen is de lengte van de array
en deel dit door 2, en dat geeft ons het middelpunt.
Laten we eens kijken.
Kan ik iemand dit schrijf en sla het op in hun ruimte?
Hoe zit het met Leila?
Kan ik u dit schrijf in?
Schrijf de eerste regel waar u de lengte van de array en krijg het midden
en bewaar deze op een nieuwe variabele.
Ik geef je een paar seconden. Bent u er klaar voor?
[Student onverstaanbaar]
Tuurlijk, had ik bereken je het middelpunt
van de hooiberg reeks in de zoekfunctie
waarbij de lengte van de hooiberg array, ter grootte variabele?
Niets lastig hier.
[Leila] het juiste formaat / 2 en just-
En sla het op en druk op de knop Opslaan hier aan de top,
en we trek het omhoog.
Perfect.
Daar gaan we dan. Awesome.
>> Zoals zal dit compileren?
[Leila] Nee, het moet hoger zijn.
[Nate] Ja, dus wat moeten we doen?
[Leila] Net als int midden of iets dergelijks.
Awesome. Ja, laten we dat doen, int midden = grootte.
Zal dit samen te stellen?
Laten we verwijderen deze reactie en krijg het uit de weg.
Wat zal niet compileren over dit?
We doen iets met integer,
dus we moeten het of iets dergelijks af te drukken.
Ja, precies.
We krijgen een ongebruikte variabele.
Wat is niet van plan om te werken over dit?
Ik denk dat je iets zei, Sam. Puntkomma's.
Ja, ik mis die puntkomma's.
Het gaat om een ​​constante ding in de loop van de termijn.
Het laatste wat ik zal doen is zal ik wat witte ruimte op beide zijden
van deze operator hier, want die typisch is hoe we het doen
volgens onze stijlgids.
We hebben het middelpunt van ons aanbod.
Nu als we ons herinneren terug naar ons algoritme,
wat was de tweede stap die we moesten doen als we hebben het midden?
[Student] Als het groter is [onverstaanbaar].
Ja, dus we moeten een soort van vergelijking te doen, en wat gaan we vergelijken hier?
Je zei dat als deze groter is dan. Wat is het in die zin met betrekking tot?
Het nummer dat verschijnt, als dat hoger is dan het middelpunt, ga dan naar de array?
Precies, dus het nummer dat komt als we-
De naald, dus we zijn in vergelijking met de naald,
en wat gaan we het vergelijken met de naald?
Omdat de naald is wat we zoeken.
We zijn te vergelijken met naar het midden.
>> Maar heeft het zin om te controleren om te zien
indien de nld = midden?
Is dat logisch?
Heeft iemand het niet eens?
Laten we het eens proberen, als (naald == middelpunt).
[Student] Heb printf je het gevonden hebt.
[Nate] printf ("We vonden het \ n");
Anders-Ik ga om te beginnen met iets anders te doen hier.
Ik ga beginnen met het opzetten accolades om if-statements de hele tijd
alleen maar omdat als we voegen meer spullen, dan
krijgen we niet de samenstellers.
Ja, Sam. Je hebt een punt.
Het probleem is dat een positie midden in de array vertegenwoordigt,
maar je kunt het om de waarde in die positie van de array te vertegenwoordigen.
Dat is een groot punt.
Heeft iedereen horen wat Sam zei?
Hij zei dat middelpunt zoals
vertegenwoordigt slechts een positie in het stelsel, maar het is niet de werkelijke element in de array.
Als u denkt over de code in zoals geschreven op dit moment,
als we kijken naar deze array hier beneden, die heeft 8 elementen in,
wat is de waarde van de midden gaat worden in deze functie?
[Student] 4.
[Nate] 4.
Als we kijken naar het aantal 4 -
en we kunnen alleen nog maar deze code en zet een beetje verdrietig gezicht in hier
omdat we het niet vinden, als we deze code uitvoert
zoals op dit moment, uploaden, gebouw, laat me naar beneden scrollen,
en als we kijken naar het getal 4,
we vonden het, maar we hebben dit niet naar printf ja.
Een van de redenen is dat we niet echt terug,
maar hebben we echt vinden de nummer 4?
En Sam is geen zegt.
Wat hebben we gevonden?
We hebben echt gevonden het midden, die, als we kijken naar de array hier beneden,
het gaat om het element te zijn bij index 4 dat we kijken naar,
die 23.
>> Hoe kunnen we daadwerkelijk krijgen dat element in het midden
en niet alleen het middelpunt zelf?
[Student] Wij zouden invoeren char of zo?
Wat zou dat te doen, gewoon uit nieuwsgierigheid?
Kunt u ingaan iets meer zijn?
U de positie zetten in het aantal,
dus je hebt te maken een connectie-Ik denk dat het char is, maar het is misschien niet.
Ja, dat is een goed punt.
We doen veel van dit omzetten van posities in tekens, deze tekens,
in de eerste twee sets probleem.
Het blijkt dat hier, dit is bijna gelijk aan
toegang te krijgen tot de i-teken in een tekenreeks, als dat zinvol is.
Hier willen we het middelpunt element te openen.
Hoe doen we dat?
Kevin, heb je suggesties hoe we dat doen?
Je zou hooiberg te doen, open beugel, mid, gesloten beugel.
Kun je schrijven dat voor ons?
Sla het op in hier, en we zullen dat omhoog te trekken.
We kijken naar deze lijn 9,
en we beseffen dat we niet willen om de naald te vergelijken met het middelpunt,
maar in plaats daarvan willen we de naald te vergelijken
om het element op positie midden in onze hooiberg array.
Cool.
Daar gaan we dan.
Ja, dat ziet er goed uit, als (naald == hooiberg [midden]).
We vonden het.
Als we nu lopen de code-we zullen een back-up een beetje-
stelt zij, het loopt, en nu als we kijken voor 4,
we vonden het niet want nu we daadwerkelijk krijgen van het nummer 23.
We krijgen de waarde 23, en dat is wat we in vergelijking met onze naald.
Maar dat is goed. Dat is een stap in de goede richting.
>> Dat is wat we proberen te doen.
We proberen niet om de naald te vergelijken met posities in de array
maar tegen de feitelijke elementen in de array.
Als we terugkijken nu weer bij de volgende stap in ons algoritme,
wat is de volgende stap?
Leila al zagen kort.
[Student] Controleer om te zien of het is groter dan of kleiner dan en dan beslissen welke manier om te bewegen.
[Nate] Ja, zou dus hoe we dat doen?
Kunt u in een aantal-Ik sla deze herziening,
en dan als je in een aantal lijnen die zal dat doen.
Ja, Charlotte. >> Ik heb een vraag.
Mocht het niet midden - 1 omdat de eerste is
het is 0 geïndexeerd, dus als we 4 plaatsen, dat is eigenlijk niet het karakter die we zoeken?
Ja, en het andere probleem dat-
dat is een grote vangst, want wat gaat uiteindelijk gebeuren mogelijk
als we in beweging blijven en we niet ooit in eerste instantie aan te passen?
Ik denk dat wat we zouden kunnen eindigen doen is proberen om toegang te krijgen
het element op de 8e positie van de array,
die in dit geval bestaat niet.
We willen een soort van boekhouding te doen voor het feit
dat hebben we een aantal nul indexering.
[Charlotte] Sorry, ik bedoelde midpoint - 1 in de vierkante haken.
We kunnen dat doen.
We komen terug op deze kwestie in slechts een beetje.
Als we eenmaal beginnen te krijgen om de werkelijke looping,
dat is wanneer we echt zien dit in het spel komen.
Voorlopig kunnen we dit doen, maar je hebt helemaal gelijk.
Dat nul indexering zal een effect hebben dat we moeten verantwoorden.
Laten we eens kijken.
>> Hoe is het groter dan en kleiner dan-?
[Student] Ik krijg hoe de groter dan en kleiner dan deel te doen.
Ik was niet zeker wat te drukken als u vindt dat het minder is dan de hooiberg midden of groter dan.
Hier kan ik redden wat I've-
[Nate] Ja, als je bespaart wat je hebt, en we trek het omhoog.
Daar gaan we dan.
[Student] En ik vraagtekens gezet voor wat ik niet wist.
[Nate] Dat ziet er geweldig uit.
Hier hebben we vraagtekens, want we weten nog steeds niet
wat we gaan helemaal nog doen.
Wat zouden we willen-doen oeps, we hebben een aantal beugels alle funky op ons.
We corrigeren deze braces.
Daar gaan we dan.
En dus wat willen we doen, volgens ons algoritme,
als we niet vinden de naald?
Zeg in het geval dat de naald is minder dan wat we kijken. Kevin.
Kijk alleen naar de linker helft.
Juist, dus zetten we een reactie hier die zegt: "kijk naar linker helft."
En als de naald groter is dan de hooiberg in het midden, wat we willen doen?
[Student] Dan moet je kijken naar de rechter helft.
Kijk naar de rechter helft, "kijk naar rechter helft."
Not too shabby.
Oke, dus op dit punt, dingen ziet er goed uit.
Het probleem met de code geschreven is wat?
[Student] Je hoeft niet eindpunten voor de helften.
Juist, we hebben niet eindpunten voor de helften.
We zijn ook alleen maar om te gaan door deze ene keer.
We alleen maar kijken naar een middelpunt.
Ofwel het element is er, of het is het niet.
Om dit te voltooien, moeten we een soort van herhaling doen.
We moeten blijven herhalen totdat we zien dat
ofwel het element is daar, want we hebben teruggebracht en eindelijk gevonden,
of het is er niet in want we hebben keek door alle van de dingen
in de juiste helften van de array en dat niets in.
>> Wanneer we nog hebt deze herhaling aan de hand, wat gaan we gebruiken?
[Student] Een lus.
Een soort lus. Ja.
[Student] Kunnen we doen een do-while-lus en laat het dat doen en dan tijdens het
de naald is niet gelijk aan-ik ben niet zeker waar ik heen ging met dat.
Maar een soort doen zolang het niet gelijk aan de waarde die de gebruiker input.
Ja, dus laten we eens kijken, hoe kan dit schrijven zelf?
Je zei dat we gebruik maken van een do-while-lus.
Waar komt de doe start?
[Student] Direct na de grootte / 2.
[Nate] Oke, en wat gaan we doen?
We zullen later de tijd.
Wat gaan we doen?
[Student] Niet willen we alle spullen hebben we in de als deel?
[Nate] Doe dit allemaal, geweldig.
Kopiëren en plakken.
Oh, man.
Laten we eens kijken of dit werkt, als we kunnen tabblad dit over.
Prachtig.
Oke, en besparen we dit zodat jullie het hebben.
Oke, en we gaan dit doen terwijl-
wat was de conditie terwijl je zoekt?
[Student] Terwijl de naald niet gelijk doet, dus als het uitroepteken.
Maar ik weet niet precies wat dat nog is.
[Nate] Ja, dit is een manier om het te doen.
Sam, heb je een reactie achterlaten?
[Sam] Ik herinnerde me toen ik keek naar de video's,
Ik nam een ​​screenshot van een van de-achtige toen we de pseudocode voor het,
was er een relatie tussen de max. en min..
Ik denk dat het iets als als max is steeds minder dan min.
Ik heb het.
[Sam] Of als als max is niet minder dan min of iets dergelijks,
want dat zou betekenen dat je alles doorzocht.
>> Ja, dus wat klinkt het max en min verwees naar?
[Sam] Waarden die-gehele getallen die gaan veranderen
ten opzichte van waar we het middelpunt.
Precies.
[Sam] Op dat moment gaat het om [onverstaanbaar] berekenen de max en min.
Middelpunt is dit max en min idee.
Heeft dat zin om mensen?
Als we gaan kijken naar hoe we dit gaan iteratie te doen,
je bent helemaal gelijk dat we willen een soort van do-while-lus te gebruiken.
Maar ik denk dat als we ons herinneren wat er op de plaats van deze array
en wat er daadwerkelijk gebeurt-Ik ga schrijven hier-
bij de eerste iteratie van binair zoeken, hebben we-
Ik ga naar b en e te gebruiken om het begin aan te duiden.
En dan het einde van ons aanbod.
We weten dat het begin ligt op 4 recht over hier,
en we weten dat het einde is bij 108.
Zeggen dat we op zoek naar het nummer 15.
De eerste keer dat we dit doen, zoals we eerder zagen,
het middelpunt is ofwel gaat worden 16 of 23
afhankelijk van hoe berekenen we dingen uit.
Sinds gelijkmatig te verdelen in het midden zou ons deze ruimte
tussen 16 en 23, kunnen we niet gelijkmatig verdelen
of verdeel het en krijgen op een echte middelpunt.
We kijken naar 16.
We beseffen: "He, 16> 15, dat we op zoek zijn."
Om vervolgens naar de linkerhelft van de array
wat we uiteindelijk doen is zich ontdoen van
deze gehele bovenste gedeelte
en zegt: "Oke, nu onze eindpunt gaat om hier te zijn."
De volgende iteratie van onze lus, we nu kijken naar deze array,
effectief te hebben weggegooid dit deel, want nu
Als we nemen het midden van het verschil tussen het begin en het einde zijn,
vinden we onze middelpunt te zijn 8,
die we kunnen dan testen 8 om te zien waar het in verhouding tot het aantal die we zoeken,
15, vinden dat 15 groter is,
zodat we naar rechts deel van de lijst,
waarvan we weten dat omdat we mensen, en we kunnen het zien.
We weten dat het rechter gedeelte gaat worden waar we het vinden,
maar de computer niet weet dat, dus wat we zullen doen is zullen we eigenlijk
hebben deze omhoog gaan, en nu het begin en het einde
zijn dezelfde plek, zodat het midden wordt het enige nummer in de lijst op dat moment,
die is 15, en we hebben het gevonden.
Is dat enig licht werpen op waar dit hele max en min-notatie gaat,
het bijhouden van de eindpunten van de array om erachter te komen
hoe om dingen te beperken?
>> Wat zou er gebeuren als dit niet gelijk aan 15 nu?
Wat als we waren op zoek naar 15 en in plaats daarvan dit nummer waren ook 16?
Wij zouden zeggen: "Oh, het is groter.
We willen om terug te gaan naar links. "
En we gaan onze e naar rechts,
op welk punt we een eindpunt dat zou tegenstrijdig.
Het zou niet mogelijk om te zoeken naar meer elementen
want nu hebben we onze eindpunt en ons begin punt,
onze max en onze min, zijn nu omgedraaid.
Wij zoeken in de volledige array. We kunnen niets vinden.
Dat is het punt waarop we zouden willen zeggen: "Oke, we gaan dit algoritme te stoppen.
We hebben niets gevonden. We weten dat het niet hier. "
Hoe gaat dit?
[Student] Hoe precies is de computer schakelt het einde?
Hoe werkt het eind eindigen vóór het begin?
Het einde eindigt vóór het begin
als gevolg van de wiskunde die we gaan elke keer dat we dit doen doen.
De manier waarop we ruilen is als je kijkt naar de eerste keer dat we deze swap te doen
waar we het begin bij 4 en het uiteinde
helemaal bij 108 en onze middelpunt, bijvoorbeeld op 16 -
Ik ga dit terug te zetten naar 15-als we op zoek naar de 15,
wisten we dat wat we deden toen we de 16 en zag dat het groter was
en wilde de gehele rechter gedeelte van de lijst te verwijderen,
zagen we dat wat we wilden doen is deze e bewegen hier.
Effectief, werd de e verplaatst naar een voor het midden.
Ook toen we deze iteratie van het algoritme
en het middelpunt was 8,
vonden we dat 8 <15, dus we wilden de b te verplaatsen
een voorbij het midden.
Nu het begin en het einde worden samen in dit 15.
>> Als we er gebeurd om te zoeken naar een andere waarde, niet 15,
of indien dit 15 had plaats geweest 16,
zouden we hebben gevonden dat de e willen we een verplaatsen voordat het middelpunt.
Nu de e zou er omgedraaid minder dan de b.
Laten we lopen door de manier waarop we eigenlijk omhoog beëindigen codering dit algoritme.
We weten dat we willen dit middelpunt berekening hebben.
We weten ook dat we willen het begin en het einde van de array te volgen
van onze huidige array, zodat we kunnen achterhalen
waar dit linkerhelft van de lijst is en waar de rechter helft van de lijst is.
Dat doen we met ofwel beginnen en eindigen,
of we kunnen noemen ze min en max.
Ik gebruik beginnen en eindigen deze keer.
Wanneer we beginnen, als we kijken terug op ons voorbeeld hier beneden,
ons begin was ingesteld op het begin van de array, als natuurlijke.
Wat index was dit? Wat moet onze beginnen te worden?
Daniel.
[Daniel] Hooiberg [0].
[Nate] Ja, dus we konden stel deze gelijk aan hooiberg [0].
Het probleem is echter dat dit geeft ons niet de positie van het eerste element.
Het geeft ons de index van het eerste element of de werkelijke waarde op dat eerste positie.
[Student] Dat zal converteren naar 0,20?
[Nate] Wat dit zal doen is, nou ja, het zal geen schade omzetten.
Wat het zal doen, is het een 4 op te slaan in beginnen,
en dan zal het moeilijk zijn om vergelijkingen te maken tegen beginnen
omdat Begin wordt die de waarde van 4
die het begin van de array,
maar we willen de indices in de array te volgen
in tegenstelling tot de waarden.
We zullen daadwerkelijk gebruik maken van een 0, als dat.
Voor het einde van de array-Charlotte bracht dit een beetje eerder.
Dit is waar we rekening houden met de nul indexeren.
>> Charlotte, wat is het einde van de array?
Wat is de index van het einde?
[Charlotte] Size - 1.
Ja, en welke maat moeten we gebruiken?
Moeten we gebruik maken van het kapitaal grootte of kleine letters maat?
Kapitaal grootte.
In dit geval kunnen we de hoofdletter grootte.
Als we wilden deze functie om draagbaar
en gebruik deze functie in andere programma's,
kunnen we daadwerkelijk gebruik maken van kleine omvang.
Het is ook goed.
Maar Charlotte is helemaal gelijk dat we willen omvang hebben - 1.
Op dit punt-
[Student] Hoe komt het dat u kunt gebruiken hoofdletters maat?
Hoe komt het dat we kunnen gebruiken hoofdletters maat?
Het blijkt dat deze # definieert zijn echt,
onder de motorkap, een tekst zoals zoeken en vervangen, als dat zinvol is.
Wanneer u uw code te compileren, de voorbewerking fase
de compiler doorloopt het bestand
en het ziet er voor overal dat u het kapitaal formaat geschreven,
en het vervangt de tekst letterlijk met een 8, net als dat.
In die zin is dit heel anders dan een variabele.
Het neemt niet elke ruimte in het geheugen.
Het is een eenvoudige tekst te vervangen truc.
In dit geval gaan we op maat te gebruiken.
Vanaf hier gaan we willen een soort van herhaling doen,
en we zijn op de goede weg met onze do-while-lus.
We willen iets doen tot een voorwaarde niet meer te houden,
en zoals we eerder zagen, zagen we dat deze voorwaarde
was inderdaad dat we niet het einde willen
minder dan beginnen.
>> Dit is onze stoppen toestand.
Als dit gebeurt, willen we om te stoppen en te verklaren als: "He, we hebben niets gevonden."
Om dit uit te drukken, willen we een soort van lus te gebruiken.
In dit geval zou het een do-while-lus, een lus, een while-lus?
We hebben een do-while-lus hier.
Hebben jullie dat soort aanpak?
Denk je dat we moeten een andere aanpak proberen?
Kevin, alle gedachten?
We kunnen een while-lus, omdat we weten dat een maximale
groter zijn dan min bij aanvang anyways.
Ja, dus er is geen initialisatie dat moet gebeuren.
Die do-while loops zijn groot wanneer je iets moet initialiseren
voor die tijd testen, terwijl hier
we weten dat we niet gaan houden initialiseren van zowel beginnen en eindigen
elke ronde van de lus.
We weten dat we hen willen initialiseren, controleer dan onze toestand.
In dit geval, zal ik daadwerkelijk te gaan met een simpele while lus.
Het blijkt dat do-while loops zijn vrij weinig gebruikt.
Een heleboel plekken zelfs niet leren doen terwijl loops.
Ze zijn goed voor het omgaan met input van de gebruiker, dus we hebben veel gezien van hen tot nu toe.
Maar normaal en terwijl loops zijn veel vaker voor.
Het blijkt dat deze voorwaarde als geschreven
zal niet echt doen ons veel goed, en waarom is dat?
Het spijt me, ik weet het niet je naam.
Ik ben Jerry. >> Sorry?
Is B-O-R-U-I.
Oh, oke.
Ik zie niet in je op mijn lijst.
Oh, het is omdat-oh, dat is logisch.
Heb je een idee van waarom dit while loop kan niet werken zoals bedoeld,
zoals geschreven met de aandoening?
[Jerry] Je bedoelt zoals u wilt dat alle de spullen na het in de-?
Ja, dus dat is een.
Misschien moeten we dit alles spullen in de while-lus, dat is helemaal waar.
Het andere ding dat is een beetje problematischer is echter dat deze voorwaarde niet werkt.
[Student] Je moet het omdraaien.
Juist, dus deze voorwaarde zal nooit in eerste instantie waar de manier waarop we over gepraat.
We willen iets doen tot eind <beginnen,
maar we willen iets doen, terwijl
beginnen ≤ end.
>> Er is dat omkering van de logica daar.
Ik ben schuldig aan het maken van die fouten de hele tijd.
[Student] Waarom moet het minder dan of gelijk aan?
Omdat herinner u het geval is, dat we bij
waar er slechts een element, en we waren naar beneden,
en we waren op zoek naar alleen de 15 in ons aanbod?
En ons begin en ons einde waren hetzelfde element.
We willen ervoor zorgen dat we die zaak te behandelen.
Als we een rechte minder dan,
we alleen kunnen de slag om een ​​2-element array.
Toen we eenmaal op neer dat laatste element, als dat ons element, we nooit zou vinden.
Nu hier, kunnen we precies doen zoals je zei.
We kunnen beginnen plopping spul in het midden van onze while-lus.
We kunnen plop in onze midden.
We kunnen al deze if-statements,
trek ze uit deze do-while-lus,
plop ze binnen,
schoon dingen een beetje,
en ik zal verder gaan en op te slaan deze herziening.
En op dit punt, we zijn aardig in de buurt.
Sam.
Ik denk dat je ook moet int midden hebben = maat - 1/2.
Ik heb het, grootte - 1/2.
Is er nog iets anders dat we moeten veranderen over die lijn?
Dat was een goede vangst.
>> Wat doet afmetingen doen? Zijn we steeds veranderende maat?
Om de regel als houden we de grootte te wijzigen.
We moeten het formaat te wijzigen elke keer dat we rond het gaan for-lus.
Maar vergeet niet toen we door ons voorbeeld een beetje eerder,
en we hadden het begin op 4
en het einde helemaal op bij 108?
Hoe hebben we berekenen het midden?
Waren we met behulp van de maat?
Of we gebruikten beginnen en eindigen in plaats daarvan?
Het is het verschil tussen het eind en het begin.
Precies, en hoe precies moet ik schrijven dat, Charlotte?
Gewoon het einde - te beginnen.
Je zou het niet nodig om de do - 1
omdat de - 1 is opgenomen in het einde en de reeds beginnen.
[Nate] Geweldig, je bent helemaal gelijk.
We hoeven niet te doen van de - 1, want dat - 1 is opgenomen
en rekening houden bij het initialiseren we het einde variabele.
>> Is er iets anders ik moet syntactisch doen om deze lijn logisch?
[Student] Plus te beginnen. >> Plus beginnen?
[Student] Aan het einde.
Omdat het alleen berekend helft van de lengte.
Je moet naar het begin toe te voegen.
[Nate] Wat zou dit te berekenen voor ons?
Als we denken aan het einde van deze eerste iteratie van de lus,
end gaat worden in de positie index 7.
Begin in stand 0 staat.
Vergeet niet, we zijn op zoek voor een van beide
positie 3 of positie 4.
Als we kijken naar deze wiskunde, om maar maken het een beetje meer tastbaar,
hier zet een aantal nummers, hebben we 7, 0,
dus 7 - 0, en daarna / 2
is 3 in deling van gehele getallen, dat is.
Dan hebben we nodig om en voeg dan terug onze beginnen?
Dat doen we niet in dit geval.
Op de eerste iteratie zal het goed omdat beginnen is 0.
Maar als we de vooruitgang, we doen echt alles moet gewoon
end - begin / 2.
Er is nog een andere truc hier, en dat is namelijk een van voorrang.
[Student] Moeten we haakjes?
[Nate] Precies, en dat is omdat als we niet zet deze haakjes,
dan is deze lijn zal in plaats daarvan worden geïnterpreteerd
als (eind) - (begin / 2), die we zeker niet willen.
Kijk uit voor die voorrang regels.
[Student] Waarom is het niet eindigen + beginnen?
Waarom is het niet eindigen + beginnen?
[Student] Waarom is het dat niet?
Waarom zou het +?
Ik denk dat je gelijk hebt.
[Student] Omdat het gemiddelde is?
[Nate] Einde + beginnen, je hebt helemaal gelijk.
Wow, ik ben het helemaal goofed. Je hebt gelijk.
Als we aan het doen waren de min, zouden we willen naar de achterkant te beginnen binnen toe te voegen
In dit geval, je bent heel goed dat we willen het gemiddelde van de twee te nemen,
dus we willen ze toe te voegen, in tegenstelling tot hen af ​​te trekken.
[Student] Het zou ook werken als je heb uiteindelijk - begin / 2 + beginnen.
Het zou als we dat doen, ik denk het wel.
>> Bijvoorbeeld, als we waren op zoek naar beginnen,
en we verschoven het hier
het 15.
Begint nu op positie 2.
End is op positie 7.
Als we aftrekken hen, krijgen we 5.
Verdeel dat door 2, krijgen we 2.
En dan voegen we 2 terug in,
en dat brengt ons naar de 4e positie,
die hier, het middelpunt.
[Student] Moeten we zorgen verpakking?
In welke zin hebben we nodig om te zorgen voor inpakken?
Als de som of het verschil tussen
afhankelijk van hoe we dat doen is niet een even getal.
Dan is de computer in de war raakt of wanneer het 2,5;
u naar links of naar rechts te bepalen welke het middelpunt?
Ik heb het.
Het blijkt dat met gehele divisie
we niet ooit deze floating point getallen.
We krijgen nooit de komma.
Het is helemaal weggegooid.
Als u een computer deelt twee int variabelen,
en een is 7, en de andere is 2,
krijgt u geen 3,5 als resultaat.
Het zal 3.
De rest zal worden weggegooid, dus het is effectief afronding
niet een ronde maar een verdieping, als jullie bekend bent met die in wiskunde,
waar u volledig te ontdoen van de decimale,
en dus je bent wezen afkappen het naar beneden naar het dichtstbijzijnde
Totaal posities, op het dichtstbijzijnde gehele getal.
[Student] Maar dan is dat problematisch, omdat als je een array van 7 elementen
dan is dat automatisch de 3e element uit het midden in plaats van de 4e.
Hoe gaan we daarmee om?
Het is problematisch omdat als we een serie van 7,
het zou halen de 3e plaats van de 4e.
Kunt u uitleggen een beetje meer?
[Student] Want als je 7 elementen dan de 4e element
zou het middelpunt zijn, toch?
Vergeet niet uw beoordeling over nul geïndexeerd, dat wel.
[Student] Ja, dus in stand 3. Dat zou het middelpunt zijn.
Ja.
Oh, oke. Ik zie wat je bedoelt.
Het is een beetje raar, want we wennen aan dit hele idee van
het wegwerken van decimalen.
Dat is een groot punt.
Laten we dit afmaken op.
We hebben berekend ons midden.
>> We testen om te zien of onze naald is gelijk aan de middelste waarde.
We afdrukt dat we het gevonden, maar echt, wat willen we doen in deze situatie?
We hebben het gevonden, dus we willen laten de beller weten dat we het gevonden.
We hebben een functie die een boolean getypte functie.
De manier waarop we het signaal aan de beller van onze functie die we klaar om te gaan
is dat we zeggen: "He, dit waar is."
Hoe zouden we dat doen, Kevin?
Je knikt je hoofd. >> [Kevin] Voeg return true.
[Nate] Precies, return true.
Nu, als het niet gelijk is, hoe zouden we kijken naar de linker helft?
Iemand een idee?
Stella, enig idee?
U moet een nieuwe positie voor het einde in te stellen.
Ja.
Dus moeten we positie van midden doen - het einde.
Geweldig.
We moeten een nieuwe positie in te stellen voor het einde
kijken naar de linkerhelft.
Dat was wat we over hadden voor waar
Ik ga terug naar dit voorbeeld.
Ik heb het hier beginnen, en dan heb ik het einde helemaal hier.
>> Nogmaals, als we op zoek naar 15, en onze middelpunt is op 16,
en we beseffen, "Oeps, 16 is groter.
We willen naar de linkerhelft. "
We zouden dan verhuizen het einde van de 15,
en dat doen we door het nemen van een weg van het midden
en het instellen van dat als onze nieuwe einde.
Evenzo, als we kijken naar de rechter helft, hoe zouden we dat doen?
Heeft u een idee?
[Student] Je hoeft alleen ingesteld beginnen te + 1 Midpoint.
[Nate] Grote.
En nu in het geval dat we niet alles vinden,
betekent dat je verzorgd voor ons?
Daniel, doet die krijgen verzorgd voor ons?
[Daniel] Nee.
[Nate] Als we het door de hele array en we niets vinden,
waar zou dat worden opgevangen, of moeten we zorgen voor het?
[Daniel] De while conditie.
[Nate] Ja, die tijd staat, precies.
Het zal zorgen voor het doornemen van de hele array als we niets vinden.
Dit terwijl lus zal eindigen.
We zullen nooit hebben ondervonden deze aandoening,
en we kunnen return false.
We kunnen dit ook als hier in als dit
want als dit if-statement waar is,
en onze functie zal terugkeren,
en dus zullen we in wezen af ​​te breken deze functie op dit moment
wanneer we terug waar.
Maar wat gebeurt er met deze structuur hier?
Zal dit geheel werken, of is er een logische fout in?
>> Er is enige logische fout in daar, met de manier waarop het opgezet.
Wat zou het zijn?
[Student] Waarom heb je de - en + 1s?
Dat zet ons aanbod aan onze nieuwe linkerhelft en rechterhelft.
[Student] Maar waarom zou je het niet doen zonder de - 1s en + 1s?
[Nate] We kunnen stellen dat gelijk is aan het midden?
Wat kan problematisch zijn dat?
[Student] Ik denk dat het inefficiënt is omdat je het controleren van een waarde die al zijn gecontroleerd.
[Nate] Precies, dus Sam is helemaal gelijk.
Als u het einde en het begin gelijk is aan het midden
in plaats van - 1 en + 1 reflectief,
op een bepaald punt in de toekomst zullen we uiteindelijk het controleren van het midden weer.
[Student] ben ik begonnen met de PSET, en toen had ik zoiets
waar ik vergat de + 1, en het kwam vast te zitten in een oneindige lus.
Juist, omdat op een gegeven moment dat je nooit meer gaat krijgen beginnen en eindigen
daadwerkelijk overlappen.
Cool.
Er is nog een logische fout, en dat is dat dit moet zeker
een else if.
Waarom zou dat zijn?
>> De reden is als het niet een anders als-heb je het gezien, Kevin?
[Kevin] Ja, omdat je het eindpunt aan het veranderen.
[Nate] Precies.
We veranderen het eindpunt,
en als het is geschreven als dit-we zullen maken spaties tussen-
het zal controleren dit geval.
Deze zaak, als het lukt, zal afbreken van de functie.
Dan zal dit controleren volgende zaak,
en indien dit succesvol is, zal het aanpassen eindpunt
en dan zal het verder op en controleer deze zaak.
Maar op dit punt, we willen niet dat het blijven controleren.
Gelukkig hebben we hier niet opnieuw het middelpunt,
en we weten dat dit geval niet zal slagen.
Maar we zeker willen het anders zetten als daar
ook al is dat misschien in dit geval
omdat we niet het aanpassen van het midden, zou dat een verschil maken?
Nee, omdat deze gevallen zijn exclusief.
Nogmaals, mijn fout.
Wij niet, denk ik, moet dit else if.
We kunnen het eens proberen en voer het uit en kijk wat er gebeurt.
Gebouw is een fout opgetreden.
Het is waarschijnlijk omdat ik verliet deze b en e in hier.
Moet ik nog meer van die omhoog naar de top?
Het maakt niet uit alsof het.
We uitzoomen, bouwen,
daar gaat, dus nu als we zoeken naar 15,
Ja.
Laat me zoomen
15, ja. We kunnen opnieuw draaien.
Het uploaden van de broncode, de bouw, hardlopen.
Wij kunnen zoeken naar iets als 13,
en krijgen we niet alles af te drukken, zodat het niet met de conclusie dat voor ons.
Dat is geweldig, want het is niet in onze lijst.
>> We zijn nu geen tijd meer.
Dat zal zij het voor deze week.
Bedankt voor het meedoen, en tot ziens.
>> [CS50.TV]