ROB BOWDEN: Hei, olen Rob. Miten käytämme binäärihaku? Otetaan selvää. Niin, huomaa, että tämä haku aiomme toteuttaa rekursiivisesti. Voisit myös toteuttaa binäärihaku iteratiivisesti, joten jos teit sen, se on täysin kunnossa. 

Nyt ensimmäinen, muistakaamme, mitä parametreja haku on tarkoitus olla. Tässä näemme int-arvo, joka on tarkoitus olla arvoa käyttäjä on etsivät. Näemme int arvot array, joka on joukko, jossa olemme etsivät arvon. Ja me näemme int n, joka on pituus meidän array. 

Nyt ensimmäinen asia ensin. Tarkistamme jos n = 0, in jolloin palaamme vääriä. Se vain sanoo, jos meillä on tyhjä array, arvo ei selvästikään ole tyhjä jono, jotta voimme palauttaa false. 

Nyt me todella haluamme tehdä binary search osa binäärihaku. Joten, haluamme löytää keskellä osa tätä array. Täällä sanomme keskellä yhtä kuin n jaettu 2, koska keskimmäinen osa on olemaan pituus meidän array jaettuna 2. Nyt aiomme tarkistaa, onko keskielementti vastaa arvoa olemme etsivät. Joten jos arvot keskimmäinen vastaa arvoa, me voi palata paikkansa, sillä löysimme arvo meidän array. 

Mutta jos se ei ollut totta, nyt meidän täytyy tehdä rekursiivinen vaiheen binäärihaku. Meidän täytyy etsiä joko jäljellä array tai keskellä jono. Joten tässä, sanomme jos arvot keskellä on pienempi kuin arvo, se tarkoittaa, että arvo oli suurempi kuin keski- jono. Joten arvon on oltava oikealla puolella elementti, että me vain katsoi. 

Joten tässä, me aiomme etsi rekursiivisesti. Ja me tarkastelemme mitä olemme ohimennen Tämän toisessa. Mutta aiomme hakevat oikealla keskellä elementin. Ja toisessa tapauksessa, se tarkoittaa, että -arvo oli pienempi kuin keskellä jono, ja niin aiomme etsiä vasemmalle. Nyt, vasen tulee olemaan hieman helpompi katsoa. Niin, tässä näemme, että olemme rekursiivisesti soittamalla Missä ensin argumentti on, jälleen, arvo Etsimme yli. Toinen argumentti tulee olemaan array että olimme etsivät yli. Ja viimeinen osa on nyt keskellä. Muista viimeinen parametri on meidän int n, niin se pituus meidän array. 

Vuonna rekursiivinen kutsu etsiä, olemme sanovat nyt, että pituus array on keskellä. Joten, jos meidän joukko oli koko 20 ja me etsinyt indeksissä 10, koska keskellä on 20 jaettuna 2, se tarkoittaa, että olemme läpäisivät 10 uudeksi pituus meidän array. Muista, että kun sinulla on array pituuden 10, se tarkoittaa voimassa elementit ovat indeksejä 0 kautta 9. Joten tämä on juuri sitä, mitä haluamme tarkensimme päivitetty array - vasen array keskeltä elementti. 

Joten, etsii oikealla on hieman vaikeaa. Nyt ensimmäinen Tarkastellaan pituus array oikealle keskielementti. Joten, jos meidän joukko oli koko n jälkeen new Array tulee olemaan kooltaan n miinus keski miinus 1. Joten, nyt ajatella n miinus keskellä. 

Jälleen, jos joukko olivat kooltaan 20 ja jaamme 2 saada keskelle, niin keskellä on 10, niin n miinus keskellä aikoo antaa meille 10, joten 10 elementtejä oikealla keskellä. Mutta meillä on myös tämä miinus 1, koska emme halua kuuluu keskellä itse. Joten n miinus keskellä miinus 1 antaa meille kokonaismäärä elementtejä oikea Keskimmäisen indeksin array. 

Nyt täällä, muista, että keskimmäinen parametri on arvojen jono. Joten tässä, jossa olemme päivitetyt arvot array. Tämä arvoja plus keskellä plus 1 on todella sanovat rekursiivisesti soittaa haku, ohimennen new Array, jossa että uudet array alkaa keskellä plus yksi alkuperäiset arvot array. 

Vaihtoehtoinen syntaksi, että nyt olet alkanut nähdä viitteitä, on Et-arvojen keskellä plus 1. Joten, tartu osoite keskellä plus yksi osa arvoista. 

Nyt, jos et olisi mukava muuttamalla array kuin, että voit olisi myös voinut toteuttaa tämän käyttämällä rekursiivinen auttaja-toiminto, jossa että auttaja toiminto vie lisää argumentteja. Joten sen sijaan että vain arvo, array, ja taulukon koko, auttajafunktio voisi ottaa enemmän argumentteja, mukaan lukien alaindeksi että olisit välitä jono ja ylempi indeksi että välität noin array. 

Ja niin pitää kirjaa sekä alemman indeksi ja ylempi indeksi, et tarvitse koskaan muuttaa alkuperäiset arvot array. Voit vain jatkaa käyttää arvoja array. Mutta täällä, huomaa emme tarvitse auttaja toimivat niin kauan kuin olemme halukas muuttamaan alkuperäistä arvot array. Olemme valmiita kulkemaan päivitetyt arvot. 

Nyt emme voi binäärihaku yli array, joka on lajittelemattoman. Joten, hoidetaan homma kuntoon. Nyt, huomaa, että sellainen on viimeisen kahden parametrit int arvot, jotka on array että olemme lajittelu, int n, joka on pituus array, joka olemme lajittelu. Niin, tässä haluamme toteuttaa Lajittelualgoritmi , joka on O n potenssiin. Voisit valita kupla lajitella, valinta lajittele tai lisäyslajittelu tai muu sellainen meillä ole nähnyt luokassa. Mutta täällä, me aiomme Käytä valinta lajitella. 

Joten, aiomme kerrata koko ryhmän yli. No, tässä näemme, että olemme iteroimalla 0-n miinus 1. Miksi ei kaikki tavalla jopa n? No, jos olemme jo järjestetty ensimmäinen n miinus 1 elementit, sitten Aivan viimeinen elementti, mitä on jo oltava oikeassa paikassa, joten lajittelu yli koko ryhmän. 

Nyt muistan miten valinta lajitella toimii. Aiomme mennä koko ryhmän yli etsii pienimmän arvon array ja keppiä että alussa. Sitten aiomme mennä yli koko array taas etsii toista pienin alkio, ja keppi toisessa asemassa jono, ja niin edelleen. Niin, sitähän tämä on tekemässä. 

Täällä, me näemme, että olemme asetetaan nykyinen minimi arvo i: nnen indeksin. Joten ensimmäistä iterointia, aiomme harkitsemaan pienin arvo on alussa meidän array. Sitten aiomme kerrata yli Loput array, tarkkailun onko olemassa mitään osia pienempi kuin yksi että olemme tällä hetkellä huomioon minimiin. 

Joten tässä, arvot j plus yksi - se on vähemmän kuin mitä meillä tällä hetkellä huomioon minimiin. Sitten aiomme päivittää mitä mielestämme on minimi Hakemisto J plus 1. Joten, että koko jono, ja tämän jälkeen silmukka, minimi pitäisi olla vähintään elementin i: nnen aseman jono. 

Kun meillä on tuo, voimme vaihtaa minimiarvo osaksi i. asema jono. Joten tämä on vain standardi swap. Tallennamme väliaikaiseen arvo - i: nnen arvon array - otetaan i: nnen arvon array pienin arvo, joka kuuluu sinne, ja sitten tallentaa takaisin, jos nykyinen minimiarvo käytetään olla i: nnen arvon jono, niin että emme menetä sitä. 

Niin, että jatkuu seuraavaan toistoon. Aloitamme etsii toista minimiarvo ja aseta sen osaksi toiseen asentoon. Kolmantena iteraatio, me etsiä kolmannen minimiarvo ja insertti että kolmanteen asentoon, ja niin kunnes olemme lajitellun array. Nimeni on Rob, ja tämä oli valinta lajitella.