[Predvaja glasba] Doug LLOYD: V redu. Torej, binarno iskanje je Algoritem lahko uporabimo poiščite element znotraj matrike. Za razliko od linearnega iskanja, se zahteva Poseben pogoj je izpolnjen vnaprej, ampak to je tako veliko bolj učinkovito, če da je pogoj, dejansko izpolnjeni. Torej, kaj je ideja tukaj? to je deli in vladaj. Želimo zmanjšati velikost iskanje območje, ki ga pol vsak čas da bi imel ciljno številko. To je, če ta pogoj pride v poštev, čeprav. Mi lahko izkoristite samo moč odpravo polovica elementov celo brez gledaš jih, če je matrika razporejene. Če je popoln mix up, Ne moremo samo iz roke zavreči polovica elementov, ker ne vemo, kaj smo se zavrže. Ampak, če je matrika razporejene, bomo lahko to storili, ker smo vem, da je vse, kar je levo, kjer smo trenutno so sme biti nižja od Vrednost smo trenutno. In vse, kar je na Pravica do kje smo mora biti večja od vrednosti smo trenutno iščejo. Torej, kaj je psevdokoda koraki za binarnem iskanju? Mi ta postopek ponovite, dokler niz ali, kot smo nadaljevali skozi, sub nizi, manjših kosov prvotna matrika, je velikosti 0. Izračunamo srednjo vrednost trenutnega pod paleto. Če je vrednost, ki jo iščete, V tem elementu matrike, stop. Našli ste jo. To je super. V nasprotnem primeru, če je cilj manj od tistega, kar je na sredini, tako da, če vrednost iščeva za je nižja od tega, kar smo videli, Ta postopek ponovite, vendar spremeniti končno točko, namesto o čemer je prvotna dokončati celotno paleto, da je samo na levi kje smo pravkar pogledal. Vedeli smo, da je bil srednji previsoka, ali cilj je bil manjši od sredine, in zato mora obstajati, če to sploh obstaja v matriki, nekje na levi sredini. In tako bomo nastavili niz lokacija samo na levi od središčne točke kot novi končno točko. Nasprotno pa, če je cilj večji od tistega, kar je na sredini, počnemo popolnoma enaka Postopek, ampak smo spremenite začetno točko, da bo Samo na desni strani središčne smo samo izračunati. In potem smo spet začeti proces. Oglejmo vizualizirati to v redu? Torej je veliko dogaja in tukaj, ampak tu je niz 15 elementov. In bomo se sledenja za veliko več stvari tokrat. Torej, v linearno iskanje, smo bili samo skrbeti tarčo. Toda tokrat smo želeli briga kje smo začeli gledati, kje smo se ustavili v prihodnost, in kaj je sredina trenutnega niza. Torej gremo z binarno iskanje. Mi smo precej na dobri poti, kajne? Jaz sem le, da bo odložil Spodaj tukaj niz indeksov. To je v bistvu samo tisto element array smo govoriš. Z linearno iskanje, smo skrbi, saj mi morate vedeti, koliko Elementi smo ponavljanjem več, ampak pravzaprav ne zanima, kaj element smo trenutno iščejo. V binarnem iskanju, počnemo. In tako tistih, ki so samo tam malo vodilo. Tako bomo lahko začeli, kajne? No, ne povsem. Se spomniš, kaj sem rekel o binarnem iskanju? Ne moremo storiti opravljena na razvrščeni matrika ali pa, ne bomo zagotovili, da nekateri elementi ali vrednosti niso nenamerne zavržejo, ko smo tik odloči, da prezreti polovica array. Torej en korak z binarno iskanje je, da mora imeti sortira paleto. In jih lahko uporabite katero koli od razvrščanje algoritmi smo govorili da boste dobili na ta položaj. Torej sedaj, smo v položaju, kjer je bomo lahko opravljajo binarno iskanje. Torej, kaj je ponoviti postopek korak za korakom in vodi Spremljajte, kaj se dogaja, ko gremo. Torej najprej moramo storiti, je izračun razpolovišča tekočega matrike. No, bomo rekli, da smo v prvi vrsti vsem, ki iščejo v vrednosti 19. Poskušamo najti številko 19. Prvi element tega Niz se nahaja na indeksu ničlo, in zadnji element tega Niz se nahaja na indeks 14. In tako bomo pozivajo tiste, začetek in konec. Tako smo izračunali srednjo vrednost s dodajanje 0 plus 14 deljeno z 2; precej preprosta sredina. In lahko rečemo, da sredina je zdaj 7. Torej je 15, kar iščemo? Ne, ni. Iščemo 19. Vendar vemo, da je 19 več od tistega, kar smo našli na sredini. Torej, kaj lahko storimo, je, spremenite začetno točko da je samo na desni strani sredini in ponovite postopek. In ko bomo to storili, zdaj pravijo, da je nova izhodiščna točka je matrika lokacija 8. Kaj smo dejansko storili, je prezreti vse na levi strani 15. Mi smo odpraviti polovico problema, zdaj, namesto da bi iskanje več kot 15 elementov v naši matriki, imamo le iskati nad 7. Torej 8 je nov začetek, točka. 14 je še vedno končna točka. In zdaj, gremo čez to še enkrat. Smo izračunali novo srednjo vrednost. 8 plus 14 je 22, deljeno z 2, je 11. Je to tisto, kar iščemo? Ne, ni. Iščemo za vrednost, ki je manj od tistega, kar smo pravkar našel. Torej bomo ponovili spet proces. Bomo spremenili končno točko do ravno na levi sredini. Zato je novi končna točka postane 10. In zdaj, da je le del array moramo, da razvrstite skozi. Tako smo zdaj odpravljena 12 od 15 elementov. Vemo, da če 19 obstaja v matriki, jo mora obstajati nekje med elementom številka 8 in element številka 10. Torej smo spet izračunamo novo srednjo vrednost. 8 plus 10 je 18, deljeno z 2 je 9. In v tem primeru, poglej se Cilj je na sredini. Našli smo točno tisto, kar smo iskali. Mi lahko ustavi. Uspešno smo zaključili binarni iskanje. V redu. Torej vemo, ta algoritem deluje, če je cilj nekje znotraj polja. Ali to algoritem deluje, če ciljna ni v matriki? No, kaj je to začetek še enkrat, in tokrat, Oglejmo si za element 16, ki je vizualno lahko vidimo ne obstaja nikjer v matriki. Začetna točka je spet 0. Končna točka je spet 14. Tisti, ki so indeksi prvi in last elementi popolne nizu. In bomo šli skozi proces smo samo šla skozi še enkrat, poskuša najti 16, čeprav vizualno, lahko smo že povedal, da je ne bo tam. Pravkar smo želeli, da poskrbite, da ta algoritem bo v resnici še vedno deluje na nek način in nas ne pustite zaljubljen v neskončni zanki. Torej, kaj je prvi korak? Izračunamo srednjo vrednost trenutnega niza. Kaj je sredina trenutnega niz? No, to je 7, kajne? 14 plus 0 deljeno z 2 je 7. Je 15, kar iščemo? No. To je zelo blizu, ampak smo iskali za vrednost nekoliko večji od tega. Tako smo vedeli, da se dogaja, da nikjer na levi strani 15. Cilj je večja od kaj je v sredini. In tako smo postavili novo začetno točko ravno desno od sredine. Sredina je trenutno 7, tako da recimo nova izhodiščna točka je 8. In kaj smo dejansko imel spet naredil, je prezrta celotno levo polovico matrike. Zdaj smo ponovite obdelati še enkrat. Izračunaj novo srednjo vrednost. 8 plus 14 je 22, deljeno z 2, je 11. Je 23, kar iščemo? Žal ne. Iščemo za vrednost da je manj kot 23. In tako v tem primeru gremo za spremembo končno točko, da je ravno levo od trenutnega sredini. Sedanji razpolovišča je 11, in zato bomo določili novo končno točko za naslednjič, ko gremo skozi ta proces do 10. Spet gremo skozi proces znova. Izračunamo srednjo vrednost. 8 plus 10 deljeno z 2 je 9. Je 19, kar iščemo? Žal ne. Mi smo še vedno išče nekaj manj kot to. Torej bomo spremenili končne točke ta čas da je samo na levi sredini. Sredina je trenutno 9, tako da bo končna točka je 8. In sedaj, samo iščemo na enem elementu matrike. Kaj je sredina tega polja? No, to se začne pri 8, je konča na 8, sredina je 8. Je to tisto, kar iščemo? Iščemo za 17? Ne, iščemo 16. Torej, če obstaja v matriki, mora obstajati nekje na levi strani, kjer smo trenutno so. Torej, kaj bomo storili? No, bomo nastavite končno točko, da je ravno levo od trenutnega sredini. Torej bomo spremenili končno točko 7. Ali vidiš, kaj se je pravkar se je tu zgodilo, čeprav? Poglej tukaj. Start je sedaj večja kot konec. Učinkovito, dva konca naše matrike so prestopile, in izhodiščna točka je zdaj po končni točki. No, da ne nobenega smisla, kajne? Torej sedaj, kar lahko rečemo, je, da smo imajo sub paleto velikosti 0. In ko smo gotten ta točka, lahko sedaj smo jamčiti, da element 16 ne obstaja v matriki, ker začetno točko in končna točka sta prečkala. In zato je ni tam. Zdaj, opazili, da je to nekoliko drugačna kot začetno točko in na koncu točka sta enaka. Če smo bili videti za 17, bi to imelo že v matriki, in začetno točko in končna točka tega zadnjega ponovitvi preden prečka te točke, mi pa bi našel 17 tam. To je samo takrat, ko so prečkali, da smo lahko zagotavljajo, da je element ne obstajajo v matriki. Dajmo torej veliko manj korakov od linearnega iskanja. V najslabšem primeru, smo imeli razdeliti seznam n elementov Večkrat na pol, da bi našli cilja, bodisi zato, ker je ciljna element bo nekje v zadnji delitev, ali pa ne obstaja sploh. Torej, v najslabšem primeru pa moramo split up array-- veš? Log n-krat; smo morali zmanjšati problem pol določeno število ponovitev. Da kolikokrat je log n. Kaj je najboljši scenarij? No, prvič smo izračunati srednjo vrednost, smo ugotovili, kaj iščemo. V vseh prejšnja Primeri na binarnem iskanju smo pravkar šla čez, če bi imeli iskal elementa 15, smo ugotovili, da bi takoj. To je bilo na samem začetku. To je bil razpolovišča prvi poskus na razcepu o delitvi v binarnem iskanju. In tako v najslabšem primera, binarno iskanje teče v log n, kar je bistveno bolje kot linearno iskanje, v najslabšem primeru. V najboljšem primeru binarno Iskanje teče v omega 1. Torej, binarno iskanje je veliko bolje kot linearni iskanja, vendar boste morali spopasti s procesom sortiranje svojo paleto, preden lahko vplivale na moč binarnega iskanja. Sem Doug Lloyd. To je CS 50.