>> [Musiikkia]
>> DOUG Lloyd: Selvﾃ､.
Joten binary haku on algoritmi voimme kﾃ､yttﾃ､ﾃ､
lﾃｶytﾃ､ﾃ､ elementin sisﾃ､llﾃ､ array.
Toisin kuin lineaarinen haku, se vaatii erityisedellytystﾃ､ tﾃ､ytyttﾃ､vﾃ､ etukﾃ､teen,
mutta se on niin paljon tehokkaampaa, jos tﾃ､mﾃ､ edellytys on, itse asiassa, tﾃ､yty.
>> Niin mitﾃ､ idea tﾃ､ﾃ､llﾃ､?
se on hajota ja hallitse.
Haluamme pienentﾃ､ﾃ､ hakualuetta puoleen joka kerta
jotta lﾃｶydettﾃ､isiin tavoite numero.
Tﾃ､ssﾃ､ on, ettﾃ､ ehto tulee pelata, vaikka.
Voimme vain hyﾃｶdyntﾃ､ﾃ､ valtaa poistamalla puolet elementit
katsomatta edes ne, jos jono on lajiteltu.
>> Jos se on tﾃ､ydellinen sekoitus ylﾃｶs, Emme voi vain kﾃ､sistﾃ､
hﾃ､vitﾃ､ puolet elementtejﾃ､, koska emme tiedﾃ､, mitﾃ､ me poisheittﾃ､minen.
Mutta jos array lajitellaan, Voimme tehdﾃ､ niin, koska me
tietﾃ､vﾃ､t, ettﾃ､ kaiken vasemmalle, missﾃ､ me tﾃ､llﾃ､ hetkellﾃ､ olemme
on oltava pienempi kuin arvo olemme tﾃ､llﾃ､ hetkellﾃ､.
Ja kaiken oikeus missﾃ､ olemme
on oltava suurempi kuin arvo me tarkastelee parhaillaan.
>> Niin mitﾃ､ pseudokoodina vaiheet binary haku?
Toistamme tﾃ､tﾃ､, kunnes array tai, kuten me kﾃ､ymme eteenpﾃ､in,
sub paneelit pienempiﾃ､ paloja alkuperﾃ､inen joukko, on koko 0.
Laske puolivﾃ､li Nykyisen osa array.
>> Jos arvo etsit on ettﾃ､ elementti array, lopeta.
Lﾃｶysit sen.
Sepﾃ､ hienoa.
Muuten, jos tavoite on vﾃ､hemmﾃ､n kuin mitﾃ､ keskellﾃ､,
joten jos arvo etsimme sillﾃ､ on alempi kuin mitﾃ､ nﾃ､emme,
toista tﾃ､mﾃ､ prosessi uudelleen, mutta muuttaa pﾃ､ﾃ､tepiste, vaan
olemisen alkuperﾃ､isen tﾃ､ydellinen tﾃ､yden valikoiman,
olla vain vasemmalla missﾃ､ me vain katsoi.
>> Tiesimme, ettﾃ､ keskellﾃ､ oli liian korkea, tai kohde oli alle keskellﾃ､,
ja niin se on olemassa, jos se olemassa lainkaan array,
jonnekin vasemmalla keskipisteen.
Ja niin me asettaa array sijainti vain vasemmalla
keskipisteen uudeksi pﾃ､ﾃ､tepiste.
Sitﾃ､ vastoin, jos tavoite on suurempi kuin mitﾃ､ keskellﾃ､,
teemme tﾃ､smﾃ､lleen sama prosessi, mutta sen sijaan me
muuttaa aloituspisteen olla juuri oikealla keskipisteen
me vain lasketaan.
Ja sitten, aloitamme uudelleen.
>> Katsotaanpa visualisoida, OK?
Joten siellﾃ､ on paljon menossa ja tﾃ､ﾃ､llﾃ､, mutta tﾃ､ssﾃ､ on joukko 15 elementtejﾃ､.
Ja aiomme olla pitﾃ､ﾃ､ kirjaa paljon enemmﾃ､n juttuja tﾃ､llﾃ､ kertaa.
Joten lineaarinen haku, olimme vain vﾃ､littﾃ､minen kohde.
Mutta tﾃ､llﾃ､ kertaa haluamme vﾃ､litﾃ､ missﾃ､ olemme
alkaa nﾃ､yttﾃ､ﾃ､, missﾃ､ pysﾃ､hdyimme etsimﾃ､ssﾃ､,
ja mitﾃ､ keskipisteen nykyisen taulukon.
Joten tﾃ､ssﾃ､ sitﾃ､ mennﾃ､ﾃ､n binary haku.
Olemme melko paljon hyvﾃ､ mennﾃ､, eikﾃｶ?
Olen juuri menossa laittaa alas Alla tﾃ､ﾃ､llﾃ､ joukko indeksejﾃ､.
Tﾃ､mﾃ､ on pohjimmiltaan vain mitﾃ､ elementti array puhumme.
Lineaarinen haku, me care, koska me
tﾃ､ytyy tietﾃ､ﾃ､, kuinka monta elementit olemme iteroimalla yli,
mutta emme oikeastaan 窶銀久ﾃ､litﾃ､ mitﾃ､ elementti me tarkastelee parhaillaan.
Binary haku, teemme.
Ja niin ne ovat vain siellﾃ､ pieni opas.
>> Jotta voimme aloittaa, eikﾃｶ?
No, ei aivan.
Muista mitﾃ､ sanoin noin binary haku?
Emme voi tehdﾃ､ sitﾃ､ lajittelemattomien array tai muuten,
emme takaa, ettﾃ､ tiettyjﾃ､ osia tai arvot eivﾃ､t ole
tahattomat hﾃ､vittﾃ､ﾃ､ kun me vain
pﾃ､ﾃ､ttﾃ､ﾃ､ ohittaa puolet jono.
>> Astu siis yksi binary haku on sinulla on lajiteltu array.
Ja voit kﾃ､yttﾃ､ﾃ､ mitﾃ､ tahansa lajittelu algoritmit olemme puhuneet
saada sinut ettﾃ､ asentoon.
Joten nyt olemme asemassa, jossa voimme tehdﾃ､ binary haku.
>> Joten toistaa prosessi askel askeleelta ja pitﾃ､ﾃ､
seurata, mitﾃ､ tapahtuu kun kuljemme.
Joten ensimmﾃ､inen meidﾃ､n tﾃ､ytyy tehdﾃ､, on laskea keskipiste nykyisen taulukon.
No, me sanomme olemme, ensimmﾃ､inen kaikki, etsii arvon 19.
Yritﾃ､mme lﾃｶytﾃ､ﾃ､ numero 19.
Ensimmﾃ､inen osa tﾃ､tﾃ､ array sijaitsee indeksi nolla,
ja viimeinen osa tﾃ､tﾃ､ array sijaitsee olevan 14.
Ja niin soitamme ne alun ja lopun.
>> Joten laskemme keskipisteen lisﾃ､ﾃ､mﾃ､llﾃ､ 0 plus 14 jaettuna 2;
melko yksinkertainen keskipiste.
Ja voimme sanoa, ettﾃ､ keskipiste on nyt 7.
Joten on 15, mitﾃ､ etsimme?
Ei se ei ole.
Etsimme 19.
Mutta me tiedﾃ､mme, ettﾃ､ 19 on suurempi kuin mitﾃ､ lﾃｶysimme keskellﾃ､.
>> Joten mitﾃ､ voimme tehdﾃ､ on muuttaa aloituspiste
olla juuri oikealla keskipiste, ja toista prosessi uudestaan.
Ja kun teemme sen, sanomme nyt uusi alkupiste on array paikka 8.
Mitﾃ､ olemme hoitaa tehokkaasti on huomiotta kaikki vasemmalle 15.
Olemme eliminoitu puoli Ongelman, ja nyt,
sen sijaan, etsiﾃ､ yli 15 elementtiﾃ､ meidﾃ､n array,
meillﾃ､ on vain etsiﾃ､ yli 7.
Joten 8 on uusi aloituspiste.
14 on edelleen pﾃ､ﾃ､tepiste.
>> Ja nyt, mennﾃ､ﾃ､n tﾃ､nﾃ､ uudelleen.
Laskemme uusi keskipiste.
8 plus 14 on 22, jaettuna 2 on 11.
Tﾃ､tﾃ､kﾃｶ me etsimme?
Ei se ei ole.
Etsimme arvo, joka on vﾃ､hemmﾃ､n kuin mitﾃ､ me juuri lﾃｶytﾃ､nyt.
Joten aiomme toistaa uudelleen.
Aiomme muuttaa pﾃ､ﾃ､tepiste olla vain vasemmalla keskipisteen.
Joten uusi pﾃ､ﾃ､tepiste tulee 10.
Ja nyt, se on vain osa array olemme lajitella kautta.
Joten olemme nyt poistettu 12 15 elementtiﾃ､.
Tiedﾃ､mme, ettﾃ､ jos 19 olemassa jono, se
on oltava olemassa jonnekin elementin numero 8 ja elementin numero 10.
>> Joten laskemme uuden keskipisteen uudelleen.
8 + 10 on 18, jaettuna 2 on 9.
Ja tﾃ､ssﾃ､ tapauksessa, katso, tavoite on keskellﾃ､.
Lﾃｶysimme juuri sitﾃ､, mitﾃ､ etsit.
Voimme lopettaa.
Olemme onnistuneesti binﾃ､ﾃ､rihaku.
Selvﾃ､.
Joten me tiedﾃ､mme tﾃ､mﾃ､n algoritmi toimii jos tavoite on
jonnekin sisﾃ､llﾃ､ jono.
Onko tﾃ､mﾃ､ algoritmi tyﾃｶ jos tavoite ei ole array?
No, aloitetaan se uudelleen, ja tﾃ､llﾃ､ kertaa,
Katsotaanpa elementille 16, joka visuaalisesti voimme nﾃ､hdﾃ､
ei ole missﾃ､ﾃ､n pakassa.
>> Alkupiste on jﾃ､lleen 0.
Pﾃ､ﾃ､tepiste on jﾃ､lleen 14.
Ne ovat indeksejﾃ､ ensimmﾃ､isen ja viimeinen elementit tﾃ､ydellinen valikoima.
Ja me mennﾃ､ lﾃ､pi me vain meni lﾃ､pi uudelleen, yrittﾃ､ﾃ､ lﾃｶytﾃ､ﾃ､ 16,
vaikka visuaalisesti, voimme jo sanoa, ettﾃ､ se ei aio olla siellﾃ､.
Haluamme vain varmistaa tﾃ､mﾃ､ algoritmi tulee itse asiassa vielﾃ､ tyﾃｶtﾃ､ jollain tavalla
ja ei jﾃ､tﾃ､ meitﾃ､ jumissa pﾃ､ﾃ､ttymﾃ､ttﾃｶmﾃ､ﾃ､n silmukkaan.
>> Niin mitﾃ､ askel ensimmﾃ､inen?
Laske puolivﾃ､li nykyisen taulukon.
Mikﾃ､ keskipisteen Nykyisen array?
No, se on 7, eikﾃｶ?
14 plus 0 jaettuna 2 on 7.
On 15, mitﾃ､ etsimme?
Ei.
Se on melko lﾃ､hellﾃ､, mutta etsimme joiden arvo hieman suurempi kuin.
>> Joten me tiedﾃ､mme, ettﾃ､ se tulee olla missﾃ､ﾃ､n vasemmalle 15.
Tavoitteena on suurempi kuin mitﾃ､ on keskipiste.
Ja niin asetamme uusia aloituspiste olla juuri oikealla keskellﾃ､.
Keskipiste on tﾃ､llﾃ､ hetkellﾃ､ 7, joten sanokaamme uusi alkupiste on 8.
Ja mitﾃ､ olemme tehokkaasti tehdﾃ､ uudelleen ohitetaan
koko vasen puoli jono.
>> Nyt toistamme kﾃ､sitellﾃ､ vielﾃ､ kerran.
Laske uusi keskipiste.
8 plus 14 on 22, jaettuna 2 on 11.
On 23, mitﾃ､ etsimme?
Valitettavasti ei.
Etsimme arvo joka on vﾃ､hemmﾃ､n kuin 23.
Ja niin tﾃ､ssﾃ､ tapauksessa, menemme muuttaa pﾃ､ﾃ､tepiste on vain
vasemmalle nykyisen keskipisteen.
Nykyinen keskipiste on 11, ja niin me asettaa uusi pﾃ､ﾃ､tepiste
Seuraavan kerran menemme Tﾃ､mﾃ､n prosessin kautta 10.
>> Jﾃ､lleen me mennﾃ､ lﾃ､pi uudelleen.
Laske keskipiste.
8 plus 10 jaettuna 2 on 9.
On 19, mitﾃ､ etsimme?
Valitettavasti ei.
Olemme vielﾃ､ etsimﾃ､ssﾃ､ numero pienempi.
Niin me muuttaa pﾃ､ﾃ､tepiste tﾃ､llﾃ､ kertaa olla vain vasemmalla keskipisteen.
Keskipiste on tﾃ､llﾃ､ hetkellﾃ､ 9, joten pﾃ､ﾃ､tepiste on 8.
Ja nyt, me vain etsimﾃ､ssﾃ､ yhdellﾃ､ alkiotaulukon.
>> Mikﾃ､ keskipiste tﾃ､mﾃ､n array?
No, se alkaa 8, se pﾃ､ﾃ､ttyy 8, keskipiste on 8.
Sitﾃ､kﾃｶ etsimme?
Me etsimme 17?
Ei, me etsimme 16.
Joten jos se on olemassa joukko, sen on olemassa jonnekin
vasemmalle, missﾃ､ me nyt olemme.
Joten mitﾃ､ me teemme?
No, me asettaa pﾃ､ﾃ､tepiste on vain vasemmalle nykyisen keskipisteen.
Niin me muuttaa pﾃ､ﾃ､tepiste 7.
Ymmﾃ､rrﾃ､tkﾃｶ, mitﾃ､ vain tﾃ､ﾃ､llﾃ､ on tapahtunut, vaikka?
Katso tﾃ､ﾃ､llﾃ､ nyt.
>> Start on nyt suurempi kuin lopussa.
Tehokkaasti, kaksi pﾃ､ﾃ､tﾃ､ meidﾃ､n array ovat ylittﾃ､neet,
ja alkupiste on nyt kun pﾃ､ﾃ､tepiste.
No, joka ei mitﾃ､ﾃ､n jﾃ､rkeﾃ､, eikﾃｶ?
Joten nyt, mitﾃ､ voimme sanoa on meidﾃ､n on osa joukko koko 0.
Ja kun me mennyt Tﾃ､ssﾃ､ vaiheessa voimme nyt
taata, ettﾃ､ elementti 16 ei ole olemassa jono,
koska alkupiste ja pﾃ､ﾃ､tepiste ovat ristissﾃ､.
Ja niin se ei ole siellﾃ､.
Nyt, huomaa, ettﾃ､ tﾃ､mﾃ､ on hieman eri kuin alkupiste ja loppu
kohta on sama.
Jos olisimme olleet etsimﾃ､ssﾃ､ 17, se olisi
ollut array, ja aloituspiste ja loppupiste ettﾃ､ viime iterointia
ennen nﾃ､itﾃ､ pistettﾃ､ ristissﾃ､, olisimme lﾃｶytyi 17 siellﾃ､.
Vasta kun he ylittﾃ､vﾃ､t ettﾃ､ voimme taata, ettﾃ､ elementti ei
olemassa jono.
>> Joten vie paljon vﾃ､hemmﾃ､n vaiheet kuin lineaarinen haku.
Pahimmassa tapauksessa, meillﾃ､ oli jakaa luettelon n alkion
toistuvasti puolet lﾃｶytﾃ､ﾃ､ kohde, joko siksi kohdistuselementti
on jossain viimeisen alueeseen tai sitﾃ､ ei ole lainkaan.
Joten pahimmassa tapauksessa meidﾃ､n on jakaa array-- tiedﾃ､t?
Loki n kertaa; me on leikata ongelma
puolessa tietyn mﾃ､ﾃ､rﾃ､n kertoja.
Ettﾃ､ monta kertaa on log n.
>> Mikﾃ､ on parhaassa tapauksessa?
No, ensimmﾃ､inen kerta laskea keskipiste,
lﾃｶydﾃ､mme mitﾃ､ etsimme.
Kaikissa edellinen esimerkkejﾃ､ binary haku
Olemme juuri mennyt yli, jos meillﾃ､ olisi etsinyt elementti 15,
olisimme havainneet, ettﾃ､ heti.
Se oli aivan alussa.
Se oli keskipiste ensimmﾃ､inen yritys split
of jako binary haku.
>> Ja niin pahimmassa tapauksessa, binary haku toimii
in log n, joka on olennaisesti parempi kuin lineaarinen haku, pahimmassa tapauksessa.
Parhaassa tapauksessa binary haku toimii omega 1.
Joten binary haku on paljon parempi kuin lineaarinen haku,
mutta sinun tﾃ､ytyy kﾃ､sitellﾃ､ prosessi lajittelu array ennen kuin voit
hyﾃｶdyntﾃ､ﾃ､ valtaa binﾃ､ﾃ､rihaku.
>> Olen Doug Lloyd.
Tﾃ､mﾃ､ on CS 50.