>> Rob Bowden: Hi, unë jam Rob.
Si mund ne të punësojë një kërkim binar?
Le të gjeni.
Pra, vini re se këtë kërkim ne jemi duke shkuar për të zbatuar Recursively.
Ju gjithashtu mund të zbatojë kërko binar iteratively, kështu që nëse ju e bëri këtë,
kjo është përsosmërisht mirë.
>> Tani pari, le të mbani mend se çfarë Parametrat në kërkim janë menduar të jetë.
Këtu, ne shohim vlera int, e cila është menduar të jetë vlera e përdoruesit është
kërkoni për.
Ne e shohim array vlerave int, e cila është grup në të cilin ne jemi
kërkoni për vlerën.
Dhe ne shohim int n, e cila është gjatësia e array tonë.
>> Tani, gjëja e parë e parë.
Ne kontrolloni për të parë nëse n është e barabartë me 0, në cilin rast ne e kthimit të rreme.
Kjo është vetëm duke thënë se në qoftë se ne kemi një bosh array, vlera nuk është e qartë në një
array bosh, kështu që ne mund të kthimit të rreme.
>> Tani, ne të vërtetë duan të bëjnë binare kërko pjesë e kërkimit binar.
Pra, ne duam të gjetur në qendër element i kësaj grup.
Këtu, të themi të mesëm është e barabartë me n ndarë me 2, pasi elementi mesme është
do të jenë gjatësia e koleksion tona i ndarë me 2.
Tani ne jemi duke shkuar për të kontrolluar për të parë nëse element të mesëm është e barabartë me vlerën që jeni
kërkoni për.
Pra, nëse vlerat e mesme është e barabartë me vlerën, ne mund të kthehet e vërtetë që kemi gjetur
Vlera në grup tonë.
>> Por në qoftë se kjo nuk ishte e vërtetë, tani ne kemi nevojë për të bërë gjithkund rekursive
hap e kërkimit binar.
Ne kemi nevojë për të kërkuar ose për të majtë të array ose për të
mes të vektorit.
Kështu që këtu, të themi nëse vlerat në mes është më pak se vlera, që do të thotë se vlera
ishte më e madhe sesa mes e array.
Pra, vlera duhet të jetë në të djathtë të element që ne vetëm shikuar.
>> Pra këtu, ne do të kërko Recursively.
Dhe ne do të shikojmë se çfarë ne jemi duke kaluar për këtë në një të dytë.
Por ne jemi duke shkuar për të kërkuar të drejtën e elementit mesme.
Dhe në rastin tjetër, kjo do të thotë se Vlera ishte më pak se mesi i
array, dhe kështu që ne jemi duke shkuar për të kërkuar në të majtë.
Tani, e majta do të jetë pak më e lehtë për të parë.
Pra, ne shohim këtu se ne jemi Recursively duke e quajtur kërko ku i pari
Argumenti është, përsëri, vlera ne jemi duke kërkuar mbi të.
Argumenti dytë do të jenë array se ne ishim në kërkim gjatë.
Dhe elementi i fundit tani është e mesme.
Mos harroni parametri i fundit është int ynë n, kështu që është gjatësia e rrjet të.
>> Në thirrjen gjithkund rekursive për të kërkuar, ne jemi tani duke thënë se gjatësia e
array është e mesme.
Pra, nëse koleksion tona ishte i madhësisë 20 dhe ne kontrolluar në indeksin 10, pasi e mesme është
20 ndarë nga 2, që do të thotë ne jemi duke kaluar 10 si i ri
Gjatësia e array tonë.
Mos harroni se kur ju keni një rrjet të e gjatësi 10, që do të thotë të vlefshme
elemente janë në indekset 0 deri në 9.
Pra, kjo është pikërisht ajo që ne duam të specifikoni grup tonë të përditësuar - e majtë
grup nga elementi mesme.
>> Pra, duke kërkuar në të djathtë është pak më e vështirë.
Tani pari, le të marrë në konsideratë gjatësinë i array për të drejtën e
element mesme.
Pra, nëse koleksion tona ishte i madhësisë n, atëherë Grup i ri do të jetë i madhësisë n minus
minus mesme 1.
Pra, le të mendojnë për n minus qëndër.
>> Përsëri, në qoftë se array ishin të madhësisë 20 dhe ne ndani me 2 për të marrë e mesme,
kështu e mesme është 10, atëherë n minus mesme do të na japë 10, kështu që 10
elementet në të djathtë e mesme.
Por ne gjithashtu kemi këtë minus 1, pasi ne nuk duam të
përfshijnë në qendër vetë.
Pra, n minus mesme minus 1 na jep Numri i përgjithshëm i elementeve të së drejtës
i indeksit mesme në vektorit.
>> Tani këtu, mos harroni se e mesme parametër është array vlerat.
Pra këtu, ne jemi duke kaluar një Rifreskimi Vlerat array.
Kjo vlerat plus plus mesme 1 është në të vërtetë duke thënë Recursively telefononi
kërko, duke kaluar në një rrjet të ri, ku që grup i ri fillon në mes
plus një nga vlerat origjinale array tonë.
>> Një sintaksë alternative për këtë, tani që ju keni filluar të shihni pointers, është
Vlerat ampersand plus mesme 1.
Pra, kap adresën e mes plus një element i vlerave.
>> Tani, në qoftë se nuk keni qenë të rehatshme modifikuar një rrjet të tillë, ju
gjithashtu do të mund të zbatohet duke përdorur këtë një funksion recursive ndihmës, ku
se funksioni ndihmës merr më shumë argumente.
Pra, në vend që të marrë vetëm vlerën, array, dhe madhësia e array,
funksioni i ndihmës mund të marrë më shumë argumente, duke përfshirë indeksin më të ulët
se ju do të kujdeseni për në rrjet dhe indeksi sipërme që ju kujdeseni
rreth array.
>> Dhe kështu që mbajtja e dy më të ulët Indeksi dhe indeksi sipërme, ju nuk e bëni
nevojë për të kurrë të modifikuar Vlerat origjinale array.
Ju vetëm mund të vazhdojë të përdorni array vlerat.
Por këtu, vini re ne nuk kemi nevojë për një ndihmës funksionojë për sa kohë që ne jemi
të gatshëm për të modifikuar origjinal Vlerat array.
Ne jemi të gatshëm për të kaluar në një vlerat updated.
>> Tani, ne nuk mund të kërko binar mbi një grup që është unsorted.
Pra, le të marrë këtë ndahen.
Tani, vini re se lloj është e kaluara dy parametrat int vlerat, e cila është
array se ne jemi klasifikim, dhe int n, cila është gjatësia e vektorit që
ne jemi zgjidhja.
Pra, këtu ne duam të zbatojë një algorithm sorting
qe eshte o i N katror.
Ju mund të zgjidhni flluskë renditjeje, përzgjedhje lloj, apo futje lloj, ose
një lloj tjetër ne nuk kemi shihet në klasë.
Por këtu, ne do të përdorni përzgjedhjes lloj.
>> Pra, ne do të iterate mbi gjithë array.
E pra, këtu ne shohim se ne jemi iterating nga 0 deri n minus 1.
Pse jo të gjithë rrugën deri në n?
E pra, në qoftë se ne kemi renditur tashmë e parë n minus 1 elemente, atëherë
element shumë të fundit ajo që duhet tashmë të jenë të në vendin e duhur, në mënyrë klasifikim mbi
tërë array.
>> Tani, mos harroni se si përzgjedhja lloj punon.
Ne jemi duke shkuar për të shkuar në të gjithë array duke kërkuar për vlerën minimale në
array dhe të ngjit që në fillim.
Pastaj ne jemi duke shkuar për të shkuar në të gjithë array përsëri në kërkim të dytë
element më i vogël, dhe të ngjit që në pozicionin e dytë në
array, dhe kështu me radhë.
Pra, kjo është ajo që kjo është duke bërë.
>> Këtu, ne jemi duke parë se ne jemi vendosjen minimale aktuale
vlerë të indeksit i-th.
Pra, në përsëritje të parë, ne jemi duke shkuar të marrin në konsideratë vlera minimale që të jetë e
fillimi i array tonë.
Pastaj, ne do të iterate mbi Pjesa tjetër e array, duke kontrolluar të
të parë nëse ka ndonjë elemente të vogla se ai që ne jemi aktualisht
konsideruar minimale.
>> Kështu që këtu, vlerat j plus një të tillë - kjo është më pak se ajo që ne jemi aktualisht
konsideruar minimale.
Pastaj ne jemi duke shkuar për të rinovuar atë ne mendojmë se është minimale për të
Indeksi plus j 1.
Pra, bëni atë në të gjithë grup, dhe pas kësaj për loop, minimale
duhet të jetë element minimale nga Pozicioni i-th në rrjet.
>> Pasi që kemi, ne mund të bie në ujdi Vlera minimale në pozicionin i-
në rrjet.
Pra, kjo është vetëm një shkëmbim standarde.
Ne dyqan në një vlerë të përkohshëm - vlera i-th në rrjet -
vënë në vlerën e i-të në grup Vlera minimale që i takon atje,
dhe pastaj dyqan përsëri në ku vlera aktuale minimale përdoret për të
Vlera i-th në rrjet, në mënyrë se ne nuk kemi humbur atë.
>> Pra, që vazhdon në Përsëritje e ardhshme.
Ne do të fillojmë të shikojmë për të dytë Vlera minimale dhe futur që në
Pozita e dytë.
Në përsëritje të tretë, ne do të shikojmë për Vlera minimale e tretë dhe të futur
që në pozicionin e tretë, dhe kështu deri sa ne kemi një rrjet të renditura.
Emri im është Rob, dhe kjo ishte zgjedhja lloj.