>> ROB BOWDEN: Hæ, ég er Rob.
Hvernig eigum við að ráða tvöfaldur leit?
Skulum finna út.
Svo, athugið að leitina við erum að fara að hrinda í framkvæmd í undirmöppum.
Þú gætir líka innleiða tvöfaldur leit iteratively, þannig að ef þú gerðir það,
það er fullkomlega í lagi.
>> Nú fyrst skulum við muna hvað breytur til að leit er ætlað að vera.
Hér sjáum við INT gildi, sem er ætlast til að vera gildið sem notandinn er
leita að.
Sjáum við int gildi array, sem er fylki sem við erum
leita að gildi.
Og við sjáum int n, sem er lengd fylkisins okkar.
>> Nú, fyrsta sem fyrst.
Við athuga hvort n jafngildir 0, í því tilviki sem við return false.
Það er bara að segja ef við höfum tóm array, gildi er greinilega ekki í
tómt array, svo við getum skila falskur.
>> Nú viljum við í raun að gera tvöfaldur leita hluti af tvöfaldur leit.
Svo viljum við að finna miðju þáttur í þessu fylki.
Hér segjum við miðja jafngildir n skipt um 2, frá því um miðja þátturinn er
fara til vera the lengd array okkar deilt með 2.
Nú við erum að fara að athuga hvort að miðja þáttur jafnt gildi við séum
leita að.
Þannig að ef gildi miðja jafnt gildi, við getur skilað satt þar fundum við
gildi í array okkar.
>> En ef það var ekki satt, nú við þurfum að gera endurkvæma
skref af tvöfaldur leit.
Við þurfum að leita annað hvort til vinstri fylkisins eða til
miðja fylking.
Svo hér, segjum við ef gildin á miðjunni er minna en gildi, sem þýðir að verðmæti
var meiri en um miðja í fylkinu.
Þannig að gildi verður að vera til hægri á þáttur sem við horfði bara á.
>> Svo hér erum við að fara að leita í undirmöppum.
Og við munum líta á það sem við erum að brottför á því á sekúndu.
En við erum að fara að leita að því rétt af miðjum frumefni.
Og í öðrum tilvikum, sem þýðir að gildi var minna en the miðja af the
array, og þannig að við ætlum að leita til vinstri.
Nú, vinstri er að fara að vera svolítið auðveldara að líta á.
Svo sjáum við hér að við erum endurkvæmt starf leita þar sem fyrsta
rifrildi er, aftur, gildi við erum að leita yfir.
Seinni rök er að fara að vera array sem við vorum að leita á.
Og síðasti þátturinn er nú miðja.
Muna síðustu breytu er int okkar n, þannig að það er lengd array okkar.
>> Í endurkvæma hringja til að leita, við erum nú að segja að við lengd
array er miðja.
Svo, ef array okkar var stærð 20 og við leita í vísitölu 10, þar miðja er
20 deilt með 2, sem þýðir að við erum liggur 10 sem ný
lengd array okkar.
Mundu að þegar þú ert með array lengd 10, sem þýðir að í gildi
þættir eru í vísitölunum 0 til 9.
Þannig að þetta er einmitt það sem við viljum tilgreina uppfærð array okkar - vinstri
array frá miðju frumefni.
>> Svo, að leita til hægri er svolítið erfiðara.
Nú fyrst skulum við íhuga lengd í fylkinu til hægri á
miðja þáttur.
Þannig að ef array okkar var af stærðinni N, þá er Ný fylking mun vera af stærð n mínus
miðja mínus 1.
Svo, við skulum hugsa um n mínus miðju.
>> Aftur, ef array voru af stærð 20 og við deilum með 2 til að fá miðju,
svo miðju er 10, þá n mínus miðja er að fara að gefa okkur 10, svo 10
þættir til hægri miðju.
En við höfum líka þessa mínus 1, þar sem við viljum ekki að
fela miðju sjálft.
Svo n mínus miðja mínus 1 gefur okkur heildarfjöldi staka til hægri
af miðjum vísitölu í array.
>> Nú hér, muna að miðja breytu er gildi array.
Svo hér erum við að standast uppfærð gildi array.
Þetta gildi auk miðja plús 1 er í raun að segja endurkvæmt kalla
leit, liggur í nýju fylki, þar sem að nýja array byrjar í miðju
plús einn af upprunalegu gildi okkar fylki.
>> Varamaður setningafræði fyrir það, nú þegar þú hefur byrjað að sjá ábendingum, er
merkið gildi miðja auk 1.
Svo, grípa veffang miðjunni plús einn þáttur í gildi.
>> Nú, ef þú værir ekki ánægð breyta fjölda svona, þú
gæti einnig hafa innleitt þetta með endurkvæma hjálpar virka, þar
sem hjálpar virka tekur fleiri rök.
Svo í stað þess að taka bara gildi, array, og the stærð af the array,
sem hjálpar virka gæti tekið meira rök, þar á meðal lægri vísitölu
að þú myndir hugsa um í array og efri vísitölu sem þér þykir vænt
um fylki.
>> Og svo halda utan um bæði lægri vísitölu og efri vísitölu, þú gerir ekki
þarf að alltaf breyta upprunalegt horf array.
Þú getur bara haldið áfram að nota gildin array.
En hér, taka við þurfum ekki hjálpar virka svo lengi sem við erum
tilbúnir til að breyta upprunalegu gildi array.
Við erum tilbúnir til að fara í uppfærða gildi.
>> Nú getum við ekki tvöfaldur leit yfir fylki sem er óflokkað.
Svo skulum við fá þessa tegund út.
Nú, taka þessi tegund er framhjá tveimur breytur int gildi, sem er
array sem við erum að flokka, og INT n, sem er lengd fylkingu sem
við erum að flokka.
Svo, hér við viljum að innleiða á að flokka reiknirit
sem er o af n í öðru veldi.
Þú gætir valið kúla tagi, úrval tegund, eða innsetning tegund, eða
einhver önnur tegund sem við höfum ekki séð í bekknum.
En hér erum við að fara að nota val konar.
>> Svo erum við að fara að iterate yfir allt array.
Jæja, hér sjáum við að við erum iterating frá 0 til N mínus 1.
Af hverju ekki alla leið upp til n?
Jæja, ef við höfum þegar raðað fyrst n mínus 1 atriði, þá
mjög síðustu þáttur hvað verður þegar að vera á réttan stað, þannig að flokkun á
Fylkið.
>> Nú, muna hvernig val Raða virkar.
Við ætlum að fara yfir allt array að leita að lægsta gildi í
array og stafur sem í upphafi.
Svo ætlum við að fara yfir allt array aftur að leita fyrir þá síðari
Minnsta þáttur, og stafur sem í annarri stöðu í
array, og svo framvegis.
Svo, það er það sem þetta er að gera.
>> Hér erum við að sjá að við erum setja núverandi lágmarki
gildi til i-ta vísitölunni.
Svo á fyrsta endurtekning, við erum að fara til að fjalla um lágmarks gildi að vera
byrjunin á fjölda okkar.
Þá erum við að fara að iterate yfir Afgangurinn af array, stöðva til
sjá hvort einhver atriði minni en sá sem við erum nú
miðað lágmarki.
>> Svo hér, gildi j plús einn - það er minna en það sem við erum nú
miðað lágmarki.
Þá erum við að fara að uppfæra það við höldum að sé lágmark að
Vísitala J auk 1.
Svo, gera það á öllu fylkinu, og eftir þetta fyrir lykkju, lágmarks
ætti að vera lágmarks þáttur frá i-th staða í array.
>> Þegar við höfum það getum við skipti á Lægsta gildi í i-ta stöðu
í array.
Svo er þetta bara staðall skipti.
Við geymum í tímabundinni gildi - i-th gildi í fylkinu -
setja í i-ta gildi í fylkinu sem lágmarks gildi sem tilheyrir þar,
og síðan geyma aftur í þar sem Núverandi lágmarksgildi notað til að vera
I-th gildi í fylkinu, svo að við vildum ekki missa það.
>> Svo, sem heldur áfram á næsta endurtekning.
Við munum byrja að leita fyrir þá síðari lágmarks gildi og setja það inn í
seinni stöðuna.
Á þriðja endurtekning, munum við leita þriðja lágmarks gildi og settu
sem í þriðju stöðuna sem, og svo á þar til við höfum raðað fylki.
Mitt nafn er Rob, og þetta var val konar.