[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 ​​vä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.