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.