>> [Muzikos grojimo]
>> Doug LLOYD: Visos dešinę.
Taigi dvejetainis paieškos yra algoritmas mes galime naudoti
rasti elementą viduje masyvą.
Skirtingai nuo linijiniu paieškoje, ji reikalauja ypatingo būti laikomasi iš anksto,
bet tai tiek daug efektyvesnis, jei kad sąlyga yra, iš tikrųjų, met.
>> Taigi, kas yra idėja čia?
tai skaldyk ir valdyk.
Mes norime sumažinti dydį paieška plotas perpus kiekvieną kartą
tam, kad rasti tikslinę, skaičių.
Tai kur ta sąlyga ateina į žaidimą, nors.
Mes galime tik sverto galia pašalinant pusė elementų
net žiūri juos, jei masyvas surūšiuotas.
>> Jei tai pilnas išmaišyti, mes galime ne tik iš rankų
išmesti pusė elementų, nes mes nežinome, ką mes dėžę.
Bet jei masyvas surūšiuotas, mes galime padaryti, nes mes
žinau, kad viskas su tuo, į kairę, kur šiuo metu yra
turi būti mažesnis nei vertė mes šiuo metu.
Ir viskas į teisė, kur mes esame
turi būti didesnis, negu vertė mes šiuo metu ieško.
>> Taigi, kas yra Pseudocode žingsniai dvejetainis ieškoti?
Mes pakartokite šį procesą tol, kol masyvas arba, kaip mes pereiti per,
sub matricos, mažesni gabalai originalus masyvas, yra dydis 0.
Apskaičiuokite Mediana dabartinės pietus masyvo.
>> Jei reikšmė jūs ieškote yra toje masyvo elemento, sustabdyti.
Jūs ją radau.
Tai puiku.
Priešingu atveju, jei tikslas yra mažiau nei tai, kas yra viduryje,
Taigi, jei vertės mes ieškome už yra mažesnis nei matome,
vėl pakartokite šį procesą, bet pakeisti pabaigos tašką, vietoj to,
buvimo originalus užpildyti visą masyvą,
būti tik į kairę kur mes tiesiog atrodė.
>> Mes žinojome, kad vidurinioji buvo per didelis, arba tikslinis buvo mažesnis nei viduryje,
ir todėl ji turi egzistuoti, jei ji egzistuoja ne visi masyvo,
kur nors į centrą kairę.
Ir todėl mes nustatyti masyvo vietą tiesiog į kairę
iš vidurio taško, kaip naujos galinio taško.
Priešingai, jei tikslas yra didesnis nei tai, kas yra viduryje,
mes darome tą patį procesas, tačiau vietoj to mes
pakeisti pradinį tašką, kad būtų tiesiog į centrą dešinėje
mes tiesiog apskaičiuotas.
Ir tada mes pradėti procesą dar kartą.
>> Leiskite vizualizuoti tai, gerai?
Taigi ten daug vyksta ir čia bet čia AN 15 elementų masyvas.
Ir mes ketiname būti sekti iš daug daugiau dalykų šiuo metu.
Taigi tiesinės paieškos, mes buvome tik rūpinasi į taikinį.
Bet šį kartą mes norime rūpi, kur mes esame
pradeda atrodyti, kur mes sustoti ieško,
ir kas Mediana dabartinės masyvo.
Taigi čia mes einame su dvejetainiu paiešką.
Mes gana daug gera eiti, tiesa?
Aš tik ketina pribaigti Toliau Čia indeksų rinkinys.
Tai iš esmės yra tai, ką elementas masyvo mes kalbame apie.
Su linijiniu paieškoje, mes rūpintis, nes mes
reikia žinoti, kiek elementai mes Iteracja per,
bet mes ne iš tikrųjų rūpi, ką elementas mes šiuo metu ieško.
Be dvejetainis paieškos, mes darome.
Ir taip jie yra tik ten taip mažai vadove.
>> Taigi, mes galime pradėti, tiesa?
Na, ne visai.
Prisiminkite, ką aš sakiau apie dvejetainis paieškos?
Mes negalime daryti ant nerūšiuotų masyvas ar kitur,
mes ne užtikrinti, kad tam tikri elementai ar vertybės nėra
netyčinio išmesti, kai mes tiesiog
nuspręsti ignoruoti pusė masyvo.
>> Taigi vienas žingsnis, su dvejetainiu paieškos yra, jūs turite turėti surūšiuoti masyvo.
Ir jūs galite naudoti bet į rūšiavimo algoritmai mes kalbėjome apie
kad jums į tą padėtį.
Taigi dabar mes tokioje padėtyje, kai mes galime atlikti dvejetainis paiešką.
>> Taigi leiskite pakartoti procesą žingsnis po žingsnio ir išlaikyti
stebėti, kas vyksta, kaip mes einame.
Taigi pirmiausia turime padaryti, tai apskaičiuoti dabartinio masyvo viduryje.
Na, mes pasakyti mes, pirmiausia gale, ieško vertės 19.
Mes bandome rasti skaičių 19.
Pirmasis elementas šis masyvas yra nulinės indeksą,
ir paskutinis elementas tai masyvas yra įsikūręs 14 indeksą.
Ir taip mes vadiname tuos pradžios ir pabaigos.
>> Taigi mes galime apskaičiuoti pagal viduriu pridėti 0 plius 14, padalinta iš 2;
gana paprasta viduryje.
Ir mes galime pasakyti, kad Mediana dabar 7.
Taigi yra 15, kas mes ieškome?
Ne, tai nėra.
Mes ieškome 19.
Bet mes žinome, kad 19 yra didesnis nei tai, ką mes radome viduryje.
>> Taigi, ką mes galime padaryti, tai pakeisti pradinį tašką
būti tik į dešinę viduryje, ir vėl pakartokite šį procesą.
Ir kai mes tai padarysime, mes dabar pasakyti nauja pradžia taškas yra masyvas vietą 8.
Ką mes iš tikrųjų padaryta yra ignoruojami viskas 15 kairę.
Mes pašalintas pusę Problemos, ir dabar,
vietoj to, kad ieškoti daugiau nei 15 elementai mūsų masyvas,
mes tik turite ieškoti per 7.
Taigi 8 yra naujas pradžios taškas.
14 vis dar yra galutinis taškas.
>> Ir dabar, mes einame per šį kartą.
Mes apskaičiuoti naują taško.
8 plius 14 yra 22, padalytą iš 2 11.
Ar tai, ką mes ieškome?
Ne, tai nėra.
Mes ieškome vertė ŠTAI mažiau nei tai, ką mes ką tik sužinojau.
Taigi mes ketiname pakartoti vėl procesas.
Mes ketiname pakeisti į pabaigos tašką būti tik į centrą kairę.
Taigi naujasis galutinis taškas tampa 10.
O dabar, tai tik dalis masyvas turime sutvarkyti.
Taigi, mes jau pašalintas 12 iš 15 elementų.
Mes žinome, kad jei 19 egzistuoja masyvo, ją
turi egzistuoti kažkur tarp elemento numeris 8 ir elementas numeris 10.
>> Taigi, mes vėl skaičiuoja naujų taško.
8 plius 10 yra 18, padalytą iš 2 9.
Ir šiuo atveju, atrodo, The tikslas yra viduryje.
Mes nustatėme, ką mes ieškome.
Mes galime sustabdyti.
Mes sėkmingai dvejetainis paieškos.
Gerai.
Taigi mes žinome, šį algoritmą veikia, jei tikslas yra
kažkur viduje masyvo.
Ar šį algoritmą dirbti, jei taikinys yra ne masyvo?
Na, pradėkime ją vėl, ir šį kartą,
Pažvelkime už elementą 16, kuris vizualiai matome
neegzistuoja niekur masyvo.
>> Pradžios taškas yra vėl 0.
Galutinis taškas vėl 14.
Tai yra pirmosios indeksai ir paskutiniai elementai visiškai masyvo.
Ir mes eiti per šį procesą mes tiesiog išgyveno vėl bando rasti 16,
nors vizualiai, jau galime pasakyti, kad ji nesiruošia būti ten.
Mes tiesiog norite įsitikinti šį algoritmą bus, iš tiesų, vis dar dirba tam tikru būdu
o ne tiesiog palikite mums įstrigo begalinis ciklas.
>> Taigi, kas yra žingsnis pirmiausia?
Apskaičiuokite Mediana dabartinės masyvo.
Kas yra pusiaukelė dabartinės masyvo?
Na, tai 7, tiesa?
14 plius 0, padalytą iš 2 7.
15, ką mes ieškome?
Ne.
Tai gana arti, bet mes ieškome kurių vertė šiek tiek didesnis, nei nurodyta.
>> Taigi mes žinome, kad jis ketina būti kur 15 kairę.
Taikinys yra didesnis nei kas yra viduryje.
Ir taip mes nustatome naują pradžios tašką į būti tik į viduryje dešinėje.
Mediana šiuo metu 7, todėl tarkim naujas pradžios taškas yra 8.
Ir ką mes iš tikrųjų daroma vėl ignoruojamas
visa kairėje pusėje, masyvo.
>> Dabar mes pakartoti apdoroti dar kartą.
Apskaičiuokite naują taško.
8 plius 14 yra 22, padalytą iš 2 11.
Ar 23 ką mes ko ieškote?
Deja, ne.
Mes ieškome vertė kuris yra mažesnis nei 23.
Ir taip, šiuo atveju, mes ketiname pakeisti pabaigos tašką būti tik
į dabartinės vidurio taško pusėje.
Dabartinė Mediana yra 11, o todėl mes nustatyti naują pabaigos tašką
kitą kartą mes einame per šį procesą iki 10.
>> Vėlgi, mes einame per šį procesą dar kartą.
Apskaičiuokite taško.
8 plius 10, padalytą iš 2 9.
Ar 19 ką mes ko ieškote?
Deja, ne.
Mes vis dar ieškome skaičius mažesnis nei.
Taigi mes pakeisti šio galutinio taško šį kartą būti tik į centrą kairę.
Mediana šiuo metu 9, todėl galutinis taškas bus 8.
Ir dabar, mes tiesiog ieškote bent vieną elementą masyvo.
>> Kokia šio masyvo viduryje?
Na, tai prasideda 8, tai baigiasi 8, Mediana yra 8.
Ar tai, ką mes ieškome?
Ar mes ieškome 17?
Ne, mes ieškome 16.
Taigi, jei ji egzistuoja masyve, ji turi egzistuoti kažkur
į kur šiuo metu yra kairėje.
Taigi, ką mes ketiname daryti?
Na, mes nustatyti pabaigos tašką būti tik į dabartinės vidurio taško pusėje.
Taigi mes pakeisti galutinį tašką iki 7.
Ar matote, ką tik čia nutiko, nors?
Pažiūrėkite čia dabar.
>> Pradėti dabar didesnis nei pabaigos.
Veiksmingi, du galai Mūsų masyvo kirto,
o pradžios taškas yra dabar po šio galutinio taško.
Na, tai nėra jokios prasmės, tiesa?
Taigi, dabar, ką mes galime pasakyti, mes turi sub masyvas dydis 0.
Ir kai mes Dotarłeś Šiuo metu mes galime dabar
užtikrinti, kad elementas 16 neegzistuoja masyvo,
nes pradžios taško ir galutinis taškas kirto.
Ir todėl ten nėra.
Dabar, pastebėti, kad tai yra šiek tiek kitoks, nei pradžios tašką ir pabaigos
taškas yra ta pati.
Jei būtume gyvenę ieško 17, ji turėtų
buvo masyvo ir pradžios taškas ir galutinis taškas pastarojo iteracijos
prieš kirto tie taškai, mes nustatėme, 17 ten.
Tai tik tada, kai jie kerta, kad mes galime garantuoja, kad elementas, nėra
egzistuoja masyvo.
>> Taigi galime imtis daug mažiau žingsniai kaip tiesinės paieškoje.
Blogiausiu atveju, mes turėjome padalinti iš n elementų sąrašą
pakartotinai per pusę rasti tikslą, arba todėl, kad tikslinė elementas
bus kažkur paskutinis skaidymą arba ji neegzistuoja ne visi.
Taigi, blogiausiu atveju, mes turime suskaidytas array-- jūs žinote?
Prisijungti n kartų; mes turi sumažinti problemą
pusę tam tikrą skaičių kartų.
Tai kiek kartų yra žurnalas n.
>> Koks geriausias scenarijus?
Na, pirmas kartas, kai mes apskaičiuoti Mediana
randame tai, ką mes ieškome.
Iš viso praėjusiais pavyzdžių, dvejetainis paieškos
mes ką tik perėjo, jei mes turėjome ieškojau elemento 15
mes būtų nustatyta, kad iš karto.
Tai buvo pačioje pradžioje.
Tai buvo Mediana pirmasis bandymas dalimis
iš į dvejetainį paieškos pasidalijimas.
>> Ir taip blogiausia atveju dvejetainis paieškos tęsiasi
į log n, kuri iš esmės geriau nei tiesinės paieškoje, blogiausiu atveju.
Geriausiu atveju dvejetainis Paieška eina omega 1.
Taigi dvejetainis paieškos yra daug geriau nei tiesinės paieškos,
bet jūs turite elgtis su proceso rūšiavimas masyvo pirmą kartą prieš jūs galite
sverto dvejetainis paieškos galią.
>> Aš Doug Lloyd.
Tai CS 50.