>> ROB BOWDEN: Tere, ma olen Rob.
Kuidas me tööle binaarne otsing?
Uurime välja.
Seega pidage meeles, et see otsing me rakendada rekursiivselt.
Sa võid ka ellu binaarne otsing korduvalt, nii et kui sa seda tegid,
see on täiesti trahvi.
>> Nüüd esimene, pidagem meeles, mida parameetrid otsing on mõeldud.
Siin näeme, int väärtust, mis on peaks olema väärtus on kasutaja
otsivad.
Näeme int väärtusi massiivi, mis on massiiv, kus me oleme
otsivad raha.
Ja me näeme, int n, mis on pikkus meie massiivi.
>> Nüüd esimene asi esimesena.
Me vaadata, kui n on 0, on mille puhul me tagasi false.
See on lihtsalt öeldes, kui meil on tühi massiiv, väärtus ei ole kindlasti
tühi massiiv, nii et me saame tagasi false.
>> Nüüd, kui me tegelikult tahame teha binaarne search osa binaarne otsing.
Niisiis, me tahame leida kuldset element selle massiivi.
Siin me ütleme, keskel on n jagatud 2, kuna keset element
saab olema pikkuse meie array jagatud 2.
Nüüd me ei kavatse vaadata, kui keskel element võrdub raha oleme
otsivad.
Nii et kui väärtuste keskel võrdne väärtus, me võib naasta tõsi, sest me leidsime
väärtus meie massiivi.
>> Aga kui see ei ole tõsi, nüüd meil on vaja teha rekursiivne
samm binaarne otsing.
Meil on vaja otsida kas vasakule massiivi või
keset massiiv.
Nii et siin me ütleme, kui väärtuste keskel on väiksem väärtus, see tähendab, et väärtus
oli suurem kui keskel massiivi.
Seega väärtus peab olema õigus element, mida me lihtsalt vaatasin.
>> Nii et siin me läheme otsi rekursiivselt.
Ja me vaatame, mida me läbiva seda võetakse teine.
Aga me kontrollime, õigus keset element.
Ja teisel juhul tähendab see, et väärtus oli alla keskele
massiiv, ja nii me otsida üles vasakule.
Nüüd vasakule saab olema natuke lihtsam vaadata.
Niisiis, me näeme siin, et me oleme rekursiivselt kutsudes otsing kui esimene
argument on jälle väärtus me otsime üle.
Teine argument saab olema massiivi otsiti läbi.
Ja viimane element on nüüd keskel.
Mäleta viimane parameeter on meie int n, nii et see pikkus meie massiivi.
>> In rekursiivne kõne otsida, me oleme nüüd selge, et pikkus
massiiv on keskel.
Niisiis, kui meie array oli suurus 20 ja me otsitakse indeksiga 10, sest keskel on
20 jagatud 2, see tähendab, et me oleme möödaminnes 10 nagu uus
pikkus meie massiivi.
Pea meeles, et kui sul on array pikkusega 10, mis tähendab, et kehtivad
elemendid on indeksid 0 kuni 9.
Nii et see on täpselt see, mida me tahame täpsustada meie uuendatud array - vasak
array keskelt element.
>> Niisiis, otsin õige on natuke raskem.
Nüüd esimene Vaatleme pikkus massiivi paremal
keskel element.
Niisiis, kui meie massiivi oli suurus n siis uus massiiv suurusega n miinus
keskel miinus 1.
Niisiis, oletame, mõtlema n miinus keskel.
>> Jällegi, kui massiivi olid suurusega 20 ja me jagame 2 saada keskel
nii keskel on 10, siis n miinus keskel läheb meile 10, nii et 10
elemente paremal keskel.
Aga meil on ka see miinus 1, sest me ei taha
sisaldama keskel ise.
Nii n miinus keskel miinus 1 annab meile koguarv elemente paremal
Keskmise index massiiv.
>> Nüüd, pea meeles, et keskmine parameeter on väärtuste massiivi.
Nii et siin me oleme kulgeb uuendatud väärtuste massiivi.
See väärtused pluss keskel pluss 1 on tegelikult öelda rekursiivselt helistada
otsing, mis kulgeb uus massiiv, kus et uus massiiv hakkab keset
pluss üks meie algseaded massiivi.
>> Asendusliikme süntaks, et nüüd, olete hakanud näha suunanäitajaks, on
ampersand väärtuste keskel pluss 1.
Niisiis, ostke aadress keskel pluss üks element väärtused.
>> Nüüd, kui te ei ole mugav muuta massiivi niimoodi, siis
oleks ka rakendanud kasutades rekursiivne abistaja funktsiooni, kus
et abistaja funktsiooni võtab rohkem argumente.
Seega selle asemel, et lihtsalt raha, massiivi ning suurust massiivi
abistaja funktsiooni võiks rohkem argumente, sealhulgas alaindeksi
et teil oleks hooli massiivi ja ülemine register, et sa hoolid
umbes massiiv.
>> Ja jälgida nii madalam indeks ja ülemine register, sa ei pea
pea kunagi muutma Algsete massiivi.
Sa võid jätkata kasuta väärtuste massiivi.
Aga siin, teate, me ei pea abimees toimida nii kaua kui me oleme
valmis muuta esialgse väärtuste massiivi.
Oleme valmis läbima ajakohastatud väärtusi.
>> Nüüd ei saa me Kahendotsingupuu üle massiivi sortimata.
Nii, lähme seda lahendada.
Nüüd märkate, et sort on viimase kahe parameetrite int väärtusi, mis on
massiivi pakin ja int n, mis on pikkus massiivi
pakin.
Nii, siin me tahame ellu sorteerimine algoritm
mis o n ruudus.
Sa võid valida mull sorteerida valik sort või sisestamise sort, või
mõne muu sort meil ei näinud klassis.
Aga siin me läheme kasutage valikut sort.
>> Niisiis, me kinnitada, kogu massiiv.
Noh, siin me näeme, et me iterating 0 kuni n miinus 1.
Miks mitte kõik viis kuni n?
Noh, kui me oleme juba valmis esimene n miinus 1 elemente, siis
väga viimane element, mida peab juba olema õiges kohas, nii et sorteerimine üle
kogu massiiv.
>> Nüüd pidage meeles, kuidas valik sort töötab.
Me läheme üle kogu antennide massiivi otsin minimaalse väärtuse
massiivi ja kepp, mis alguses.
Siis me lähme kogu array jälle otsin teise
väikseim element ja kepp, mis aasta teisel positsioonil
massiiv, ja nii edasi.
Nii see on, mida see teeb.
>> Siin me näeme, et me oleme millega praegune miinimum
väärtust i-nda indeks.
Nii esimese iteratsiooni, me kaaluda minimaalne väärtus olla
algus meie massiivi.
Siis me Käi ülejäänud massiiv, kontrollides, et
vaata, kas on mingeid elemente väiksem üks, et me oleme praegu
arvestades minimaalne.
>> Nii et siin, väärtustab j pluss üks - see on vähem kui see, mida me praegu
arvestades minimaalne.
Siis me uuendada mida me arvame, on minimaalne, et
indeks j pluss 1.
Niisiis, teha kogu massiiv, ja pärast seda loop, minimaalne
peaks olema minimaalne elemendi i-nda positsiooni massiiv.
>> Kui meil on, et me ei vaheta minimaalse väärtuse i-nda positsiooni
massiiv.
Nii et see on lihtsalt standard swap.
Me salvestada ajutiselt väärtus - i-nda väärtuse massiivi -
pannakse i-nda väärtuse massiivi minimaalne väärtus, mis kuulub sinna,
ja siis hoidke tagasi, kui praegune minimaalne väärtus varem
i-nda väärtuse massiivi, nii et me ei kaota.
>> Nii, et jätkub järgmise iteratsiooni.
Hakkame otsima teist minimaalne väärtus ning lisada, et arvesse
teisel positsioonil.
Kolmandal iteratsiooni, me otsima Kolmanda minimaalne väärtus ning sisesta
et kolmandasse asendisse ning edasi, kuni meil on sorteeritud massiiv.
Minu nimi on Rob ja see oli valik sort.