[Powered by Google Translate] [§ 3] [menej komfortné] 

[Nate Hardison] [Harvard University] 

[To je CS50.] [CS50.TV] 

Dobre, poďme začať. Vitajte do týždňa 4 CS50. Ak ste otvoriť webový prehliadač a otvoriť PSet 3, Scramble s CS50, budeme začať chodiť prostredníctvom sekcie otázok tam. Rovnako ako minulý týždeň, budeme pracovať v CS50 Spaces, ak budete tiež vytiahnuť, že sa rovnako, a ak budete pokračovať a navštívte tento odkaz, na ktorý som dostal tu hore. Je čas začať. Máme našu malú hi programu tu. Nič blázon. Jedna z prvých vecí, ktoré chcem urobiť s vami dnes prebrať niekoľko riešení k problému Set 1, takým príkladom riešenia, len tak môžete získať pocit, pre to, čo druhy kódu zamestnancov je písanie, aké študentov kódu ostatných píšu, a máte sa na to pozrieť, pretože viem, že je to divné keď zadáte riešenie problému nastavenie a získať pripomienky na svoje vlastné verziu, ale niekedy je to užitočné vidieť, ako ostatní ľudia robili to, najmä tie, ktoré sú pekne vyzerajúce. Pre najviac sa rozdeliť, bol som naozaj ohromený s riešením, ktoré ste produkoval. Ešte som začal hľadať na zoznam 2s Problem Set, ale v prípade, že ste niečo ako prvý, Znamená to, že nič, ale dobré veci. 

Ak sa pozriete na mojej verzii, začnime celú cestu dole na revízie 1, a budeme sa rýchlo pozrieť na riešenie Mario. Ak budete ťahať doplnila, tieto programy, ktoré budeme prezentovať sú správne. Nebolo správnosť problémy s týmito problémami, ale skôr, chceme hovoriť trochu o rôznych konštrukčných problémov , Ktoré boli použité tu. Jedna z vecí, ktorá bola zaujímavá o riešení je to, že používa tento nový konštrukt s názvom libra definovať, niekedy tiež označovaná ako hash definovať. Dovoľte mi, aby som sa zamerať na to tu. # Define umožňuje dať mená týchto čísel v programe. V tomto prípade je maximálna výška pyramídy v Mario bol 23 a skôr než dávať 23 v mojom kóde, by sme odkazujú na to, ako pevný kódovanie 23 - Namiesto toho dáva názov MAX_HEIGHT na toto číslo, tak, aby sa tu v mojom do-while môžete vlastne sa odkazovať na MAX_HEIGHT namiesto toho, aby počet 23 palcov [Študent] Aká je výhoda robiť, že? To je veľká otázka. Jedným z nich je čitateľnosť. Výhodou použitia tohto # define je čitateľnosť. Keď čítam tento kód, vidím, čo sa deje. 

Vidím v tomto stave tu testujeme pre výšku je <0, ktoré sme tiež mohol definované byť minimálna výška alebo min výška. Ďalšou výhodou je to, že som si potom prečítať zvyšok riadku vidieť že sme tiež kontrolu, aby sa ubezpečil, že výška nie je väčšia než výška max, pretože budeme pokračovať, zatiaľ čo výška je väčšia než výška max Ďalšou výhodou je, keď som vzdialite trochu sem- keď som spustiť tento program, a ja ho spustiť, povedzme, s 23 práve teraz, vám vypíše všetky riadky 23 len ako, že. Ale povedať, že som chcel zmeniť výšku max, a teraz chcem obmedziť maximálnu výšku pyramíd byť iba povedať-man, ktorý bol zdesený. # Include <stdio.h>, # define MAX_HEIGHT, a povedzme, že sme chceli nastaviť výšku 10. V tomto okamihu, všetko, čo som musel urobiť, bolo zmeniť v tomto jednom mieste. Môžem prekompilovať kód, a teraz, keď sa snažím a zadajte 12, to bude výzva ma znovu. V tomto prípade, sme iba pomocou MAX_HEIGHT raz. Nie je to tak veľký problémov ísť a zmeniť ju v cykle while, ak potrebujete. Ale v programoch, kde ste odkazujúce na rovnakej magické číslo znovu a znovu, to # define mechanizmus je naozaj šikovný pretože stačí zmeniť to raz v hornej časti súboru je zvyčajne kam ste ich uložili, a zmena presakuje cez zvyšok súboru. 

Ďalšie veci, ktoré som chcel poznamenať, v tejto úlohe, že som si myslel, vyzeral naozaj pekné, jeden bol pomenovanie premenných. Vidíte tu, že máme celočíselné premenné s názvom riadku a tzv výšku. Priestory, krížiky, to pomáha, aby sa kód trochu čitateľnejšie, robí to trochu zrozumiteľnejšie, čo sa vlastne deje. Toto je v kontraste k používaniu, povedzme, náhodná písmená alebo len hatmatilka úplne. Posledná vec, ktorú som si zdôrazniť, je, že v pre slučky, často tieto Iterator premenné, tieto pulty, ktoré používate vo vašej pre slučky, je to štandardné a konvenčné štart je buď i a potom j a potom k a ísť na odtiaľ, ak potrebujete viac premenných, a to je len konvencie. Existuje veľa dohovorov. To závisí na programovacom jazyku, ktorý používate. Ale v C, sme zvyčajne začínajú s i To nedáva zmysel používať, povedzme, alebo b v závislosti na situácii. To je to pre tento jeden. Ak teraz vytiahnuť Revízia 2, uvidíte ďalšie Mario, a toto je podobná tej druhej, ktoré sme práve videli, ale to robí niečo celkom fajn. Ak sa pozrieme v tejto sekcii tu vnútri vnútornej slučky for, že používate nejaký šialený hľadáte syntaxe tu práve v tomto odbore. Toto sa nazýva ternárnu operátor. Ak je else zhustené do jedného riadku. Podmienkou je táto časť v zátvorkách. Je to ako tvrdiť, ak j <výšky - aj - 1. A čo potom obsah, že ak blok by byť so priestor a potom obsah toho, čo iného by sa táto #. Je to v podstate priradenie priestor do tejto premennej. Je to uvedenie priestorov v obsahu bloku premenné, Ak je táto podmienka splnená, a ak podmienka nie je splnená, potom blok premenná dostane to #. A potom, samozrejme, namiesto toho, aby budovanie celý reťazec a tlač všetko von na konci toto riešenie vytlačí to jeden znak v čase. Celkom v pohode. 

Ešte pár vecí, ktoré sa pozerajú na. Budeme prejsť na chamtivý. Teraz, keď sa pozrieme na chamtivý, to prvé riešenie používa tieto # definuje celkom dosť. Máme ešte jednu konštantu definovanú pre každý z rôznych čísel v tomto programe. Máme jednu pre centov za dolár, jeden pre štvrťrok, desaťhalierniky, Nickels, a haliere, a teraz, keď sme sa posunúť nadol a kód prečítať, môžeme vidieť štandardné do-while slučky tlač všetko von. Druh jadru tohto problému bolo si uvedomil, že ste potrebovali previesť plavák, ktorý budete čítať od užívateľa na celé číslo presne si to spočítajte, a to je preto, že s plávajúcou desatinnou čiarkou, ako by sme hovorili o v prednáške krátko, to nie je možné presne vyjadriť každý jednu hodnotu na číselnej osi pretože existuje nekonečne veľa hodnôt medzi 3 a, povedzme, 3,1 i Môžete mať 3,01 a 3,001 a 3,0001, a môžete ísť ďalej. Ukázalo sa, že vždy, keď pracujete s peniazmi, si často chcete previesť do formátu integer, takže nie ste straty haliere a také veci. Robiť, že a zaokrúhlenie bol kľúč. Toto riešenie používa dokonale jednoduchý, skvelý algoritmus, ktoré znížia počet zostávajúcich centov, najprv štvrtiny, potom desaťhalierniky, potom Nickels, potom mincí, a pridávať k počtu mincí každý čas. 

Ďalším riešením, ktoré uvidíme, ako som oddialiť a ísť k revízii 4, mal veľmi podobný začiatok, ale namiesto toho používa div a mod priamo tu pre výpočet počtu centov. Toto je počet štvrtiny sa rovná počtu centov delený 25, a dôvod, prečo to funguje, je preto, že robíme celočíselné delenie, tak je to vyradenie všetky zvyšky. [Študent] Musíme ju komentovať vyhľadávania? To naozaj záleží. [Študent] Si komentovať viac než kód tu. Jo, a tak, že sú banda rôzne filozofie na túto tému. Môj osobný filozofia je, že váš kód je naozaj pravda, ako váš kód je to, čo je skutočne vykonávajúci na počítači, a tak váš kód by mal byť čitateľné a čo najprehľadnejšie, že nebude vyžadovať toľko komentárov. To znamená, že keď robíte veci, ktoré sú trochu zložitejšie matematicky alebo algoritmické, je dobré, aby sa vyjadril ty, takže môžete pridať ďalší rozmer, ďalšiu vrstvu na toho, kto číta váš kód. V týchto riešení, často sú komentované viac ťažko len preto, že Chceme byť schopní distribuovať a ľudia vyzdvihnúť a čítať je celkom ľahko. Ale určite by som sa zhodujú, že je to ťažké. [Študent] Ale v prípade pochybností, ísť ťažšie? Ak ste na pochybách, choďte ťažšie. Niektorí ľudia budú niekedy hovoria vrátenie 0, alebo niečo také. Myslím, že je to smiešne komentár. Je zrejmé, že to, čo sa deje. Nepotrebujem English mi povedať, že. Niekedy ľudia budú písať veci ako "kthxbai!" To je rozkošný, ale aj ne- že to nerobí rozdiel medzi komentovanie bodov, alebo nie. Tieto druhy komentáre sú len ha, ha. Cool. 

V tomto bode, poďme začať pracovať na probléme Nastaviť 3 časť otázok. Ak ste stlačil znova, rovnako ako u minulého týždňa, nebudeme sledovať šortky v tejto sekcii. Necháme vás chlapi, že vo svojom voľnom čase, a hovoriť o otázkach. Ale teraz v tejto sekcii sa budeme venovať trochu viac času hovorí o menej kódovacích základy ako sme to urobili minulý týždeň, a namiesto toho, budeme viac sústrediť na trochu viac teórie, tak hovorí o binárne vyhľadávanie a potom triedenie. Z tých z vás, ktorí boli po spolu s prednáškou, môže niekto dať mi rekapituláciu, aký je rozdiel medzi binárne vyhľadávanie a lineárne vyhľadávanie? Čo sa deje? Iste. Lineárne vyhľadávanie prehľadá každý prvok v triedenom zozname jeden po druhom po druhom jeden po druhom, a binárne vyhľadávacie rozdeľuje zoznam na 2 skupiny, kontroly, či klávesy hodnoty, ktoré hľadáte, je väčšia alebo menšia ako na stred hodnota že ste práve našli, a ak je to menej, ako to ide s nižším zoznamu a potom rozdelí to znovu, to isté funkcie celú cestu dole, kým sa nájde stred sa rovná hodnote samotného. Právo. 

Prečo nás zaujíma? Prečo hovoríme o binárne vyhľadávanie oproti lineárnej hľadanie? Jo. Binárne je oveľa rýchlejší, takže ak zdvojnásobíte veľkosť problému trvá ešte jeden krok, skôr než dvakrát toľko. Presne tak. To je skvelý odpoveď. Lineárne vyhľadávanie je veľmi kontrole jeden prvok v čase, a ako sme videli v prvý deň prednášky keď Dávid išiel cez jeho príklade telefónneho zoznamu a vytrhol jednu stránku z telefónneho zoznamu v čase a stále robí, že znovu a znovu a znovu, to bude trvať ho naozaj dlho nájsť nikoho v telefónnom zozname, ak, samozrejme, hľadal niekoho na samom začiatku abecedy. S binárne vyhľadávanie, môžete ísť oveľa rýchlejšie, a nie je to len dvakrát tak rýchlo alebo 3 krát tak rýchlo, alebo 4 krát tak rýchlo. Ale problém dostane menšie a menšie a menšie oveľa rýchlejšie. Pre ilustráciu, začneme hovoriť o tom, čo sa deje keď píšeme binárne vyhľadávanie. Problém po ruke, je, že keď mám rad čísel, hovoria, 1, 2, 3, 5, 7, 23, 45, 78, 12323, a potom 9 s tonou 0s po tom, chceme byť schopní zistiť, naozaj rýchlo, čo je v Toto pole čísel. Viem, že to vyzerá trochu hlúpo a trochu neprirodzený, pretože teraz je to. Máme pole, ktoré nemá veľmi veľa prvkov v ňom, a keď sa spýtam, jeden z vás prísť na to, či je alebo nie je 23 je v poli, môže to urobiť celkom rýchlo len tým, že sa pozrel na to a hovoril mi áno alebo nie. Analógový, aby zvážila, predstavte si, že by tomu tak bolo, povedzme, tabuľkového procesora Excel s 10.000 riadkov, 20.000 riadky. Samozrejme, môžete to urobiť na príkazové F alebo ovládacie F a pozrite sa niečo vymyslieť. Môžete tiež použiť filtre a vyhľadávania ďalšie veci, ale ak ste mali pozerať cez ten súbor riadok po riadku po riadku, to bude trvať vám dlho nájsť. Je to niečo ako v príklade telefónneho zoznamu, aj tam, kde nikto sa pozerá cez jedno telefónne stránku knihy naraz. Typicky, oni otvoriť do stredu, alebo v prípade mnohých telefónnych zoznamov a slovníkov kde ste skutočne to nedočkavý na prvé písmeno, preklopeniu tohto prvého písmena a otvoriť a začať prechádzať tam. 

Pripomeňte mi svoje meno znovu. >> Sam. Sam. Rovnako ako Sam povedal, že lineárny procesu hľadania bude naozaj pomalé, a namiesto toho s binárne vyhľadávanie, ako to funguje, je, že zakaždým, keď sme sa prejsť iterácie nášho hľadania algoritmu, budeme rozdeliť zoznam na polovicu, v podstate, do dvoch menších zoznamov. A potom na ďalší iterácii slučky, budeme rozdeľovať znova do iných menších zoznamov. Ako môžete vidieť, problém je čím ďalej menší a menší pretože zachovávame škrty polovicu zoznamu zakaždým. Ako to discard prácu? Rovnako ako pripomienka, čo budeme robiť, keď sme boli počítač a my sme boli, povedzme, vyhľadávame pre číslo 5 v tomto zozname je to, že by sme si vybrať číslo uprostred. V strede tohto zoznamu, pretože tam sú 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 čísel, by sme vybrať číslo buď na 4. mieste alebo na 5. pozícii, a my by sme zavolať, že uprostred nášho zoznamu. Vyberte číslo uprostred. Potom, rovnako ako Sam povedal, budeme testovať, či toto číslo sa rovná na číslo, ktoré chceme získať, alebo si požadované číslo. Ak je to rovnaké, potom sme ho našli. Vyhrali sme. Ak to nie je rovnaké, potom existuje pár prípadov. Tieto dva prípady sú buď číslo musí byť väčší ako počet tých, ktoré sa práve pozeráte, alebo je to menej než. Ak je to väčšia, sme sa presunúť doprava. A ak je to menej, sme sa presunúť doľava. A potom sme celý proces opakovať znovu buď na pravej, alebo na ľavej polovice polovice zoznamu. 

Prvý problém v dnešnom oddielu je zistiť, ako môžeme skutočne začať vyjadrovať toto v C kód. Máme pseudokódu tu. Čo budeme začať robiť je, že som si vytiahnuť úplne nový priestor, uložiť túto revíziu tak, že máme tieto poznámky na neskôr, budeme mazať, to všetko a potom skopírovať a vložiť z problémového súboru táto informácia do našich priestorov, a dúfajme, že to nepraskne. Perfect. Ak ste všetko robiť, skopírujte a vložte tento kód do nového priestoru, do prázdnu. Poďme skúsiť Daniel. Ak skompilovať a spustiť tento program, to funguje? Nie >> Čo to hovorí? To hovorí, že ovládanie dosiahne konca non-void funkcie. Jo, tak mi dovoľte skúste ju spustiť. Už ste videli toto? Viete, čo to znamená? Dobre, poďme rozobrať to trochu. Je to povedal na file.c na riadku 9, stĺpec 1 máme chybu, rovnako ako ste povedal, a hovorí, že je to vyplývajúce z chyby varovania a spiatočnej typu varovanie. Vyzerá to, že sa niečo deje s návratový typ, ktorý dáva zmysel. Máme non-void funkciu, čo znamená, že máme funkciu že nevracia neplatné. Void funkcia je ten, ktorý vyzerá takto: void foo (), a je to neplatná, pretože návratový typ je void, čo znamená, že ak by sme mali niečo tu ako návrat 1, mali by sme sa chyba kompilátora pre to. Avšak, máme non-void funkcie. Naše non-void funkcia v tomto prípade je naša vyhľadávacie funkcie pretože má návratový typ bool. Keď to hovorí, že kontrolné dosiahne koniec non-void funkcie, je to preto, že hľadanie nemá return. Nie je to vracia nič typu bool. 

Môžeme opraviť to, a čo vy na to vyhľadávanie by sa mal vrátiť v predvolenom nastavení? Aký by mal byť predvolený návratová hodnota hľadanie? Vzhľadom k tomu, že to, čo môžeme dať na koniec. Charlotte, máš nejaké-? Pravda alebo lož? >> Pravda alebo lož. Ktorý z nich? False. Neviem. False? Poďme to skúsiť. Prečo si to return false? To je skvelé intuíciu. [Charlotte] Neviem. Budeme sa vrátiť false v tomto prípade, pretože to bude náš východiskový ak z nejakého dôvodu je zoznam prázdny, alebo je ihla že sme hľadali neexistuje. Potom na samom konci, keď nemáme vráti true skôr v tejto funkcii, vždy vieme, že táto funkcia bude hovoriť Nie, to nie je v poli. Nie je to v kope sena. Teraz, keď sme sa zostaviť a spustiť to, dovoľte mi, aby som uložiť to tak môžeme vytiahnuť ho hore. Teraz, keď sme sa zostaviť a spustiť náš program, buduje. Dostaneme našu malú riadku. Ak som trafil 4-uh-oh. Nebolo vytlačiť nič. Vyzerá to, že všetko skončilo dobre. Musíme vyplniť tento palcov Hovorili sme o tom algoritmu v pseudokódu trochu skôr. Ukážte, uložte tento, a ja vytiahnuť, že algoritmus opäť prebudí. Ideme toho chlapa. Nie. Tu to je. Ako to urobíme? Čo by byť dobrá stratégia pre rozjazd tento kód? Musíte vybrať číslo uprostred. Ako sme si vybrať číslo uprostred poľa? Nejaké návrhy? [Študent] strlen deleno 2. Strlen deleno 2. To je veľký. Strlen práce s špeciálnymi druhmi polí. Aké druhy polí? String pole, pole znakov. Je to ten istý druh konceptu, ktorý chceme použiť, ale nemôžeme použiť strlen, pretože nemáme pole znakov. Máme rad ints. Ale čo strlen si pre nás? Viete, čo to bude pre nás? [Študent] strlen získa nám dĺžku. Presne tak, to bude nám dĺžku. Strlen dostane dĺžku poľa pre nás. 

Ako sme sa dostali, že v našom programe binárne vyhľadávanie? Ako by ste si dĺžku poľa? [Študent] strlen? Môžete si dĺžku správne formátovaný poľa reťazca C s strlen. Problém však je, že nemáme pole reťazcov. Ak sa pozrieme späť na tento kód, máme túto integer poľa. Ako môžeme vedieť, ako dlho to je? [Študent] Je tam ekvivalent jeden pre koncový bod, ako je int l alebo tak niečo? Ukazuje sa, že v skutočnosti nie je, a tak v istom zmysle to je jedna z tých vecí, ktoré je len dobré vedieť o C, že neexistuje žiadny spôsob, ako dostať dĺžku poľa ak všetko, čo som vám je pole. Dôvod, prečo to funguje s reťazcami, dôvod strlen práce, Je tomu tak preto, ak reťazec je správny formát, bude mať zvláštne, že \ 0 znak na samom konci. 

Môžete si tiež predstaviť, ak máte nesprávne formátovaný reťazec a nie je tam žiadny \ 0 znak tam, potom celá vec nefunguje. [Študent] Môžete pridať \ 0? My by v tomto prípade. Mohli by sme pridať nejaký \ 0 alebo nejaký znamenať charakter a potom ju využiť. Ale to nie je úplne to fungovať pretože \ 0 je pre char typu, a tu máme ints. Druhá vec je, ak by sme mali použiť špeciálne hodnotu ako -1 označiť koniec poľa potom by sme mohli po uložení -1 v našich celočíselných polí. Mali by sme byť prilepené. Ukazuje sa, že jediný spôsob, ako sa dostať dĺžku z poľa v C je skutočne pamätať keď ho nastaviť a potom prejsť okolo s poli tak, že kedykoľvek mám funkciu, ktorá to urobí nejakú prácu na pole celých čísel alebo plavákmi alebo štvorhra, alebo to, čo ste, Tiež som dať táto funkcia Array na dĺžku, a to je presne to, čo sme urobili tu v vyhľadávacie funkcie. Keď sa pozriete, čo sme urobili, keď sme sa prejsť v našom poli tu, sme tiež prejsť v dĺžke, veľkosti. Proste sa to stane, že sme nazvali túto premennú tu, tento parameter alebo argument. To sa nazýva funkcia, je zoznam argument alebo parameter zoznam, a títo sú tiež nazývaní argumenty alebo parametre. Ľudia používajú rôzne termíny v rôznych časoch. Niekedy striedať je sám. To len tak sa stane, že táto premenná je tu pomenované podobne k tomu # define tu. Ale nie sú to isté. Kapitalizácia záleží. 

Ak sa pozriete na to, čo sa tu deje, prehlasujeme naše int pole, ktoré sme len čísla. Dali sme to na našu veľkosť, ktorá zodpovedá nášmu # definovať až na vrchole. Bude to byť 8. A potom, keď sme sa potom zavolať na našu funkciu vyhľadávania dole, sme sa prejsť v počte chceme hľadať, ktoré sme vyzvaní, dostal od užívateľa. Míňame v poli, tento čísla, a potom tiež musíme prejsť vo veľkosti poľa, a potom je hodnota veľkosti 8 je uložená alebo odovzdané k tejto celočíselné premenné nazvanej veľkosti. Máme veľkosť poľa. Teraz, keď sa vrátime k tomu, čo hovorili predtým, Myslím, že Missy vychovaný myšlienku, že to, čo sme potrebovali urobiť, je dostať dĺžku poľa a rozdeliť ju 2, a že nám dá polovicu. Poďme sa pozrieť,. Môžem mať niekto napísať, a uložte ho vo svojom vesmíre? Ako o Leila? Môžem mať píšete to v? Napíšte prvý riadok, kde budete mať dĺžku poľa a získať polovicu a uložiť ho do novej premennej. Dám vám pár sekúnd. Ste pripravení? [Študent nepočuteľný] Iste, mohol som ťa vypočítať stred z Haystack poľa vnútri vyhľadávacie funkcie pomocou dĺžku Haystack poľa, čo je veľkosť variabilný? Nič zložité tu. [Leila] Len veľkosť / 2 a just- A uložiť ho, a stlačte tlačidlo Uložiť tu hore, a my vytiahnite ju. Perfect. Tam ideme. Awesome. 

Ako je, že sa to zostaviť? [Leila] No, to musí byť vyššia. [Nate] Jo, tak čo budeme robiť? [Leila] Ako int stred, alebo tak niečo. Awesome. Jo, poďme to urobiť, int midpoint = veľkosť. Bude to zostaviť? Poďme zmazať tento komentár a dostať ju z cesty. Čo sa to skompilovať o tom? Nerobíme nič s integer, takže musíme ju vytlačiť, alebo niečo také. Jo, presne tak. Dostaneme nepoužívané premenné. Čo iného sa nebude pracovať o to? Myslím, že si hovoril niečo, Sam. Bodkočiarkou. Jo, som tu chýbajú tie bodkočiarkami. Je to bude konštantná vec v celom priebehu funkčného obdobia. Posledná vec urobím je, že som si dal nejaký biely priestor na oboch stranách tohto operátora tu, pretože to je zvyčajne, ako to robíme podľa nášho štýlu sprievodcu. Máme polovicu nášho poľa. Teraz, keď si spomenieme späť do nášho algoritmu, čo bol druhý krok, ktorý sme museli robiť, keď máme stred? [Študent] Ak to je väčší [nepočuteľné]. Jo, takže musíme urobiť nejaký porovnanie, a to, čo sme porovnaním tu? Hovoril ste, že ak je väčší ako. Čo je v tejto vete na mysli? Počet, že príde, ak je to väčšie ako stredu, potom sa do poľa? Presne, tak číslo, ktoré prichádza, keď sme- Ihla, takže sme v porovnaní s ihlou, a čo sme porovnaním proti ihly? Vzhľadom k tomu, ihla je to, čo sme hľadali. Sme porovnaní sa dostať do stredu. 

Ale to zmysel skontrolovať, Ak needle = stred? Dáva to zmysel? Má niekto nesúhlasí? Poďme to skúsiť, ak (ihla == stred). [Študent] Páči printf ste ju našli. [Nate] printf ("Našli sme ju \ n!"); Inak-Idem začať robiť niečo iné tu. Chystám sa začať dávať rovnátka okolo if celú dobu len preto, že keď pridáme ďalšie veci, potom nemáme sa kompilátory. Jo, Sam. Máš pravdu. Problém je, že stred predstavuje pozíciu v poli, ale môžete dostať ktorá predstavuje hodnotu v tejto polohe v poli. To je skvelé miesto. Bolo všetci počuli, čo povedal Sam? On hovoril, že stred, ako je predstavuje len miesto v poli, ale nie je to skutočný prvok poľa. Ak si myslíte, že informácie o kóde, ako písomné teraz, Ak sa pozrieme na tomto poli sa sem, ktorý má 8 elementy v tom, čo je hodnota stred bude v tejto funkcii? [Študent] 4. [Nate] 4. Ak sa pozrieme na čísla 4 - a my môžeme len spustiť tento kód a dať trochu smutný tvár v tú pretože sme nenašli to, keď narazíme tento kód ako je teraz, nahrať, stavebniny, dovoľte mi, aby som prejdite nadol, a keď sa pozrieme na čísla 4, sme ho našli, ale my sme nedostali to printf áno. Jedným z dôvodov je to, že sme nemali vrátiť true, ale sme naozaj nájsť číslo 4? A Sam sa hovoriť nie. Čo sme zistili? Sme naozaj našli stred, ktorý, ak sa pozeráme na pole tu dole, to bude prvok na indexe 4, že sa pozeráme na, ktorá je 23. 

Ako sa vlastne dostať, že prvok v stredu a nie len stred sám? [Študent] Radi by sme zadať char, alebo tak niečo? Čo by to bolo, len zo zvedavosti? Môžete upresniť, trochu viac? Musíte zmeniť pozíciu v počte, takže musíš robiť niektoré pripojenie Myslím, že je to char, ale to nemusí byť. Jo, to je dobrá pripomienka. Robili sme veľa tohto konvertujúceho pozícií do znakov, tieto znaky, v prvých dvoch problémových súborov. Ukazuje sa, že tu je to takmer podobné prístup k Ith znak v reťazci, ak to dáva zmysel. Tu chceme získať prístup k midpoint prvok. Ako to urobíme? Kevin, máte nejaké návrhy, ako by sme mohli urobiť, že? Dalo by sa to kôpka sena, otvorený držiak, stredná, uzavretá držiak. Môžete napísať, že pre nás? Uložte ho tu, a my vytiahnuť, že až. Pozeráme sa na tomto riadku 9, a my sme si uvedomili, že nechceme porovnávať ihlu do stredu, ale namiesto toho, chceme porovnať ihlu k prvku v polohe stredu v našej Haystack poľa. Cool. Tam ideme. Jo, to vyzerá celkom dobre, ak (ihla == Haystack [midpoint]). Našli sme ho. Teraz, keď sme sa spustiť na code-Dáme späť do trochu- zostavuje, beží, a teraz keď sa pozrieme na 4, nenašli sme ho, pretože teraz sme vlastne stále číslo 23. Sme získanie hodnoty 23, a to je to, čo sme v porovnaní s našou ihly. Ale to je dobre. To je krok správnym smerom. 

To je to, čo sa snažíme robiť. Nesnažíme sa tieto ihlu proti pozícií v poli ale proti skutočných prvkov v poli. Ak sa pozrieme späť hneď na ďalší krok v našom algoritmu, aký je ďalší krok? Leila už spomenul krátko. [Študent] Skontrolujte, či je to väčšie alebo menšie ako a potom sa rozhodnúť, akým spôsobom sa pohybovať. [Nate] Jo, to by tak ako to urobíme? Môžete dať do nejakej-Ja zachrániť túto revíziu, a potom, keď dáte v niektorých liniek, ktoré budú robiť, že. Jo, Charlotte. >> Mám dotaz. Nemal by to byť stred - 1, pretože prvá vec, ktorú je je to 0 indexované, takže keď dáme 4, že to nie je v skutočnosti charakter sme hľadali? Áno, a ďalší problém s tým je- to je skvelý úlovok, pretože to, čo sa chystá skončiť sa deje možná ak budeme ďalej a my už nikdy nastaviť pôvodne? Myslím, že to, čo by sme mohli skončiť robiť sa pokúša získať prístup prvok na 8. pozícii poľa, ktorý je v tomto prípade neexistuje. Budeme chcieť urobiť nejaké účtovníctva za to, že máme nejakú nulovú indexovanie. [Charlotte] Ospravedlňujem sa, myslel som polovicu - 1 v hranatých zátvorkách. Môžeme to urobiť, že. Vrátime sa k tejto otázke v len trochu. Akonáhle začneme sa dostať do skutočnej slučky, to je, keď budeme naozaj vidieť vstupujú do hry. V súčasnej dobe, môžeme to urobiť, ale ty si úplnú pravdu. To nula indexovanie bude mať vplyv, že musíme robiť. Poďme sa pozrieť,. 

Ako je väčší ako a menšie ako-? [Študent] som si, ako to urobiť väčšie ako a menšie ako druhé. Len som si nebol istý, čo tlačiť, ak zistíte, že je to menej ako Haystack stredu alebo väčšia ako. Tu môžem zachrániť, čo I've- [Nate] Jo, ak si zachrániť to, čo máte, a my vytiahnite ju. Tam ideme. [Študent] A dal som otázniky, čo som nevedel. [Nate] To vyzerá skvele. Tu máme otázniky, pretože stále nevieme čo budeme robiť docela ešte. Čo by sme chceli robiť, pardon, máme nejaké zátvorky všetci funky na nás. Budeme opraviť tieto rovnátka. Tam ideme. A tak to, čo chceme robiť, podľa nášho algoritmu, ak nebudeme nájsť ihlu? Povedzme, že v prípade, že ihla je menšia ako to, čo sme pri pohľade na. Kevin. Len sa pozrieť na ľavej polovici. Dobre, takže budeme dať komentár tu hovorí "pozri sa na ľavej polovici." A v prípade, že ihla je väčšia ako kope sena na stredu, čo chceme robiť? [Študent] Potom sa pozriete na pravej polovici. Pozrite sa na pravej polovici, "pozri sa na pravej polovice." Nie je tak zlý. Dobre, takže v tomto bode, čo hľadáte celkom dobre. Problém s kódom písaným je to, čo? [Študent] Nemáte koncové body pre polovíc. Dobre, nemáme koncové body pre polovíc. Tiež sme sa len ísť cez to raz. Sme ešte len vo chvíli, sa pozrieť na jeden stred. Buď prvok je tam, alebo to nie je. V záujme dokončenia tohto, budeme musieť urobiť nejaké opakovanie. Musíme neustále opakujú, kým nezistíme, že buď element je tam preto, že sme zúžil a nakoniec zistil, že je, alebo je to tam nie je, pretože sme sa pozrel cez všetky veci, v príslušných polovíc pole a zistil, že nič je tam. 

Kedykoľvek sme dostali toto opakovanie deje, čo budeme používať? [Študent] slučka. Nejaký slučky. Áno. [Študent] Môžeme urobiť do-while, a mať to robiť, a potom pri ihla nie je rovné-nie som istý, kde som išiel s tým. Ale niečo ako to, že tak dlho, ako to robí nie rovnaká hodnota, ktorú užívateľ vstup. Jo, tak sa poďme pozrieť, ako to môže písať sám? Povedal si, že ideme použiť do-while. Kde sa to začalo? [Študent] Hneď po veľkosť / 2. [Nate] Dobre, a čo budeme robiť? Budeme vyplniť chvíľu neskôr. Čo budeme robiť? [Študent] Vari chceme robiť všetky tie veci, ktoré máme v prípade časti? [Nate] Do všetky tie veci, skvelé. Kopírovanie a vkladanie. Oh, človeče. Uvidíme, či to funguje, či to pôjde karta to znova. Krásne. Dobre, a šetríme to tak vy si to. Dobre, a my sa chystáme urobiť to pri- čo bolo, keď podmienka, že si po? [Študent] Kým sa ihla nie je rovné, tak ako výkričník. Ale nie som si istý, čo presne to je ešte. [Nate] Jo, to je jeden spôsob, ako to urobiť. Sam, máte napísať komentár? [Sam] som si spomenul, keď som sa pozrela na videá, Vzal som si screenshot z jedného z-ako keď sme robili pseudokódu pre to, tam bol nejaký vzťah medzi max a min. Myslím, že to bolo niečo ako keď max je stále menej ako min. Mám to. [Sam] Alebo ako keď max nie je menšia ako min alebo niečo také, pretože to by znamenalo, že ste hľadali všetko. 

Jo, tak čo to znieť ako max a min boli na mysli? [Sam] Hodnoty že-celé čísla, ktoré sa chystáte zmeniť vzhľadom k miestu, kde sme dali polovicu. Presne tak. [Sam] V tomto bode, bude to [nepočuteľné] výpočet max a min. Stred je to max a min nápad. Dáva to zmysel, aby ľudí? Ak by sme mali začať uvažovať o tom, ako budeme robiť túto iterácii, máš úplnú pravdu, že chceme použiť nejaký do-while. Ale myslím, že ak by sme si spomenúť, čo sa deje na mieste tohto poľa a čo sa vlastne deje, ja sa chystám napísať sem- pri prvom opakovaní binárneho vyhľadávania, máme- Budem používať B a E na označenie začiatku. A potom koniec nášho poľa. Vieme, že začiatok je na 4 tamto, a vieme, že koniec je na 108. Povedzme, že hľadáte pre číslo 15. Prvýkrát sme to, ako sme videli skôr, stred je buď bude 16 alebo 23 v závislosti na tom, ako vypočítať veci. Vzhľadom k tomu, rovnomerne rozdeliť v polovici by nám tento priestor medzi 16 a 23, nemôžeme rovnomerne rozdeliť alebo rozdeliť a dostať na pravej stredu. My sa pozrieme na 16. Budeme si uvedomiť, "Hey, 16> 15, ktoré sme hľadali." Potom pohľad na ľavej polovici poľa čo skončíme robí, je odhadzovať celý tento horná časť a povedal: "Dobre, teraz naše koncový bod bude tu." Ďalšie iterácie nášho slučky, sme teraz pozrieme na tomto poli, efektívne, čo ste vylúčili túto časť, pretože teraz ak budeme brať polovicu byť rozdiel medzi začiatkom a koncom, nájdeme naše stred na 8, ktoré potom môžeme otestovať 8 vidieť, kde je vo vzťahu k počtu sme hľadali, 15, zistíme, že 15 je väčšia, takže sa musíme presunúť do pravej časti zoznamu, ktoré poznáme, pretože sme ľudia, a my môžeme vidieť to. Vieme, že pravá časť bude tam, kde sme ho nájsť, ale počítač nevie, že, takže to, čo budeme robiť, je my budeme skutočne sa to ísť hore, a teraz na začiatku a na konci sú rovnaké miesto, takže stred sa stáva iba číslo v zozname v tomto bode, ktorý je o 15, a našli sme ho. Znamená to, že vrhnúť nejaké svetlo na tom, kde to celé max a min zápis sa deje, sledovanie koncových bodov pole, aby sa zistiť ako zúžiť veci dole? 

Čo by sa stalo, keby to nebolo rovné 15 teraz? Čo keď sme hľadali 15, a namiesto toho, toto číslo bolo tiež 16? Radi by sme povedať: "Ach, to je väčšia. Chceme sa vrátiť doľava. " A my by sme presunúť náš e doprava, na ktorom mieste máme koncový bod, ktorý by bol konfliktný. To by nebolo možné vyhľadať akékoľvek ďalšie prvky pretože teraz máme koncový bod a naše počiatočný bod, naša max a naše min, sú teraz prevrátený. Hľadáme cez celé pole. Nemôžeme nič nájsť. To je bod, v ktorom by sme chceli povedať, "Dobre, budeme zastaviť tento algoritmus. Nenašli sme nič. My vieme, že to tu nie je. " Ako sa to deje? [Študent] Ako presne sa počítač prepne do konca? Ako koniec skončiť pred začiatkom? Koniec skončí pred začiatkom pretože matematiky, že budeme robiť zakaždým, keď sme sa to urobiť. Spôsob, akým sme sa vymeniť, je, keď sa pozriete na prvýkrát sme urobiť swapu kde máme začiatok na 4 a koniec celú cestu dole na 108 a naše stred, povedzme, na 16 - Chystám sa obnoviť túto späť do 15 Ak hľadáme pre 15, vedeli sme, že to, čo sme urobili, keď sme skontrolovali 16 a videl, že to bolo väčšie a chcel odhodiť celú pravú časť zoznamu, sme videli, že to, čo sme chceli urobiť, je presunúť tento e tu. Účinne, dostal e dojatá k jednému pred stredom. Podobne, keď sme robili túto iteráciu algoritmu a stred bol v 8, Zistili sme, že 8 <15, a tak sme chceli presunúť b jedna minulosť stredu. Teraz, na začiatku a na konci sú obaja spoločne v tomto 15. 

Ak by sme sa deje sa pozrieť na inú hodnotu, nie 15, alebo ak je to 15 miesto toho bol 16, by sme zistili, že e chceme presunúť jeden pred stredom. Teraz e by sa tam hodil menej ako b Prejdime ako sme vlastne skončili kódovanie tohto algoritmu. Vieme, že chceme mať túto midpoint výpočet. Vieme tiež, že chceme sledovať začiatok a koniec poľa z nášho aktuálneho poľa, takže môžeme zistiť kde tento ľavá polovica zoznamu a kde pravá polovica zoznamu je. Robíme, že sa buď začína a končí, alebo môžeme im hovoriť min a max Budem používať začínať a končiť tentoraz. Keď začneme, ak sa pozrieme späť na náš príklad tu dole, náš začiatok bol nastavený na samom začiatku poľa, ako prírodné. Čo index to bolo? Čo by naše začať byť? Daniel. [Daniel] Haystack [0]. [Nate] Jo, takže sme mohli nastaviť rovná kope sena [0]. Problém však je, že tento nám nie pozíciu prvého prvku. To nám dáva index prvého prvku alebo skutočnou hodnotou v tejto prvej pozícii. [Študent] To bude konvertovať na 0,20? [Nate] Čo to bude robiť, je-dobre, nebude to robiť žiadne konverzie. Čo to bude robiť, je to uloží 4 v začatí, a potom to bude veľmi ťažké, aby sa porovnanie proti začatiu pretože begin usporiada hodnotu 4, čo je začiatok nášho poľa, ale chceme sledovať indexy v poli oproti hodnotám. Budeme vlastne používať 0, takhle. Pre ukončenie pole-Charlotte priniesla to až o niečo skôr. To je miesto, kde sa budeme brať do úvahy nulovú indexovanie. 

Charlotte, čo je koniec poľa? Čo je index na konci? [Charlotte] Veľkosť - 1. Jo, a akú veľkosť by sme mali používať? Mali by sme použiť kapitálu veľkosti alebo malými písmenami veľkosť? Capital veľkosť. V tomto prípade môže byť použitie kapitálové veľkosti. Ak by sme chceli túto funkciu je prenosný a používajte túto funkciu v iných programoch, môžeme skutočne využiť malé písmená veľkosti. Je to taky v pohode. Ale Charlotte je úplne správne, že chceme mať veľkosť - 1. V tomto bode, [Študent] Ako je to, že môžete použiť veľká veľkosť? Ako je možné, že by sme mohli použiť veľká veľkosť? Ukazuje sa, že tieto # definuje sú naozaj, pod kapotou, text ako nájsť a nahradiť, ak to dáva zmysel. Pri kompilácii kódu, predspracovanie fázy prekladača prechádza súboru, a vyzerá to všade možne, že ste napísali kapitálu veľkosti, a nahrádza tento text doslova s ​​8, rovnako ako to. V tomto zmysle je veľmi odlišné od premennej. Neznamená to však trvať nejaké miesto v pamäti. Je to jednoduchý textový nahradiť trik. V tomto prípade, budeme používať veľkosť. Odtiaľ sme chceš robiť nejaké opakovanie, a my sme na správnej ceste s našou do-while. Chceme urobiť niečo, kým podmienka neplatí už, a ako sme videli skôr, videli sme, že táto podmienka bol naozaj, že nechceme koniec byť menšia než začne. 

To je naše zastavenie stav. Ak k tomu dôjde, chceme zastaviť a vyhlásiť ako, "Hele, my sme nič nenašli." Ak chcete vyjadriť, my chceme použiť nejaký slučky. V tomto prípade, že by bolo do-while, pre slučky, zatiaľ čo slučka? Máme do-while tu. Páči sa vám chalani páči tohto prístupu? Myslíte si, že by sme mali skúsiť iný prístup? Kevin, nejaké myšlienky? Mohli by sme mať while, pretože vieme, že maximálna by boli vyššie ako min na začiatku tak ako tak. Jo, takže to nie je inicializácia, ktorá sa musí stať. Tieto do-while slučky sú skvelé, keď máte inicializovať predtým skúšanie, vzhľadom k tomu, tu vieme, že nebudeme mať reinitializing ako začať a skončiť každé kolo zo slučky. Vieme, že chceme inicializovať, potom navštívte naše podmienky. V tomto prípade, to som vlastne ísť s jednoduchým slučke while. Ukazuje sa, že do-while slučky sú používané docela zriedka. Mnoho miest ani učiť sa while. Sú dobré pre spracovanie vstupov užívateľa, takže sme videli veľa z nich tak ďaleko. Ale normálne a while sú oveľa častejšie. Ukazuje sa, že táto podmienka, ako sú písané nebude naozaj nám veľmi dobre, a prečo je to? Je mi ľúto, ja neviem, ako sa voláš. Som Jerry. >> Ľúto? Je to B-O-R-U-I. Oh, dobre. Nevidím ťa na mojom zozname. Oh, je to preto, že-oh, to dáva zmysel. Máte predstavu o tom, prečo táto while nemusí fungovať, ako bolo zamýšľané, ako je napísané s podmienkou? [Jerry] Myslíš ako chcete všetky tie veci po ňom do-? Jo, takže to je jedna. Mohli by sme dať všetky tieto veci do slučky while, čo je úplne pravdivé. Ďalšia vec, ktorá je trochu problematickejšie, aj keď, je to, že táto podmienka nebude fungovať. [Študent] Musíte odhodiť. Správne, takže táto podmienka nebude nikdy platiť spočiatku ako sme o tom hovorili. Chceme urobiť niečo do konca <začínajú, ale chceme niečo urobiť, zatiaľ čo začať ≤ koniec. 

Tam je to obrátenie logiky tam. Som vinný robiť tie chyby stále. [Študent] Prečo to musí byť menšie alebo rovné? Vzhľadom k tomu, Spomínate si na prípad, že sme sa dostali do tam, kde bol len jeden prvok, a my sme boli dole, a my sme boli pri pohľade na len 15 v našom poli? A naše začiatok a náš koniec bol rovnaký prvok. Chceme, aby sa ubezpečil, že s nimi budeme nakladať ten prípad. Ak sme rovno menší než, by sme iba možnosť, aby sa dostal na 2-elementu poľa. Akonáhle sme sa dostali až do toho posledného prvku, keby tomu tak bolo naše prvok, by sme nikdy nájsť. Teraz tu môžeme urobiť presne tak, ako si hovoril. Môžeme začať plopping veci priamo do stredu našej slučke while. Môžeme PLOP v našom strede. Môžeme si vziať všetky tieto if, vytiahnite ich z tohto do-while, PLOP je v, čisté veci sa trochu, a ja pôjdem napred a ušetrite túto revíziu. A v tomto bode, dostávame veľmi blízko. Sam. Myslím si, že tiež mať INT midpoint = veľkosť - 1/2. Mám to, veľkosť - 1/2. Je ešte niečo, čo musíme zmeniť na tejto linke? To bol dobrý úlovok. 

Čo robiť veľkosť? Sme neustále sa meniace veľkosť? V záujme zachovania riadok podobný tomuto, musíme zmeniť veľkosť. Ak máme zmeniť veľkosť zakaždým, keď sme ísť okolo slučky for. Ale pamätajte si, keď sme išli cez našom príklade len trochu skôr, a mali sme na začiatku na 4 a koniec celú cestu na 108? Ako sme vypočítať stred? Boli sme s použitím veľkosť? Alebo sme používali začať a skončiť miesto? To je rozdiel medzi koncom a začiatkom. Presne, a ako presne by som mal napísať, že, Charlotte? Len koniec - začína. Tie nebudú musieť robiť - 1 pretože - 1 bol zahrnutý do konca a začne už. [Nate] Skvelé, máš úplnú pravdu. Nemáme robiť - 1, pretože to - 1 bola zahrnutá a vyúčtované, budú pri inicializuje Koniec premennej. 

Je ešte niečo, čo musím urobiť, syntakticky, aby táto položka zmysel? [Študent] Plus začať. >> Plus začať? [Študent] Na konci. Vzhľadom k tomu, je to len počíta polovica dĺžky. Musíte pridať začať. [Nate] Čo by to spočítať pre nás? Ak budeme uvažovať o konci tejto úplne prvej iterácii slučky, end bude v polohe indexe 7. Začnite v pozícii 0. Pamätajte si, že my hľadáme buď pozícia 3 alebo 4 pozíciu. Ak sa pozrieme na tento matematike, len aby to trochu viac konkrétne, dať nejaká čísla tu, máme 7, 0, tak 7-0, a potom / 2 je 3 v celé číslo, ktoré je. Potom si musíme potom pridať späť naše začať? Nevieme v tomto prípade. Na prvom iterácii, bude to v poriadku, pretože end je 0. Ale ako sme pokrok, robíme naozaj všetko stačí end - začať / 2. Je tu ešte jedna Trik je tu, a to je práve jedna z priorít. [Študent] Potrebujeme zátvorky? [Nate] Presne tak, a to preto, že ak sa nám nepodarí dať tieto zátvorky, potom táto linka bude vykladať miesto ako (koniec) - (začiatok / 2), ktorý sa rozhodne nechceme. Dajte si pozor na tie pravidlá prednosť. [Študent] Prečo nie je koniec + začať? Prečo nie je koniec + začať? [Študent] Prečo je to tak, že? Prečo by to bolo +? Myslím, že máš pravdu. [Študent] Vzhľadom k tomu, že je to priemer? [Nate] End + začatí, máš úplnú pravdu. Wow, som totálne podelal. Máš pravdu. Ak by sme robili mínus, by sme chceli pridať začať znovu prihlásiť V tomto prípade ste veľmi správne, že chceme, aby sa priemer dvoch, tak sme si chceš pridať, ako protichodný k odpočítať je. [Študent] To by tiež fungovať, ak ste koniec - začať / 2 + začať. To by, keby sa do-myslím, že áno. 

Napríklad, ak sme sa pozerali na začiatok, a my posunul ho sem na 15. Teraz môžete začať na pozíciu 2. Koniec je na pozíciu 7. Ak odpočítame je, dostaneme 5. Rozdeľte že 2, dostaneme 2. A potom pridáme 2 späť, a že nás dostane na 4. pozíciu, ktorá je práve tu, čo je na stred. [Študent] Páči sa musíme postarať o balení? V akom zmysle sa musíme postarať o balení? Ak súčet alebo rozdiel medzi v závislosti na tom, ako to urobiť, je to párne číslo. Potom počítač dostane zmätený, či je to 2,5; sa presuniete vľavo alebo vpravo určiť, ktoré je na stred? Mám to. Ukazuje sa, že s delení, nemáme vôbec dostať tieto plávajúcou desatinnou čiarkou čísla. Nikdy sme sa desatinu. Je to úplne zlikvidovať. Ak máte počítač delenie dvoch int premenné, a jeden je 7, a druhý je 2, nezískate 3,5 ako výsledok. Bude sa 3. Zvyšok budú zahodené, tak je to skutočne zaokrúhlenie nie je bicykel, ale podlaha, ak ste oboznámení s tým v matematike, kde ste úplne zbaviť desatinné, a tak ste v podstate skracovať ju nadol na najbližšiu Vcelku pozície, na najbližšie celé číslo. [Študent] Ale potom je to problematické, pretože ak máte pole 7 prvkov potom to automaticky berie tretí prvok z stredu miesto 4.. Ako sa s tým vysporiadať? Je to problematické, pretože ak sme mali rad 7, to by som vyzdvihnúť 3. miesto 4.. Mohli by ste vysvetliť trochu viac? [Študent] Pretože ak máte 7 prvkov potom 4. prvok by byť stredom, nie? Nezabudnite svoj komentár o tom, že nula indexované, hoci. [Študent] Jo, tak v polohe 3. To by bolo na stred. Jo. Oh, dobre. Chápem, čo máte na mysli. Je to trochu divné, ako sme si zvyknúť na celej tejto predstave ako sa zbaviť desatinných miest. To je skvelé miesto. Poďme dokončiť túto hore. Sme počíta náš stred. 

Testujeme, či naše ihla rovná strednej hodnote. Sme tlač, že sme ho našli, ale naozaj, čo chceme robiť v tejto situácii? Našli sme to, a tak chceme, aby volajúci, že sme ho našli. Máme funkciu, ktorá je boolean zadaný funkcie. Ako sme signál k volajúcemu našej funkcie, ktoré sme pripravení ísť je povieme, "Hele, to je pravda." Ako by sme to robili, Kevin? Ste kývol hlavou. >> [Kevin] Pridať return true. [Nate] Presne tak, vráti true. Teraz, ak to nie je rovnaké, ako by sa pozrieme na ľavej polovici? Nejaké nápady? Stella, nejaké nápady? Musíte nastaviť novú pozíciu pre koniec. Jo. Takže musíme urobiť pozície stredu - koniec. Great. Musíme nastaviť novú pozíciu na konci pozrieť sa na ľavej polovici. To bolo to, čo sme o tom hovorili pred, kde Stále sa vracia k tomuto príkladu. Mám začať tu, a potom som sa nakoniec všetci cestu cez tú. 

Opäť platí, že ak sme hľadali 15, a náš stred je 16, a my si uvedomiť, "Oops, 16 je väčší. Chceme presunúť na ľavú polovicu. " Potom by sme presunúť koniec 15, a my, že tým, že jeden od stredu a nastavení, ktoré ako náš nový konci. Podobne, ak sa chcete pozrieť na pravú polovicu, ako by to robili? Máte nejaký nápad? [Študent] Stačí nastaviť začať midpoint + 1. [Nate] Great. A teraz v prípade, že sme nič nenájdeme, to, že sa postaral o pre nás? Daniel, to, že si postarané o nás? [Daniel] č [Nate] Ak by sme robiť to cez celé pole a my nič nenájdeme, kde by to byť postarané, alebo by sme mali postarať sa o to? [Daniel], kým podmienka. [Nate] Jo, a zároveň podmienka, presne. To sa bude starať o prechádza celé pole, ak nenájdeme nič. Tento cyklus while skončí. Nikdy nebudeme sa stretli túto podmienku, a môžeme sa vrátiť false. Môžeme tiež nechať túto možnosť, ak tu takto pretože ak túto možnosť, ak tvrdenie je pravdivé, a naša funkcia vráti, a tak budeme podstate preruší táto funkcia v tomto bode keď sa vrátime true. Ale čo sa stane s touto štruktúrou tu? Bude to fungovať úplne, alebo je tam nejaký logický chyba tam? 

Tam je nejaký logický chyba tam, s tým, ako to nastaviť. Čo by mohlo byť? [Študent] Prečo potrebujete - a + 1s? , Ktorá stanovuje našu ponuku tak, aby boli naše nová ľavá polovica a pravá polovica. [Študent] Ale prečo by nemohla to urobiť bez toho, aby - 1s a + 1s? [Nate] Dalo by sa nastaviť rovná stredu? Čo by mohlo byť problematické, že? [Študent] Myslím, že je to neefektívne, pretože máte kontrolu hodnotu, ktorá je už skontrolovať. [Nate] Presne tak, Sam je úplne pravdu. Ak sa nastaviť koniec a začne sa rovná stredu miesto - 1 a + 1 zamyslene, v určitom okamihu v budúcnosti budeme nakoniec kontrolu stred znova. [Študent] Začal som PSet, a potom som mal niečo také kde som zabudol + 1, a to uviazol v nekonečnej slučke. Jasne, pretože v určitom okamihu budete nikdy dostať začať a skončiť skutočne prekrývajú. Cool. Je tu ešte jedna logická chyba, a to je, že by to malo byť určite else if. Prečo by to mohlo byť? 

Dôvodom je, pokiaľ to nie je inak, ak-si videl, Kevin? [Kevin] Jo, pretože meníte koncový bod. [Nate] Presne tak. Meníme koncový bod, a ak je to napísané takto-Dáme aby medzery medzi- bude kontrolovať tento prípad. Tento prípad, ak sa podarí, zmizne, z funkcie. Potom to bude kontrolovať túto ďalší prípad, a ak je to podarí, upraví na koncový bod, a potom to bude pokračovať a zistiť tento prípad. Ale v tomto bode, nechceme, aby aj naďalej kontrolu. Našťastie, sme sa obnoviť polovicu tu, a vieme, že tento prípad nebude úspešná. Ale my určite chceme dať else, ak tam aj napriek tomu, že by mohol v tomto prípade pretože nie sme nastavenie stredového bodu, by to robiť rozdiel? Nie, pretože tieto prípady sú exkluzívne. Opäť, môj zlý. Nechceme, myslím, je potrebné túto else if. Môžeme to skúsiť a spustiť ho a uvidíte, čo sa stane. Budova, došlo k chybe. Je to pravdepodobne preto, že som opustil to b je a ŽP tu. Mám viac tých, ktorí sa na vrchole? To nevyzerá to. My oddialiť, vybudovať, tam to ide, takže teraz, keď hľadáme 15, Áno. Dovoľte mi, aby som Zoom 15, áno. Môžeme spustiť znova. Nahranie zdrojový kód, stavebné, beh. Môžeme hľadať niečo ako 13, a nemáme dostať niečo vytlačiť, tak to nie je zistenie, že pre nás. To je skvelé, pretože to nie je v našom zozname. 

Sme teraz oneskorene. To bude mať to pre tento týždeň. Vďaka za vstup, a uvidíme sa neskôr. 

[CS50.TV]