[TÓNLIST spila] 

DOUG LLOYD: Allt í lagi. Svo er tvöfaldur leita að algrím við getum notað að finna stak inni fylki. Ólíkt línuleg leit, það krefst sérstök skilyrði að vera uppfyllt fyrirfram, en það er svo miklu meira duglegur ef að ástand er í raun uppfyllt. 

Svo er það hugmynd hér? það er gjá og sigra. Við viljum draga úr stærð leitarsvæðinu um helming í hvert skipti í því skyni að finna miða númer. Þetta er þar sem það skilyrði kemur inn í leik, þó. Við getum aðeins áhrif á afl útrýming helmingur af þeim þáttum án þess þó að horfa á þá ef array er raðað. 

Ef það er heill blanda upp, við getum ekki bara úr böndunum henda helmingur af þeim þáttum, vegna við vitum ekki hvað við erum að fleygja. En ef array er raðað, við getum gert það, vegna þess að við vita að allt til vinstri á hvar við erum núna verður að vera lægra en gildi við erum nú á. Og allt til rétt um hvar við erum verður að vera hærri en gildið við erum nú að horfa á. 

Svo er það sauðakóðanum skref fyrir tvöfaldur leit? Við endurtaka þetta ferli þar til array eða, eins og við halda áfram í gegnum, undir fylki, smærri stykki af upprunalega array, af stærð 0. Reikna miðpunkt af núverandi undir fylkisins. 

Ef gildið sem þú ert að leita að er í því frumefni af the array, hætta. Þú fannst það. Það er frábært. Annars, ef miðað er minna en það sem er á miðju, þannig að ef verðmæti við erum að leita fyrir er lægra en það sem við sjáum, endurtaka þetta ferli aftur, en breyta endastað stað af því að vera upprunalega ljúka fullt fjölbreytta, að vera bara til vinstri þar sem við horfði bara. 

Við vissum að miðja var of hár, eða miða var minna en miðju, og svo það verður að vera til, ef það er til á öllum í fylkinu, einhvers staðar vinstra megin við miðpunkt. Og svo við munum stilla array staðsetningu bara til vinstri á miðju sem nýr endir benda. Hins vegar ef miðað er meiri en það er á miðju, við gerum nákvæmlega sama ferli, en í staðinn erum við breyta upphafsstað að vera bara til hægri miðpunkt við reiknað bara. Og þá byrjum við ferlið aftur. 

Skulum sjón þetta í lagi? Svo er það mikið að fara og hér, en hér er fylki af 15 þáttum. Og við erum að fara að vera að halda utan af a einhver fjöldi fleiri efni í þetta sinn. Svo í línuleg leit, við vorum bara umhyggju miða. En í þetta sinn við viljum sama um hvar erum við farin að líta, þar við erum hætt að leita, og hvað er miðpunkt af núverandi array. Svo hér við fara með tvöfaldur leit. Við erum nokkuð mikið gott að fara, ekki satt? Ég ætla bara að fara að setja niður neðan hér sett af vísitölum. Þetta er í rauninni bara það sem þáttur fylkisins við erum að tala um. Með línuleg leit við umönnun, að því leyti sem vér þarf að vita hversu margir þættir sem við erum iterating yfir, en við gerum ekki raunverulega sama hvað þáttur við erum nú að horfa á. Í tvöfaldur leit, gera við. Og svo þeir eru bara það sem smá leiðbeiningar. 

Svo við getum byrjað, ekki satt? Jæja, ekki alveg. Mundu það sem ég sagði um tvöfaldur leit? Við getum ekki gert það á Óflokkaður array eða annað, við erum ekki að tryggja að ákveðnir þættir eða gildi ekki vera tilviljun hent þegar við bara ákveðið að hunsa helmingur fylkisins. 

Svo stíga einn með tvöfaldur leit er þú verður að hafa flokkað array. Og þú getur notað eitthvað af flokkun reiknirit sem við höfum talað um til að fá þig til að staða. Svo nú erum við í þeirri stöðu að við getum gert tvöfaldur leit. 

Svo skulum endurtaka ferlið skref fyrir skref og halda utan um hvað er að gerast sem við förum. Svo fyrsta sem við þurfum að gera er að reikna miðpunkt núverandi array. Jæja, munum við segja að við erum fyrst af allt, leita að verðmæti 19. Við erum að reyna að finna númerið 19. Fyrsti þáttur af þessu array er staðsett á vísitölu núll, og síðast þáttur af þessu array er staðsett á vísitölu 14. Og svo við munum kalla þá upphaf og lok. 

Svo við reiknum miðpunkt með bæta 0 plús 14 deilt með 2; nokkuð augljóst miðpunkt. Og við getum sagt að miðpunkt er nú 7. Svo er 15 það sem við erum að leita að? Nei það er ekki. Við erum að leita að 19. En við vitum að 19 er meiri en það sem við fundum á miðjunni. 

Svo er það sem við getum gert breyta upphafsstað að vera bara til hægri af miðpunkt, og endurtaka ferlið aftur. Og þegar við gerum það, segjum við nú nýtt upphaf liður er array staðsetningu 8. Það sem við höfum í raun gert er hunsað allt vinstra megin við 15. Við höfum eytt helmingi af vandamálinu, og nú, í stað þess að þurfa að leita yfir 15 þættir í fylking okkar, höfum við aðeins að leita á 7. Svo er 8 nýja upphafsstað. 14 er enn endapunkturinn. 

Og nú förum við yfir þetta aftur. Við reikna nýja miðpunkt. 8 plús 14 er 22, deilt með 2 er 11. Er þetta það sem við erum að leita að? Nei það er ekki. Við erum að leita fyrir gildi sem er minna en það sem við fundum bara. Þannig að við erum að fara að endurtaka ferlið aftur. Við erum að fara að breyta endastað til bara vinstra megin við miðpunkt. Svo nýja endapunkturinn verður 10. Og nú, það er bara hluti af array við verðum að raða í gegnum. Þannig að við höfum nú eytt 12 af 15 þáttum. Við vitum að ef 19 er í fylkinu, það þarf að liggja einhvers staðar á milli frumefni númer 8 og frumefni númer 10. 

Svo við reiknum nýja miðpunkt aftur. 8 plús 10 er 18, deilt með 2 er 9. Og í þessu tilfelli, líta, því miða er á miðjunni. Við fundum einmitt það sem við erum að leita að. Við getum hætt. Við lokið tvöfaldur leit. Allt í lagi. Þannig að við vitum þetta reiknirit virkar ef miðað er einhvers staðar inni í fylkinu. Er þetta reiknirit virka ef markmiðið er ekki í fylkinu? Jæja, við skulum byrja það aftur, og að þessu sinni, við skulum líta á frumefni 16, sem sjónrænt við getum séð er ekki til staðar í fylkinu. 

Upphaf málsins er aftur 0. The endir benda er aftur 14. Þeir eru vísitala fyrst og Síðustu þættir heill fylkisins. Og við munum fara í gegnum ferlið við bara fór í gegnum aftur, reyna að finna 16, jafnvel þó sjónrænt, getum við nú þegar segja að það er ekki að fara að vera þar. Við viljum bara að ganga úr skugga um þetta reiknirit mun í raun enn að vinna á einhvern hátt og ekki bara láta okkur fastur í óendanlega lykkju. 

Svo er það skref fyrst? Reikna miðpunkt af núverandi array. Hvað er miðpunktur núverandi array? Jæja, það er 7, ekki satt? 14 plús 0 deilt með 2 er 7. Er 15 það sem við erum að leita að? Nei Það er mjög nálægt, en við erum að leita fyrir gildi örlítið stærri en það. 

Þannig að við vitum að það er að fara að hvergi vinstra megin við 15. Útkoman er meiri en hvað er í miðju. Og svo við setjum nýja upphafsstað til vera rétt hægra megin við miðju. Miðpunkt er nú 7, svo skulum segja að nýtt upphaf liður er 8. Og það sem við höfum í raun gert aftur er hunsaður allt vinstri helminginn af fylkisins. 

Nú endurtaka við að vinna einu sinni. Reikna nýja miðpunkt. 8 plús 14 er 22, deilt með 2 er 11. Er 23 það sem við erum að leita að? Því miður, engin. Við erum að leita fyrir gildi sem er minna en 23. Og svo í þessu tilfelli erum við að fara að breyta endastað að vera bara vinstra megin við núverandi miðpunkt. Núverandi miðpunkt er 11, og þannig að við munum setja nýja endastað fyrir næsta skipti sem við förum í gegnum þetta ferli til 10. 

Aftur, við förum í gegnum ferlið aftur. Reikna miðpunkt. 8 plús 10 deilt með 2 er 9. Er 19 það sem við erum að leita að? Því miður, engin. Við erum enn að leita að a tala minna en það. Þannig að við munum breyta endastað þetta sinn að vera bara vinstra megin við miðpunkt. Miðpunkt er nú 9, svo endapunkturinn verður 8. Og nú, við erum bara að leita á einni þáttur array. 

Hvað er miðpunktur þessa array? Jæja, það byrjar á 8, það endar á 8, miðpunkt er 8. Er það það sem við erum að leita að? Erum við að leita að 17? Nei, við erum að leita fyrir 16. Þannig að ef það er til staðar í fylkinu, það verður að vera til staðar vinstra megin við þar sem við erum nú. Svo hvað erum við að fara að gera? Jæja, munum við að ákvarða endastað að vera bara vinstra megin við núverandi miðpunkt. Þannig að við munum breyta endastað til 7. Sérðu hvað bara gerðist hér, þó? Horfðu upp hér núna. 

Start er nú meiri en í lok. Á áhrifaríkan hátt, tveir endar af array okkar hafa yfir, og upphafsstað er nú eftir endapunktur. Jæja, það er ekki gera allir skilningarvit, ekki satt? Svo nú, hvað við getum sagt er að við hafa undir fjölbreytta stærð 0. Og þegar við erum farinn að þetta lið, getum við nú tryggja að sá hluti 16 er ekki til í fylkinu, vegna þess að byrjun og endir benda hafa yfir. Og svo er það ekki þar. Nú, eftir að þetta er örlítið öðruvísi en upphafsstað og enda benda að vera sama. Ef við hefðum verið að leita í 17, það myndi hafa verið í fylkinu, og byrjun og endir benda á að á síðasta endurtekning áður en þeir stig yfir, við hefðum fundið 17 þar. Það er aðeins þegar þeir fara yfir það sem við getum tryggja að þátturinn er ekki eru í fylkinu. 

Svo skulum taka a einhver fjöldi færri skref en línuleg leit. Í versta falli, við höfðum að skipta upp lista yfir n þætti ítrekað í tvennt til að finna miða, annaðhvort vegna þess að miða þáttur mun vera einhvers staðar í síðasta deild, eða það er ekki til á öllum. Svo í versta tilfelli, verðum við að skipt upp í array-- veistu? Log n sinnum, við þurfa að skera vandamál í hálfan ákveðinn fjölda skipta. Sem fjöldi skipta er log n. 

Hvað er besta falli? Jæja, fyrsta skipti sem við reikna miðpunkt, finnum það sem við erum að leita að. Í öllum fyrri dæmi um tvöfaldur leit við höfum bara farið yfir, ef við hefðum verið að leita að frumefni 15, við hefðum komist að strax. Það var í upphafi. Það var miðpunktur fyrsta tilraun á hættu af deild í tvöfaldur leit. 

Og svo í versta ræða, tvöfaldur leita keyrir í log n, sem er talsvert betri en línuleg leit, í versta tilfelli. Í besta tilfelli, tvöfaldur Leita keyrir omega af 1. Svo er tvöfaldur leita mikið betri en línuleg leit, en þú verður að takast á við ferli flokkun array fyrst áður en þú getur áhrif á afl tvöfaldur leit. 

Ég er Doug Lloyd. Þetta er CS 50.