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.