[Powered by Google Translate] [§ 3] [méně komfortní]
>> [Nate Hardison] [Harvard University]
>> [To je CS50.] [CS50.TV]
>> Dobře, pojďme začít.
Vítejte do týdne 4 CS50.
Pokud jste otevřít webový prohlížeč a otevřít PSet 3,
Scramble s CS50, budeme začít chodit
prostřednictvím sekce otázek tam.
Stejně jako minulý týden, budeme pracovat v CS50 Spaces,
pokud budete také vytáhnout, že se stejně,
a pokud budete pokračovat a navštivte tento odkaz, na který jsem dostal tady nahoře.
Je čas začít.
Máme naši malou hi programu zde. Nic blázen.
Jedna z prvních věcí, které chci udělat s vámi dnes probrat několik řešení
k problému Set 1, takovým příkladem řešení,
jen tak můžete získat pocit, pro to, co druhy kódu zaměstnanců je psaní,
jaké studentů kódu ostatních píší,
a máte se na to podívat, protože vím, že je to divné
když zadáte řešení problému nastavení a získat připomínky
na své vlastní verzi, ale někdy je to užitečné vidět, jak ostatní lidé dělali to,
zejména ty, které jsou pěkně vypadající.
Pro nejvíce se rozdělit, byl jsem opravdu ohromen s řešením, které jste produkoval.
Ještě jsem začal hledat na seznam 2s Problem Set, ale v případě, že jste něco jako první,
znamená to, že nic, ale dobré věci.
>> Pokud se podíváte na mé verzi, začněme celou cestu dolů na revize 1,
a budeme se rychle podívat na řešení Mario.
Pokud budete tahat doplnila, tyto programy, které budeme prezentovat jsou správné.
Nebylo správnost problémy s těmito problémy, ale spíše,
chceme mluvit trochu o různých konstrukčních problémů
, které byly použity zde.
Jedna z věcí, která byla zajímavá o řešení
je to, že používá tento nový konstrukt s názvem libra definovat,
někdy také označována jako hash definovat.
Dovolte mi, abych se zaměřit na to tady.
# Define umožňuje dát jména těchto čísel v programu.
V tomto případě je maximální výška pyramidy v Mario
byl 23 a spíše než dávat 23 v mém kódu,
bychom odkazují k tomu, jak pevný kódování 23 -
Namísto toho dává název MAX_HEIGHT na toto číslo,
tak, aby se tady v mém do-while
můžete vlastně se odkazovat na MAX_HEIGHT
místo toho, aby počet 23 palců
[Student] Jaká je výhoda dělat, že?
To je velká otázka.
Jedním z nich je čitelnost.
Výhodou použití tohoto # define je čitelnost.
Když čtu tento kód, vidím, co se děje.
>> Vidím v tomto stavu zde testujeme
pro výšku je <0, které jsme také mohl definovány
být minimální výška nebo min výška.
Další výhodou je, že se může potom přečíst zbytek řádku vidět
že jsme také kontrolu, aby se ujistil, že výška není větší než výška max.,
protože budeme pokračovat, zatímco výška je větší než výška max.
Další výhodou je, když jsem vzdálíte trochu sem-
když jsem spustit tento program, a já jej spustit, řekněme, s 23 právě teď,
vám vypíše všechny řádky 23 jen jako, že.
Ale říct, že jsem chtěl změnit výšku max,
a teď chci omezit maximální výšku pyramid
být pouze říci-man, který byl zděšený.
# Include , # define MAX_HEIGHT,
a řekněme, že jsme chtěli nastavit výši 10.
V tomto okamžiku, vše, co jsem musel udělat, bylo změnit v tomto jednom místě.
Mohu překompilovat kód, a teď, když se snažím a zadejte 12,
to bude výzva mě znovu.
V tomto případě, jsme pouze pomocí MAX_HEIGHT jednou.
Není to tak velký potíží jít
a změnit ji v cyklu while, pokud potřebujete.
Ale v programech, kde jste odkazující na stejné magické číslo
znovu a znovu, to # define mechanismus je opravdu šikovný
protože stačí změnit to jednou v horní části souboru je obvykle kam jste je uložili,
a změna prosakuje přes zbytek souboru.
>> Další věci, které jsem chtěl poznamenat, v tomto úkolu, že jsem si myslel, vypadal opravdu pěkné,
jeden byl pojmenování proměnných.
Vidíte zde, že máme celočíselné proměnné s názvem řádku a tzv. výšku.
Prostory, křížky, to pomáhá, aby se kód trochu čitelnější,
dělá to trochu srozumitelnější, co se vlastně děje.
Toto je v kontrastu k používání, řekněme, náhodná písmena
nebo jen hatmatilka úplně.
Poslední věc, kterou jsem si zdůraznit, je, že v pro smyčky,
často tyto iterátor proměnné, tyto pulty, které používáte ve vaší pro smyčky,
je to standardní a konvenční start je buď i a potom j a pak k
a jít na odtamtud, pokud potřebujete více proměnných,
a to je jen konvence.
Existuje spousta úmluv.
To závisí na programovacím jazyku, který používáte.
Ale v C, jsme obvykle začínají s i.
To nedává smysl používat, řekněme, nebo b
v závislosti na situaci.
To je to pro tento jeden.
Pokud nyní vytáhnout Revize 2, uvidíte další Mario,
a toto je podobná té druhé, které jsme právě viděli,
ale to dělá něco docela fajn.
Podíváme-li se v této sekci tady uvnitř vnitřní smyčky for,
že používáte nějaký šílený hledáte syntaxe tu právě v tomto oboru.
Toto se nazývá ternární operátor.
Je-li else zhuštěné do jednoho řádku.
Podmínkou je tato část v závorkách.
Je to jako tvrdit, pokud j <výšky - i - 1.
A co pak obsah, že pokud blok by být se prostor
a pak obsah toho, co jiného by se tato #.
Je to v podstatě přiřazení prostor do této proměnné.
Je to uvedení prostor v obsahu bloku proměnné,
Pokud je tato podmínka splněna, a pokud podmínka není splněna,
pak blok proměnná dostane to #.
A pak, samozřejmě, místo toho, aby budování celý řetězec
a tisk všechno ven na konci toto řešení vytiskne to jeden znak v čase.
Docela v pohodě.
>> Ještě pár věcí, které se dívají na. Budeme se přesunout na chamtivý.
Nyní, když se podíváme na chamtivý, to první řešení
používá tyto # definuje docela dost.
Máme ještě jednu konstantu definovanou pro každý z různých čísel v tomto programu.
Máme jednu pro centů za dolar, jeden pro čtvrtletí, desetníky, nickels, a haléře,
a teď, když jsme se posunout dolů a kód přečíst,
můžeme vidět standardní do-while smyčky tisk všechno ven.
Druh jádru tohoto problému bylo si uvědomil, že
jste potřebovali převést plovák, který budete číst od uživatele na celé číslo
přesně si to spočítejte, a to je proto, že
s plovoucí desetinnou čárkou, jako bychom mluvili o v přednášce krátce,
to není možné přesně vyjádřit každý jednu hodnotu na číselné ose
protože existuje nekonečně mnoho hodnot mezi 3 a, řekněme, 3,1 i.
Můžete mít 3,01 a 3,001 a 3,0001, a můžete jít dál.
Ukázalo se, že vždy, když pracujete s penězi, si často chcete převést
do formátu integer, takže nejste ztráty haléře a takové věci.
Dělat, že a zaokrouhlení byl klíč.
Toto řešení používá dokonale jednoduchý, skvělý algoritmus,
které sníží počet zbývajících centů, nejprve čtvrtiny,
pak desetníky, pak nickels, pak mincí,
a přidávat k počtu mincí každý čas.
>> Dalším řešením, které uvidíme, jak jsem oddálit a jít k revizi 4,
měl velmi podobný začátek, ale místo toho používá div a mod
přímo tady pro výpočet počtu centů.
Toto je počet čtvrtiny se rovná počtu centů dělený 25,
a důvod, proč to funguje, je proto, že děláme celočíselné dělení,
tak je to vyřazení všechny zbytky.
[Student] Musíme ji komentovat vyhledávání?
To opravdu záleží.
[Student] Jsi komentovat více než kód tady.
Jo, a tak, že jsou banda různé filosofie na toto téma.
Můj osobní filozofie je, že váš kód je opravdu pravda,
jako váš kód je to, co je skutečně vykonávající na počítači,
a tak váš kód by měl být čitelné a co nejpřehlednější, že nebude vyžadovat tolik komentářů.
To znamená, že když děláte věci, které jsou trochu složitější matematicky
nebo algoritmicky, je dobré, aby se vyjádřil ty, takže můžete
přidat další rozměr, další vrstvu na toho, kdo čte váš kód.
V těchto řešení, často jsou komentovány více těžce jen proto, že
Chceme být schopni distribuovat a lidé vyzvednout
a číst je docela snadno.
Ale určitě bych se shodují, že je to těžké.
[Student] Ale v případě pochybností, jít těžší?
Pokud jste na pochybách, jděte těžší.
Někteří lidé budou někdy říkají vrácení 0, nebo něco takového.
Myslím, že je to směšné komentář.
Je zřejmé, že to, co se děje.
Nepotřebuji English se mi říct, že.
Někdy lidé budou psát věci jako "kthxbai!"
To je rozkošný, ale také ne-
že to nedělá rozdíl mezi komentování bodů, nebo ne.
Tyto druhy komentáře jsou jen ha, ha.
Cool.
>> V tomto bodě, pojďme začít pracovat na problému Nastavit 3 část otázek.
Pokud jste stiskl znovu,
stejně jako u minulého týdne, nebudeme sledovat šortky v této sekci.
Necháme vás chlapi, že ve svém volném čase, a mluvit o otázkách.
Ale teď v této sekci se budeme věnovat trochu více času
mluví o méně kódovacích základy
jako jsme to udělali minulý týden, a místo toho, budeme více soustředit na
trochu více teorie, tak mluví o binární vyhledávání a poté třídění.
Z těch z vás, kteří byli po spolu s přednáškou,
může někdo dát mi rekapitulaci, jaký je rozdíl
mezi binární vyhledávání a lineární vyhledávání?
Co se děje? Jistě.
Lineární vyhledávání prohledá každý prvek v tříděném seznamu
jeden po druhém po druhém jeden po druhém,
a binární vyhledávací rozděluje seznam na 2 skupiny,
kontroly, zda klávesy hodnoty, které hledáte, je větší nebo menší než na střed hodnota
že jste právě našli, a pokud je to méně, než to jde s nižším seznamu
a pak rozdělí to znovu, to samé funkce
celou cestu dolů, dokud se najde střed se rovná hodnotě samotného.
Právo.
>> Proč nás zajímá?
Proč mluvíme o binární vyhledávání oproti lineární hledání?
Jo.
Binární je mnohem rychlejší, takže pokud zdvojnásobíte velikost problému
trvá ještě jeden krok, spíše než dvakrát tolik.
Přesně tak.
To je skvělý odpověď.
Lineární vyhledávání je velmi kontrole jeden prvek v době,
a jak jsme viděli v první den přednášky
když David šel přes jeho příkladu telefonního seznamu
a vytrhl jednu stránku z telefonního seznamu v době
a stále dělá, že znovu a znovu a znovu,
to bude trvat ho opravdu dlouho najít nikoho v telefonním seznamu,
pokud, samozřejmě, hledal někoho na samém počátku abecedy.
S binární vyhledávání, můžete jít mnohem rychleji,
a není to jen dvakrát tak rychle nebo 3 krát tak rychle, nebo 4 krát tak rychle.
Ale problém dostane menší a menší a menší mnohem rychleji.
Pro ilustraci, začneme mluvit o tom, co se děje
když píšeme binární vyhledávání.
Problém po ruce, je, že když mám řadu čísel,
říkají, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
a pak 9 s tunou 0s po tom,
chceme být schopni zjistit, opravdu rychle, co je v
Toto pole čísel.
Vím, že to vypadá trochu hloupě a trochu nepřirozený,
protože teď je to.
Máme pole, které nemá velmi mnoho prvků v něm,
a když se zeptám, jeden z vás přijít na to, zda je či není
23 je v poli, může to udělat docela rychle
jen tím, že se podíval na to a říkal mi ano nebo ne.
Analogový, aby zvážila, představte si, že by tomu tak bylo, řekněme,
tabulkového procesoru Excel s 10.000 řádků, 20.000 řádky.
Samozřejmě, můžete to udělat na příkazové F nebo ovládací F a podívejte se něco vymyslet.
Můžete také použít filtry a vyhledávání další věci,
ale pokud jste měli dívat přes ten soubor řádek po řádku po řádku,
to bude trvat vám dlouho najít.
Je to něco jako v příkladu telefonního seznamu, i tam, kde
nikdo se dívá přes jedno telefonní stránku knihy najednou.
Typicky, oni otevřít do středu,
nebo v případě mnoha telefonních seznamů a slovníků kde
jste skutečně to nedočkavý na první písmeno,
překlopení tohoto prvního písmene a otevřít a začít procházet tam.
>> Připomeňte mi své jméno znovu. >> Sam.
Sam.
Stejně jako Sam řekl, že lineární procesu hledání bude opravdu pomalé,
a místo toho s binární vyhledávání, to funguje tak, že
pokaždé, když jsme se projít iterace našeho hledání algoritmu,
budeme rozdělit seznam na polovinu, v podstatě,
do dvou menších seznamů.
A pak na další iteraci smyčky, budeme rozdělovat znovu
do jiných menších seznamů.
Jak můžete vidět, problém je čím dál menší a menší
protože zachováváme Škrt polovinu seznamu pokaždé.
Jak to discard práci?
Stejně jako připomínka, co budeme dělat, když jsme byli počítač
a my jsme byli, řekněme, vyhledáváme pro číslo 5 v tomto seznamu
je to, že bychom si vybrat číslo uprostřed.
Ve středu tohoto seznamu, protože tam jsou 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 čísel,
bychom vybrat číslo buď na 4. místě nebo na 5. pozici,
a my bychom zavolat, že uprostřed našeho seznamu.
Vyberte číslo uprostřed.
Pak, stejně jako Sam řekl, budeme testovat, zda toto číslo se rovná
na číslo, které chceme získat nebo si požadované číslo.
Pokud je to stejné, pak jsme ho našli. Vyhráli jsme.
Pokud to není stejné, pak existuje pár případů.
Tyto dva případy jsou buď počet musí být větší než počet díváme,
nebo je to méně než.
Pokud je to větší, jsme se přesunout doprava.
A pokud je to méně, jsme se přesunout doleva.
A pak jsme celý proces opakovat znovu
buď na pravé, nebo na levé poloviny poloviny seznamu.
>> První problém v dnešním oddílu je zjistit,
jak můžeme skutečně začít vyjadřovat toto v C kód.
Máme pseudokódu zde.
Co budeme začít dělat je, že jsem si vytáhnout zcela nový prostor,
uložit tuto revizi tak, že máme tyto poznámky na později,
budeme mazat, to vše a potom zkopírovat a vložit z problémového souboru
tato informace do našich prostor, a doufejme, že to nepraskne.
Perfect.
Pokud jste vše dělat, zkopírujte a vložte tento kód do nového prostoru,
do prázdnou.
Pojďme zkusit Daniel. Pokud zkompilovat a spustit tento program, to funguje?
Ne >> Co to říká?
To říká, že kontrolní dosáhne konce non-void funkce.
Jo, tak mi dovolte zkuste ji spustit.
Už jste viděli tohle? Víte, co to znamená?
Dobře, pojďme rozebrat to trochu.
Je to řekl na file.c na řádku 9, sloupec 1 máme chybu, stejně jako jste řekl,
a říká, že je to vyplývající z chyby varování a zpáteční typu varování.
Vypadá to, že se něco děje s návratový typ, který dává smysl.
Máme non-void funkci, což znamená, že máme funkci
že nevrací neplatné.
Void funkce je ten, který vypadá takto:
void foo (), a je to neplatná, protože návratový typ je void,
což znamená, že pokud bychom měli něco tady
jako návrat 1, měli bychom se chyba kompilátoru pro to.
Nicméně, máme non-void funkce.
Naše non-void funkce v tomto případě je naše vyhledávací funkce
protože má návratový typ bool.
Když to říká, že kontrolní dosáhne konec non-void funkce,
je to proto, že hledání nemá return.
Není to vrací nic typu bool.
>> Můžeme opravit to, a co vy na to
vyhledávání by se měl vrátit ve výchozím nastavení?
Jaký by měl být výchozí návratová hodnota hledání?
Vzhledem k tomu, že to, co můžeme dát na konec.
Charlotte, máš nějaké-?
Pravda nebo lež? >> Pravda nebo lež.
Který z nich?
False. Nevím.
False? Pojďme to zkusit.
Proč si to return false? To je skvělé intuici.
[Charlotte] Nevím.
Budeme se vrátit false v tomto případě, protože to bude náš výchozí
pokud z nějakého důvodu je seznam prázdný, nebo je jehla
že jsme hledali neexistuje.
Pak na samém konci, když nemáme vrátí true dříve v této funkci,
vždy víme, že tato funkce bude říkat Ne, to není v poli.
Není to v kupce sena.
Nyní, když jsme se sestavit a spustit to, dovolte mi, abych uložit to tak můžeme vytáhnout ho nahoru.
Nyní, když jsme se sestavit a spustit náš program, buduje.
Dostaneme naši malou řádku.
Pokud jsem trefil 4-uh-oh.
Nebylo vytisknout nic. Vypadá to jako všechno skončilo dobře.
Musíme vyplnit tento palců
Mluvili jsme o tom algoritmu v pseudokódu trochu dříve.
Ukažte, uložte tento,
a já vytáhnout, že algoritmus opět probudí.
Jdeme toho chlapa. Ne.
Tady to je.
Jak to uděláme?
Co by být dobrá strategie pro rozjíždění tento kód?
Musíte vybrat číslo uprostřed.
Jak jsme si vybrat číslo uprostřed pole?
Nějaké návrhy?
[Student] strlen děleno 2.
Strlen děleno 2. To je veliký.
Strlen práce s speciálními druhy polí.
Jaké druhy polí?
String pole, pole znaků.
Je to ten samý druh konceptu, který chceme použít,
ale nemůžeme použít strlen, protože nemáme pole znaků.
Máme řadu ints.
Ale co strlen si pro nás?
Víte, co to bude pro nás?
[Student] strlen získá nám délku.
Přesně tak, to bude nám délku.
Strlen dostane délku pole pro nás.
>> Jak jsme se dostali, že v našem programu binární vyhledávání?
Jak byste si délku pole?
[Student] strlen?
Můžete si délku správně formátovaný pole řetězce C s strlen.
Problém však je, že nemáme pole řetězců.
Podíváme-li se zpět na tento kód, máme tuto integer pole.
Jak můžeme vědět, jak dlouho to je?
[Student] Je tam ekvivalent jeden pro koncový bod, jako je int l nebo tak něco?
Ukazuje se, že ve skutečnosti není, a tak v jistém smyslu to je
jedna z těch věcí, které je jen dobré vědět o C,
že neexistuje žádný způsob, jak dostat délku pole
pokud vše, co jsem vám je pole.
Důvod, proč pracuje s řetězci, důvod strlen práce,
Je tomu tak proto, pokud řetězec je správný formát,
bude mít zvláštní, že \ 0 znak na samém konci.
>> Můžete si také představit, pokud máte nesprávně formátovaný řetězec
a není tam žádný \ 0 znak tam, pak celá věc nefunguje.
[Student] Můžete přidat \ 0?
My by v tomto případě.
Mohli bychom přidat nějaký \ 0
nebo nějaký znamenat charakter a pak ji využít.
Ale to není úplně to fungovat
protože \ 0 je pro char typu,
a tady máme ints.
Druhá věc je, pokud bychom měli použít speciální hodnotu
jako -1 označit konec pole
pak bychom mohli po uložení -1 v našich celočíselných polí.
Měli bychom být přilepená.
Ukazuje se, že jediný způsob, jak se dostat na délku
z pole v C je skutečně pamatovat
když jej nastavit a pak projít kolem s poli
tak, že kdykoli mám funkci, která to udělá nějakou práci
na pole celých čísel nebo plováky nebo čtyřhra, nebo to, co jste,
Také jsem dát tato funkce Array na délku,
a to je přesně to, co jsme udělali tady v vyhledávací funkce.
Když se podíváte, co jsme udělali, když jsme se projít v našem poli tady,
jsme také projít v délce, velikosti.
Prostě se to stane, že jsme nazvali tuto proměnnou zde,
tento parametr nebo argument.
To se nazývá funkce, je seznam argument nebo parametr seznam,
a tito jsou také nazýváni argumenty nebo parametry.
Lidé používají různé termíny v různých časech.
Někdy střídat je sám.
To jen tak se stane, že tato proměnná je zde pojmenovány podobně
k tomu # define tady.
Ale nejsou to samé.
Kapitalizace záleží.
>> Pokud se podíváte na to, co se zde děje, prohlašujeme
naše int pole, které jsme jen čísla.
Dali jsme to na naši velikost, která odpovídá našemu # definovat až na vrcholu.
Bude to být 8.
A pak, když jsme se pak zavolat na naši funkci vyhledávání dole,
jsme se projít v počtu chceme hledat, které jsme vyzváni,
dostal od uživatele.
Míjíme v poli, tento čísla,
a pak také musíme projít ve velikosti pole,
a pak je hodnota velikosti 8 je uložena
nebo předány k této celočíselné proměnné nazvané velikosti.
Máme velikost pole.
Nyní, když se vrátíme k tomu, co mluvili dříve,
Myslím, že Missy vychován myšlenku, že to, co jsme potřebovali udělat, je dostat délku pole
a rozdělit ji 2, a že nám dá polovinu.
Pojďme se podívat,.
Mohu mít někdo napsat, a uložte jej ve svém vesmíru?
Jak o Leila?
Mohu mít píšete to v?
Napište první řádek, kde budete mít délku pole a získat polovinu
a uložit jej do nové proměnné.
Dám vám pár sekund. Jste připraveni?
[Student neslyšitelný]
Jistě, mohl jsem tě vypočítat střed
z haystack pole uvnitř vyhledávací funkce
pomocí délku haystack pole, což je velikost variabilní?
Nic složité tady.
[Leila] Jen velikost / 2 a just-
A uložit jej, a udeřil na tlačítko Uložit tady nahoře,
a my vytáhněte ji.
Perfect.
Tam jdeme. Awesome.
>> Jak je, že se to sestavit?
[Leila] No, to musí být vyšší.
[Nate] Jo, tak co budeme dělat?
[Leila] Jako int střed, nebo tak něco.
Awesome. Jo, pojďme to udělat, int midpoint = velikost.
Bude to sestavit?
Pojďme smazat tento komentář a dostat ji z cesty.
Co se to zkompilovat o tom?
Neděláme nic s integer,
takže musíme ji vytisknout, nebo něco takového.
Jo, přesně tak.
Dostaneme nepoužívané proměnné.
Co jiného se nebude pracovat o to?
Myslím, že jsi říkal něco, Sam. Středníky.
Jo, jsem tu chybí ty středníky.
Je to bude konstantní věc v celém průběhu funkčního období.
Poslední věc udělám je, že jsem si dal nějaký bílý prostor na obou stranách
tohoto operátora zde, protože to je obvykle, jak to děláme
podle našeho stylu průvodce.
Máme polovinu našeho pole.
Nyní, když si vzpomeneme zpět do našeho algoritmu,
co byl druhý krok, který jsme museli dělat, když máme střed?
[Student] Pokud to je větší [neslyšitelné].
Jo, takže musíme udělat nějaký srovnání, a to, co jsme porovnáním tady?
Říkal jste, že pokud je větší než. Co je v této větě na mysli?
Počet, že přijde, pokud je to větší než středu, pak se do pole?
Přesně tak, číslo, které přichází, když jsme-
Jehla, takže jsme ve srovnání s jehlou,
a co jsme porovnáním proti jehly?
Vzhledem k tomu, jehla je to, co jsme hledali.
Jsme srovnání se dostat do středu.
>> Ale to smysl zkontrolovat,
Pokud needle = střed?
Dává to smysl?
Má někdo nesouhlasí?
Pojďme to zkusit, pokud (jehla == střed).
[Student] Líbí printf jste ji našli.
[Nate] printf ("Našli jsme ji \ n!");
Jinak-Jdu začít dělat něco jiného tady.
Chystám se začít dávat rovnátka kolem if celou dobu
jen proto, že když přidáme další věci, pak
nemáme se kompilátory.
Jo, Sam. Máš pravdu.
Problém je, že střed představuje pozici v poli,
ale můžete dostat která představuje hodnotu v této poloze v poli.
To je skvělé místo.
Bylo všichni slyšeli, co řekl Sam?
On říkal, že střed, jak je
představuje jen místo v poli, ale není to skutečný prvek pole.
Pokud si myslíte, že informace o kódu, jako písemné teď,
Podíváme-li se na tomto poli se sem, který má 8 elementy v tom,
co je hodnota střed bude v této funkci?
[Student] 4.
[Nate] 4.
Podíváme-li se na čísla 4 -
a my můžeme jen spustit tento kód a dát trochu smutný obličej v tu
protože jsme nenašli to, když narazíme tento kód
jak je teď, nahrát, stavebniny, dovolte mi, abych přejděte dolů,
a když se podíváme na čísla 4,
jsme ho našli, ale my jsme nedostali to printf ano.
Jedním z důvodů je to, že jsme neměli vrátit true,
ale jsme opravdu najít číslo 4?
A Sam se říkat ne.
Co jsme zjistili?
Jsme opravdu našli střed, který, pokud se díváme na pole tady dole,
to bude prvek na indexu 4, že se díváme na,
která je 23.
>> Jak se vlastně dostat, že prvek ve středu
a ne jen střed sám?
[Student] Rádi bychom zadat char, nebo tak něco?
Co by to bylo, jen ze zvědavosti?
Můžete upřesnit, trochu víc?
Musíte změnit pozici v počtu,
takže musíš dělat některé připojení Myslím, že je to char, ale to nemusí být.
Jo, to je dobrá připomínka.
Dělali jsme hodně tohoto konvertujícího pozic do znaků, tyto znaky,
v prvních dvou problémových souborů.
Ukazuje se, že zde je to téměř podobné
přístup k Ith znak v řetězci, pokud to dává smysl.
Zde chceme získat přístup k midpoint prvek.
Jak to uděláme?
Kevin, máte nějaké návrhy, jak bychom mohli udělat, že?
Dalo by se to kupka sena, otevřený držák, střední, uzavřená držák.
Můžete napsat, že pro nás?
Uložte ho tady, a my vytáhnout, že až.
Díváme se na tomto řádku 9,
a my jsme si uvědomili, že nechceme srovnávat jehlu do středu,
ale místo toho, chceme porovnat jehlu
k prvku v poloze středu v naší haystack pole.
Cool.
Tam jdeme.
Jo, to vypadá docela dobře, pokud (jehla == haystack [midpoint]).
Našli jsme ho.
Nyní, když jsme se spustit kód-Dáme zpět do trochu-
sestavuje, běží, a teď když se podíváme na 4,
nenašli jsme ho, protože teď jsme vlastně stále číslo 23.
Jsme získání hodnoty 23, a to je to, co jsme v porovnání s naší jehly.
Ale to je dobře. To je krok správným směrem.
>> To je to, co se snažíme dělat.
Nesnažíme porovnání jehlu proti pozic v poli
ale proti skutečných prvků v poli.
Podíváme-li se zpět hned na další krok v našem algoritmu,
jaký je další krok?
Leila již zmínil krátce.
[Student] Zkontrolujte, zda je to větší nebo menší než a pak se rozhodnout, jakým způsobem se pohybovat.
[Nate] Jo, to by tak jak to uděláme?
Můžete dát do nějaké-Já zachránit tuto revizi,
a pak, když dáte v některých linek, které budou dělat, že.
Jo, Charlotte. >> Mám dotaz.
Neměl by to být střed - 1, protože první věc, kterou je
je to 0 indexovány, takže když dáme 4, že to není ve skutečnosti charakter jsme hledali?
Ano, a další problém s tím je-
to je skvělý úlovek, protože to, co se chystá skončit se děje možná
pokud budeme dál a my už nikdy nastavit původně?
Myslím, že to, co bychom mohli skončit dělat se pokouší získat přístup
prvek na 8. pozici pole,
který je v tomto případě neexistuje.
Budeme chtít udělat nějaké účetnictví za to,
že máme nějakou nulovou indexování.
[Charlotte] Omlouvám se, myslel jsem polovinu - 1 v hranatých závorkách.
Můžeme to udělat, že.
Vrátíme se k této otázce v jen trochu.
Jakmile začneme se dostat do skutečné smyčky,
to je, když budeme opravdu vidět vstupují do hry.
V současné době, můžeme to udělat, ale ty jsi naprostou pravdu.
To nula indexování bude mít vliv, že musíme činit.
Pojďme se podívat,.
>> Jak je větší než a menší než-?
[Student] jsem si, jak to udělat větší než a menší než druhé.
Jen jsem si nebyl jistý, co tisknout, pokud zjistíte, že je to méně než haystack středu nebo větší než.
Zde mohu zachránit, co I've-
[Nate] Jo, pokud si zachránit to, co máte, a my vytáhněte ji.
Tam jdeme.
[Student] A dal jsem otazníky, co jsem nevěděl.
[Nate] To vypadá skvěle.
Zde máme otazníky, protože stále nevíme
co budeme dělat docela ještě.
Co bychom chtěli dělat, pardon, máme nějaké závorky všichni funky na nás.
Budeme opravit tyto rovnátka.
Tam jdeme.
A tak to, co chceme dělat, podle našeho algoritmu,
pokud nebudeme najít jehlu?
Řekněme, že v případě, že jehla je menší než to, co jsme při pohledu na. Kevin.
Jen se podívat na levé polovině.
Dobře, takže budeme dát komentář zde říká "podívej se na levé polovině."
A v případě, že jehla je větší než kupce sena na středu, co chceme dělat?
[Student] Pak se podíváte na pravé polovině.
Podívejte se na pravé polovině, "podívej se na pravé poloviny."
Není tak špatný.
Dobře, takže v tomto bodě, co se hledá docela dobře.
Problém s kódem psaným je to, co?
[Student] Nemáte koncové body pro polovin.
Dobře, nemáme koncové body pro polovin.
Také jsme se jen jít přes to jednou.
Jsme teprve ve chvíli, se podívat na jeden střed.
Buď prvek je tam, nebo to není.
V zájmu dokončení tohoto, budeme muset udělat nějaké opakování.
Musíme neustále opakují, dokud nezjistíme, že
buď element je tam proto, že jsme zúžil a nakonec zjistil, že je,
nebo je to tam není, protože jsme se podíval přes všechny věci,
v příslušných polovin pole a zjistil, že nic je tam.
>> Kdykoliv jsme dostali toto opakování děje, co budeme používat?
[Student] smyčka.
Nějaký smyčky. Ano.
[Student] Můžeme udělat do-while, a mít to dělat, a pak při
jehla není rovno-nejsem jistý, kde jsem šel s tím.
Ale něco jako to, že tak dlouho, jak to dělá ne stejná hodnota, kterou uživatel vstup.
Jo, tak se pojďme podívat, jak to může psát sám?
Říkal jsi, že jdeme použít do-while.
Kde se to začalo?
[Student] Hned po velikost / 2.
[Nate] Dobře, a co budeme dělat?
Budeme vyplnit chvíli později.
Co budeme dělat?
[Student] Copak chceme dělat všechny ty věci, které máme v případě části?
[Nate] Do všechny ty věci, skvělé.
Kopírování a vkládání.
Oh, člověče.
Uvidíme, jestli to funguje, jestli to půjde karta to znovu.
Krásné.
Dobře, a šetříme to tak vy si to.
Dobře, a my se chystáme udělat to při-
to, co bylo, když podmínka, že jsi po?
[Student] Zatímco se jehla není rovno, tak jako vykřičník.
Ale nejsem si jistý, co přesně to je ještě.
[Nate] Jo, to je jeden způsob, jak to udělat.
Sam, máte napsat komentář?
[Sam] jsem si vzpomněl, když jsem se podívala na videa,
Vzal jsem si screenshot z jednoho z-jako když jsme dělali pseudokódu pro to,
tam byl nějaký vztah mezi max. a min.
Myslím, že to bylo něco jako když max je stále méně než min.
Mám to.
[Sam] Nebo jako když max není menší než min nebo něco takového,
protože to by znamenalo, že jste hledali všechno.
>> Jo, tak co to znít jako max a min byly na mysli?
[Sam] Hodnoty že-celá čísla, které se chystáte změnit
vzhledem k místu, kde jsme dali polovinu.
Přesně tak.
[Sam] V tomto bodě, bude to [neslyšitelné] výpočet max. a min.
Střed je to max a min nápad.
Dává to smysl, aby lidi?
Pokud bychom měli začít uvažovat o tom, jak budeme dělat tuto iteraci,
máš naprostou pravdu, že chceme použít nějaký do-while.
Ale myslím, že pokud bychom si vzpomenout, co se děje na místě tohoto pole
a co se vlastně děje, já se chystám napsat sem-
při prvním opakování binárního vyhledávání, máme-
Budu používat B a E k označení začátku.
A pak konec našeho pole.
Víme, že začátek je na 4 támhle,
a víme, že konec je na 108.
Řekněme, že hledáte pro číslo 15.
Poprvé jsme to, jak jsme viděli dříve,
střed je buď bude 16 nebo 23
v závislosti na tom, jak vypočítat věci.
Vzhledem k tomu, rovnoměrně rozdělit v polovině by nám tento prostor
mezi 16 a 23, nemůžeme rovnoměrně rozdělit
nebo rozdělit a dostat na pravé středu.
My se podíváme na 16.
Budeme si uvědomit, "Hey, 16> 15, které jsme hledali."
Poté pohled na levé polovině pole
co skončíme dělá, je odhazovat
celý tento horní část
a řekl: "Dobrá, nyní naše koncový bod bude tady."
Další iterace našeho smyčky, jsme nyní podíváme na tomto poli,
efektivně, co jste vyloučili tuto část, protože teď
pokud budeme brát polovinu být rozdíl mezi začátkem a koncem,
najdeme naše střed na 8,
které pak můžeme otestovat 8 vidět, kde je ve vztahu k počtu jsme hledali,
15, zjistíme, že 15 je větší,
takže se musíme přesunout do pravé části seznamu,
které známe, protože jsme lidé, a my můžeme vidět to.
Víme, že pravá část bude tam, kde jsme ho najít,
ale počítač neví, že, takže to, co budeme dělat, je my budeme skutečně
se to jít nahoru, a teď na začátku a na konci
jsou stejné místo, takže střed stává jediným číslo v seznamu v tomto bodě,
který je o 15, a našli jsme ho.
Znamená to, že vrhnout nějaké světlo na tom, kde to celé max a min zápis se děje,
sledování koncových bodů pole, aby se zjistit
jak zúžit věci dolů?
>> Co by se stalo, kdyby to nebylo rovno 15 teď?
Co když jsme hledali 15, a místo toho, toto číslo bylo také 16?
Rádi bychom říci: "Ach, to je větší.
Chceme se vrátit k levé. "
A my bychom přesunout náš e doprava,
na kterém místě máme koncový bod, který by byl konfliktní.
To by nebylo možné vyhledávat pro všechny více prvků
protože teď máme koncový bod a naše počáteční bod,
naše max a naše min, jsou nyní převrácený.
Hledáme přes celé pole. Nemůžeme nic najít.
To je bod, ve kterém bychom chtěli říci, "Dobře, budeme zastavit tento algoritmus.
Nenašli jsme nic. My víme, že to tu není. "
Jak se to děje?
[Student] Jak přesně počítač přepne do konce?
Jak konec skončit před začátkem?
Konec skončí před začátkem
protože matematiky, že budeme dělat pokaždé, když jsme se to udělat.
Způsob, jakým jsme se vyměnit, je, když se podíváte na poprvé jsme udělat swapu
kde máme začátek na 4 a konec
celou cestu dolů na 108 a naše střed, řekněme, na 16 -
Chystám se obnovit tuto zpátky do 15-li hledáme pro 15,
věděli jsme, že to, co jsme udělali, když jsme zkontrolovali 16 a viděl, že to bylo větší
a chtěl odhodit celou pravou část seznamu,
jsme viděli, že to, co jsme chtěli udělat, je přesunout tento e tady.
Účinně, dostal e dojatá k jednomu před středem.
Podobně, když jsme dělali tuto iteraci algoritmu
a střed byl v 8,
Zjistili jsme, že 8 <15, a tak jsme chtěli přesunout b
jedna minulost středu.
Nyní, na začátku a na konci jsou oba společně v tomto 15.
>> Pokud bychom se děje se podívat na jinou hodnotu, ne 15,
nebo je-li to 15 místo toho byl 16,
bychom zjistili, že e chceme přesunout jeden před středem.
Nyní e by se tam hodil méně než b.
Projděme jak jsme vlastně skončili kódování tohoto algoritmu.
Víme, že chceme mít tuto midpoint výpočet.
Víme také, že chceme sledovat začátek a konec pole
z našeho aktuálního pole, takže můžeme zjistit
kde tento levá polovina seznamu a kde pravá polovina seznamu je.
Děláme, že se buď začíná a končí,
nebo můžeme jim říkat min a max.
Budu používat začínat a končit tentokrát.
Když začneme, podíváme-li se zpět na náš příklad tady dole,
náš začátek byl nastaven na samém začátku pole, jako přírodní.
Co index to bylo? Co by naše začít být?
Daniel.
[Daniel] Haystack [0].
[Nate] Jo, takže jsme mohli nastavit rovná kupce sena [0].
Problém však je, že tento nám není pozici prvního prvku.
To nám dává index prvního prvku nebo skutečnou hodnotou v této první pozici.
[Student] To bude konvertovat k 0,20?
[Nate] Co to bude dělat, je-dobře, nebude to dělat žádné konverze.
Co to bude dělat, je to uloží 4 v zahájení,
a pak to bude velmi těžké provést srovnání proti zahájení
protože begin uspořádá hodnotu 4,
která je na začátku našeho pole,
ale chceme sledovat indexy v poli
oproti hodnotám.
Budeme vlastně používat 0, takhle.
Pro ukončení pole-Charlotte přinesla to až o něco dříve.
To je místo, kde se budeme brát v úvahu nulovou indexování.
>> Charlotte, co je konec pole?
Co je index na konci?
[Charlotte] Velikost - 1.
Jo, a jakou velikost bychom měli používat?
Měli bychom použít kapitálu velikosti nebo malými písmeny velikost?
Capital velikost.
V tomto případě může být použití kapitálové velikosti.
Pokud bychom chtěli tuto funkci je přenosný
a používejte tuto funkci v jiných programech,
můžeme skutečně využít malá písmena velikosti.
Je to taky v pohodě.
Ale Charlotte je naprosto správné, že chceme mít velikost - 1.
V tomto bodě,
[Student] Jak je to, že můžete použít velká velikost?
Jak je možné, že bychom mohli použít velká velikost?
Ukazuje se, že tyto # definuje jsou opravdu,
pod kapotou, text jako najít a nahradit, pokud to dává smysl.
Při kompilaci kódu, předzpracování fáze
překladače prochází souboru,
a vypadá to všude možně, že jste napsali kapitálu velikosti,
a nahrazuje tento text doslova s ​​8, stejně jako to.
V tomto smyslu je velmi odlišné od proměnné.
Neznamená to však trvat nějaké místo v paměti.
Je to jednoduchý textový nahradit trik.
V tomto případě, budeme používat velikost.
Odtud jsme chceš dělat nějaké opakování,
a my jsme na správné cestě s naší do-while.
Chceme udělat něco, dokud podmínka neplatí už,
a jak jsme viděli dříve, viděli jsme, že tato podmínka
byl opravdu, že nechceme konec
být menší než začne.
>> To je naše zastavení stav.
Pokud k tomu dojde, chceme zastavit a prohlásit jako, "Hele, my jsme nic nenašli."
Chcete-li vyjádřit to, my chceme použít nějaký smyčky.
V tomto případě, že by bylo do-while, pro smyčky, zatímco smyčka?
Máme do-while zde.
Líbí se vám kluci líbí tohoto přístupu?
Myslíte si, že bychom měli zkusit jiný přístup?
Kevin, nějaké myšlenky?
Mohli bychom mít while, protože víme, že maximální
by byly vyšší než min na začátku tak jako tak.
Jo, takže to není inicializace, která se musí stát.
Tyto do-while smyčky jsou skvělé, když máte inicializovat
předtím zkoušení, vzhledem k tomu, zde
víme, že nebudeme mít reinitializing jak začít a skončit
každé kolo ze smyčky.
Víme, že chceme inicializovat, pak navštivte naše podmínky.
V tomto případě, to jsem vlastně jít s jednoduchým smyčce while.
Ukazuje se, že do-while smyčky jsou používány docela zřídka.
Mnoho míst ani učit se while.
Jsou dobré pro zpracování vstupů uživatele, takže jsme viděli mnoho z nich tak daleko.
Ale normální a while jsou mnohem častější.
Ukazuje se, že tato podmínka, jak jsou psány
nebude opravdu nám moc dobře, a proč je to?
Je mi líto, já nevím, jak se jmenuješ.
Jsem Jerry. >> Líto?
Je to B-O-R-U-I.
Oh, dobře.
Nevidím tě na mém seznamu.
Oh, je to proto, že-oh, to dává smysl.
Máte představu o tom, proč tato while nemusí fungovat, jak bylo zamýšleno,
jak je napsáno s podmínkou?
[Jerry] Myslíš jako chcete všechny ty věci po něm do-?
Jo, takže to je jedna.
Mohli bychom dát všechny tyto věci do smyčky while, což je naprosto pravdivé.
Další věc, která je trochu problematičtější, i když, je to, že tato podmínka nebude fungovat.
[Student] Musíte odhodit.
Správně, takže tato podmínka nebude nikdy platit zpočátku jak jsme o tom mluvili.
Chceme udělat něco do konce <začínají,
ale chceme něco udělat, zatímco
začít ≤ konec.
>> Tam je to obrácení logiky tam.
Jsem vinen dělat ty chyby pořád.
[Student] Proč to musí být menší než nebo rovno?
Vzhledem k tomu, pamatuješ si na případ, který jsme dostali na
tam, kde byl jen jeden prvek, a my jsme byli dole,
a my jsme byli při pohledu na jen 15 v našem poli?
A naše začátek a náš konec byl stejný prvek.
Chceme, aby se ujistil, že s nimi budeme nakládat ten případ.
Pokud jsme rovnou menší než,
bychom pouze možnost, aby se dostal na 2-elementu pole.
Jakmile jsme se dostali až do toho posledního prvku, kdyby tomu tak bylo naše prvek, bychom nikdy najít.
Nyní zde můžeme udělat přesně tak, jak jsi říkal.
Můžeme začít plopping věci přímo do středu naší smyčce while.
Můžeme plop v našem středu.
Můžeme si vzít všechny tyto if,
vytáhněte je z tohoto do-while,
plop je v,
čisté věci se trochu,
a já půjdu napřed a ušetřete tuto revizi.
A v tomto bodě, dostáváme velmi blízko.
Sam.
Myslím si, že také mít INT midpoint = velikost - 1/2.
Mám to, velikost - 1/2.
Je ještě něco, co musíme změnit na této lince?
To byl dobrý úlovek.
>> Co dělat velikost? Jsme neustále se měnící velikost?
Aby se udržel řadu jako to, máme pro změnu velikosti.
Máme-li změnit velikost pokaždé, když jsme jít kolem smyčky for.
Ale pamatujte si, když jsme jeli přes našem příkladu jen trochu dříve,
a měli jsme na začátku na 4
a konec celou cestu na 108?
Jak jsme vypočítat střed?
Byli jsme s použitím velikost?
Nebo jsme používali začít a skončit místo?
To je rozdíl mezi koncem a začátkem.
Přesně, a jak přesně bych měl napsat, že, Charlotte?
Jen konec - začíná.
Ty nebudou muset dělat - 1
protože - 1 byl zahrnut do konce a začne již.
[Nate] Skvělé, máš naprostou pravdu.
Nemáme dělat - 1, protože to - 1 byla zahrnuta
a vyúčtovány, budou při inicializujeme Konec proměnné.
>> Je ještě něco, co musím udělat, syntakticky, aby tato položka smysl?
[Student] Plus začít. >> Plus začít?
[Student] Na konci.
Vzhledem k tomu, je to jen počítá polovina délky.
Musíte přidat začít.
[Nate] Co by to spočítat pro nás?
Budeme-li uvažovat o konci této úplně první iteraci smyčky,
end bude v poloze indexu 7.
Začněte v pozici 0.
Pamatujte si, že my hledáme buď
pozice 3 nebo 4 pozici.
Podíváme-li se na tento matematice, jen aby to trochu víc konkrétní,
dát nějaká čísla tady, máme 7, 0,
tak 7-0, a pak / 2
je 3 v celé číslo, které je.
Pak si musíme pak přidat zpět naše začít?
Nevíme v tomto případě.
Na prvním iteraci, bude to v pořádku, protože end je 0.
Ale jak jsme pokrok, děláme opravdu všechno stačí
end - začít / 2.
Je tu ještě jedna Trik je zde, a to je právě jedna z priorit.
[Student] Potřebujeme závorky?
[Nate] Přesně tak, a to proto, že pokud se nám nepodaří dát tyto závorky,
pak tato linka bude vykládat místo
jako (konec) - (začátek / 2), který se rozhodně nechceme.
Dejte si pozor na ty pravidla přednost.
[Student] Proč není konec + začít?
Proč není konec + začít?
[Student] Proč je to tak, že?
Proč by to bylo +?
Myslím, že máš pravdu.
[Student] Vzhledem k tomu, že je to průměr?
[Nate] End + zahájení, máš naprostou pravdu.
Wow, jsem totálně podělal. Máš pravdu.
Pokud bychom dělali minus, bychom chtěli přidat začít znovu přihlásit
V tomto případě jste velmi správné, že chceme, aby se průměr dvou,
tak jsme si chceš přidat, jak protichůdný k odečíst je.
[Student] To by také fungovat, pokud jste konec - začít / 2 + začít.
To by, kdyby se do-myslím, že ano.
>> Například, pokud jsme se dívali na začátek,
a my posunul ho sem
na 15.
Nyní můžete začít na pozici 2.
Konec je na pozici 7.
Pokud odečteme je, dostaneme 5.
Rozdělte že 2, dostaneme 2.
A pak přidáme 2 zpět,
a že nás dostane na 4. pozici,
která je právě zde, což je na střed.
[Student] Líbí se musíme postarat o balení?
V jakém smyslu se musíme postarat o balení?
Pokud součet nebo rozdíl mezi
v závislosti na tom, jak to udělat, je to sudé číslo.
Pak počítač dostane zmatený, zda-li je to 2,5;
se přesunete vlevo nebo vpravo určit, které je na střed?
Mám to.
Ukazuje se, že s celočíselném dělení,
nemáme vůbec dostat tyto plovoucí desetinnou čárkou čísla.
Nikdy jsme se desetinu.
Je to úplně zlikvidovat.
Pokud máte počítač dělení dvou int proměnné,
a jeden je 7, a druhý je 2,
nezískáte 3,5 jako výsledek.
Bude se 3.
Zbytek budou zahozeny, tak je to skutečně zaokrouhlení
není kolo, ale podlaha, pokud jste obeznámeni s tím v matematice,
kde jste úplně zbavit desetinné,
a tak jste v podstatě zkracovat ji dolů na nejbližší
Vcelku pozice, na nejbližší celé číslo.
[Student] Ale pak je to problematické, protože pokud máte pole 7 prvků
pak to automaticky bere třetí prvek z středu místo 4..
Jak se s tím vypořádat?
Je to problematické, protože pokud jsme měli řadu 7,
to by si vybral třetí místo 4..
Mohl byste vysvětlit trochu víc?
[Student] Protože pokud máte 7 prvků pak 4. prvek
by být středem, ne?
Nezapomeňte svůj komentář o tom, že nula indexovány, ačkoli.
[Student] Jo, tak v poloze 3. To by bylo na střed.
Jo.
Oh, dobře. Chápu, co máte na mysli.
Je to trochu divné, jak jsme si zvyknout na celé této představě
jak se zbavit desetinných míst.
To je skvělé místo.
Pojďme dokončit tuto nahoru.
Jsme počítá náš střed.
>> Testujeme, zda naše jehla se rovná střední hodnotě.
Jsme tisk, že jsme ho našli, ale opravdu, co chceme dělat v této situaci?
Našli jsme to, a tak chceme, aby volající, že jsme ho našli.
Máme funkci, která je boolean zadaný funkce.
Jak jsme signál k volajícímu naší funkce, která jsme připraveni jít
je řekneme, "Hele, to je pravda."
Jak bychom to dělali, Kevine?
Jste kývl hlavou. >> [Kevin] Přidat return true.
[Nate] Přesně tak, vrátí true.
Nyní, pokud to není stejné, jak by se podíváme na levé polovině?
Nějaké nápady?
Stella, nějaké nápady?
Musíte nastavit novou pozici pro konec.
Jo.
Takže musíme udělat pozice středu - konec.
Great.
Musíme nastavit novou pozici na konci
podívat se na levé polovině.
To bylo to, co jsme o tom mluvili před, kde
Pořád se vrací k tomuto příkladu.
Jsem začít tady, a pak jsem se nakonec všichni cestu přes tu.
>> Opět platí, že pokud jsme hledali 15, a náš střed je 16,
a my si uvědomit, "Oops, 16 je větší.
Chceme přesunout na levou polovinu. "
Pak bychom přesunout konec 15,
a my, že tím, že jeden od středu
a nastavení, které jako náš nový konci.
Podobně, pokud se chcete podívat na pravou polovinu, jak by to dělali?
Máte nějaký nápad?
[Student] Stačí nastavit začít midpoint + 1.
[Nate] Great.
A nyní v případě, že jsme nic nenajdeme,
to, že se postaral o pro nás?
Daniel, to, že si postaráno o nás?
[Daniel] č.
[Nate] Pokud bychom dělat to přes celé pole a my nic nenajdeme,
kde by to být postaráno, nebo bychom měli postarat se o to?
[Daniel], zatímco podmínka.
[Nate] Jo, a zároveň podmínka, přesně.
To se bude starat o prochází celé pole, pokud nenajdeme nic.
Tento cyklus while skončí.
Nikdy nebudeme se setkali tuto podmínku,
a můžeme se vrátit false.
Můžeme také nechat tuto možnost, pokud tady takhle
protože pokud tuto možnost, pokud tvrzení je pravdivé,
a naše funkce vrátí,
a tak budeme podstatě přeruší tato funkce v tomto bodě
když se vrátíme true.
Ale co se stane s touto strukturou tady?
Bude to fungovat úplně, nebo je tam nějaký logický chyba tam?
>> Tam je nějaký logický chyba tam, s tím, jak to nastavit.
Co by mohlo být?
[Student] Proč potřebujete - a + 1s?
, Která stanovuje naší nabídku tak, aby byly naše nová levá polovina a pravá polovina.
[Student] Ale proč by nemohla to udělat, aniž by - 1s a + 1s?
[Nate] Dalo by se nastavit rovná středu?
Co by mohlo být problematické, že?
[Student] Myslím, že je to neefektivní, protože máte kontrolu hodnotu, která je již zkontrolovat.
[Nate] Přesně tak, Sam je úplně pravdu.
Pokud se nastavit konec a začne se rovná středu
místo - 1 a + 1 zamyšleně,
v určitém okamžiku v budoucnosti budeme nakonec kontrolu střed znovu.
[Student] Začal jsem PSet, a pak jsem měl něco takového
kde jsem zapomněl + 1, a to uvízl v nekonečné smyčce.
Jasně, protože v určitém okamžiku budete nikdy dostat začít a skončit
skutečně překrývají.
Cool.
Je tu ještě jedna logická chyba, a to je, že by to mělo být určitě
else if.
Proč by to mohlo být?
>> Důvodem je, pokud to není jinak, pokud-jsi viděl, Kevin?
[Kevin] Jo, protože měníte koncový bod.
[Nate] Přesně tak.
Měníme koncový bod,
a pokud je to napsáno takto-Dáme aby mezery mezi-
bude kontrolovat tento případ.
Tento případ, pokud se podaří, zmizí, z funkce.
Pak to bude kontrolovat tuto další případ,
a je-li to podaří, upraví na koncový bod,
a pak to bude pokračovat a zjistit tento případ.
Ale v tomto bodě, nechceme, aby i nadále kontrolu.
Naštěstí, jsme se obnovit polovinu tady,
a víme, že tento případ nebude úspěšná.
Ale my určitě chceme dát else, pokud tam
i přesto, že by mohl v tomto případě
protože nejsme nastavení středového bodu, by to dělat rozdíl?
Ne, protože tyto případy jsou exkluzivní.
Opět, můj špatný.
Nechceme, myslím, je třeba tuto else if.
Můžeme to zkusit a spustit jej a uvidíte, co se stane.
Budova, došlo k chybě.
Je to pravděpodobně proto, že jsem opustil to b je a ŽP tady.
Mám víc těch, kteří se na vrcholu?
To nevypadá to.
My oddálit, vybudovat,
tam to jde, takže teď, když hledáme 15,
Ano.
Dovolte mi, abych Zoom
15, ano. Můžeme spustit znovu.
Nahrání zdrojový kód, stavební, běh.
Můžeme hledat něco jako 13,
a nemáme dostat něco vytisknout, tak to není zjištění, že pro nás.
To je skvělé, protože to není v našem seznamu.
>> Jsme nyní opožděně.
To bude mít to pro tento týden.
Díky za vstup, a uvidíme se později.
>> [CS50.TV]