>> ROB Bowden: Živjo, jaz sem Rob.
Kako bomo uporabili binarno iskanje?
Pa poglejmo.
Torej, upoštevajte, da to iskanje gremo izvajati rekurzivno.
Lahko bi tudi izvajala binarno iskanje iterativno, tako da, če si to storil,
To je popolnoma v redu.
>> Zdaj prvič, spomnimo se, kaj Parametri za iskanje so mišljeni.
Tukaj vidimo, int vrednost, ki je naj bi bila vrednost uporabnik
išče.
Vidimo array int vrednote, ki je niz, v katerem smo
išče vrednosti.
In vidimo, int n, ki je Dolžina naše matrike.
>> Zdaj, prva stvar najprej.
Preveriti moramo, da vidim, če je n enak 0, v tem primeru se vrnemo false.
To je samo rekel, če imamo prazna matrika, vrednost nedvomno ni v
prazen niz, tako da se lahko vrnemo false.
>> Zdaj smo dejansko želeli narediti binarno Iskanje del binarnega iskanja.
Torej, želimo, da bi našli sredino element v tem polju.
Tukaj smo rekli srednji enaka n razdeljen z 2, saj srednji element
bo dolžina naš niz deliti z 2.
Zdaj bomo, da preverite, če je srednji element enaka vrednosti borimo
išče.
Torej, če vrednosti srednji enaka vrednosti, smo lahko vrne true, saj smo ugotovili,
vrednost v naši matriki.
>> Če pa to ni res, zdaj moramo narediti rekurzivno
korak binarnega iskanja.
Moramo iskati bodisi levo matrike ali
Srednji matrike.
Tako da tukaj smo rekli, če vrednosti na sredini je manjša od vrednosti, ki pomeni, da je vrednost
je večja od sredine matrike.
Torej mora biti vrednost na desni strani element, ki smo pravkar pogledal.
>> Torej, tukaj, bomo iskanje rekurzivno.
In bomo pogledali, kaj smo mimo to v sekundi.
Ampak bomo iskati za desno od srednjega elementa.
In v drugem primeru, to pomeni, da je bila vrednost nižja od sredine
matrika, zato bomo za iskanje na levi strani.
Zdaj, leva se bo nekoliko lažje gledati.
Torej, vidimo tukaj, da smo rekurzivno kliče iskanje kjer prvi
argument je, še enkrat, vrednost iščemo več.
Drugi argument, ki se bo matrika, ki smo iskali več.
In zadnji element je zdaj srednja.
Ne pozabite, zadnji parameter je naša int n, tako da je dolžina našega matrike.
>> V rekurzivnega klica za iskanje, smo Zdaj pravijo, da dolžina
Niz je srednja.
Torej, če je bila naša paleta velikosti 20 in smo Iskali pri indeksu 10, saj je srednji
20 deljeno z 2, kar pomeni, da smo poteka 10 kot nova
Dolžina naše matrike.
Ne pozabite, da če imate niz dolžine 10, kar pomeni, da velja
elementi so indeksi od 0 do 9.
Torej, to je točno tisto, kar smo želeli določajo našo posodobljeno paleto - levo
matrika iz srednjega elementa.
>> Torej, je videti na desni strani je nekoliko težje.
Zdaj najprej, kaj je upoštevati dolžino matrike na desni strani
srednji element.
Torej, če je bila naša paleta velikosti n, potem Nova matrika bo v velikosti n minusom
srednji minus 1.
Torej, kaj je razmišljati n minus sredini.
>> Again, če bi bila matrika velikosti 20 in delimo z 2, da bi dobili na sredini,
Tako srednji je 10, potem je n minus srednji se dogaja, da nam je 10, torej 10
Elementi na desni sredini.
Vendar imamo tudi ta minus 1, saj ne želimo, da se
vključujejo sredini sam.
Torej n minus srednja minus 1 pa nas daje Skupno število elementov v desno
srednjega indeksa v matriki.
>> Zdaj tukaj, ne pozabite, da srednji parameter je niz vrednosti.
Tako da tukaj smo vrtaš posodobljene vrednosti matrike.
Te vrednosti plus srednji plus 1 je dejansko rekel rekurzivno pokličite
iskanje, ki poteka v novem polju, kjer da nova mreža začne v sredini
plus eden od naših prvotne vrednosti matrike.
>> Nadomestnega sintaksa za to, zdaj, Začeli ste videli kazalci, je
ampersand vrednosti srednji plus 1.
Torej, zgrabite naslov sredini plus en element vrednot.
>> Zdaj, če ne bi bilo udobno spreminjanje paleto, kot je ta, boste
Lahko bi tudi izvajala to uporabo rekurzivna funkcija pomočnik, kjer
to funkcijo pomočnika traja več argumentov.
Torej, namesto da bi samo vrednost, matrika in velikostjo polja,
Funkcija pomočnik lahko traja več trditev tudi spodnji indeks
da bi vas skrbi v matriki in zgornji indeks, ki vam ni vseeno
o matriki.
>> In tako sledenja tako nižja indeks in zgornji indeks, pa ne
morali kdaj spremeniti izvirne vrednosti matrike.
Lahko samo še uporabite niz vrednot.
Ampak tukaj, opazili ne potrebujemo pomočnika delujejo tako dolgo, kot smo
pripravljeni spremeniti izvirnik Vrednosti matrike.
Mi smo pripravljeni, da prenese v an dodani vrednosti.
>> Zdaj ne moremo binarno iskanje na matrika, ki je, razvrščeni.
Torej, kaj je dobil to urejeno.
Zdaj, opazili, da je nekako mimo dveh parametri int vrednosti, ki je
matrika, ki smo razvrščanje in int n, ki je dolžina polja, ki
smo sortiranje.
Torej, tukaj želimo izvajati sortiranje algoritem
da je o n kvadrat.
Lahko izbirate mehurček sortiranje, izbor sort, ali vstavljanje sort, ali
nekatere druge vrste nismo videli v razredu.
Ampak tukaj, gremo na uporabite za izbiro vrste.
>> Torej, bomo Ponovil prek celotnega niza.
No, pa smo videli, da smo ponavljanjem od 0 do n minus 1.
Zato ni vse tja do n?
No, če smo že razporejene prvi n minus 1 elemente, nato
Zelo zadnji element, kaj mora že biti v pravem mestu, tako sortiranje nad
celoten niz.
>> Vedeti moramo, kako izbira nekako deluje.
Mi smo šli prek celotnega niza išče najmanjšo vrednost v
matrika in palico, ki na začetku.
Potem smo šli v celotnem obdobju Niz spet iščejo drugi
najmanjši element, in palico, ki v drugem položaju v
matrika, in tako naprej.
Torej, to je tisto, kar to počne.
>> Tukaj smo videli, da smo postavimo trenutni minimum
vrednost indeksa i-tega.
Torej na prvi ponovitvi, gremo preučiti minimalno vrednost, da se
začetek našega array.
Nato bomo Ponovil več Preostali del matrike, preverjanje, da
glej če obstajajo elementi manjši od tisti, ki smo trenutno
glede na minimum.
>> Torej, tukaj, vrednote j plus eno - to je manj, kot smo trenutno
glede na minimum.
Potem bomo posodobiti, kar mislimo, da je najmanjše
Indeks j plus 1.
Torej, da je v celotnem polju, in potem to za zanke, najmanj
mora biti minimalna element iz Položaj i-ti v matriki.
>> Ko bomo imeli, da bomo lahko swap najmanjša vrednost v položaj i-
v matriki.
Torej to je samo standardni swap.
Hranimo v začasni vrednosti - Vrednost i-ti v matriki -
dajo v vrednosti i-tega v matriki najmanjša vrednost, ki sodi tja,
in nato shranjevanje nazaj v kadar Sedanja minimalna vrednost, s katero se
i-ta vrednost v matriki, tako da nismo izgubili.
>> Tako, da se nadaljuje Naslednja ponovitev.
Bomo začeli iskati drugo Najnižja vrednost in vstavite, da v
drugi položaj.
Na tretji ponovitvi, bomo iskali tretja najnižja vrednost in vložek
da v tretjem položaju, in tako dokler imamo urejen niz.
Moje ime je Rob, in to je bil izbor sort.