>> 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.