>> [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.