>> [Glazbom]
>> Doug LLOYD: U redu.
Dakle, binarna traži je algoritam možemo koristiti
pronaći element unutar niza.
Za razliku od linearnog potrazi, to zahtijeva poseban uvjet biti ispunjen prije,
ali to je tako mnogo učinkovitiji ako taj uvjet je, u stvari, susreo.
>> Dakle, ono što je ideja ovog mjesta?
to podijeli pa vladaj.
Želimo smanjiti veličinu potraga područje od pola svaki put
kako bi se pronašli ciljani broj.
Ovo je mjesto gdje se taj uvjet dolazi u igru, iako.
Možemo samo utjecati na snagu eliminira polovice elemenata
čak i bez gledanja na ih, ako je niz sortira.
>> Ako je kompletna mješavina gore, Ne možemo samo iz ruke
odbaciti polovina elemenata, jer ne znamo što ćemo odbacivanje.
No, ako je niz sortira, možemo to učiniti, jer mi
znam da je sve do ostavi gdje smo trenutno
mora biti manji od Vrijednost smo trenutno.
I sve do Pravo gdje smo
mora biti veći od vrijednosti trenutno gledamo u.
>> Zato što je pseudokod koraci za binarnog pretraživanja?
Mi ponovite ovaj postupak dok polje ili, kao što smo nastavili kroz,
sub polja, manjih komada izvorni niz, od veličine 0.
Izračunajte polovište tekuće sub polja.
>> Ako je vrijednost koju tražite u tom elementu niza, zaustaviti.
Pronašao si.
To je odlično.
Inače, ako je ciljani manje od onoga što je u sredini,
pa ako vrijednost tražimo je niži od onoga što smo vidjeli,
ponovite ovaj postupak opet, ali promijeniti završne točke, umjesto
da su izvorni dovršiti cijeli niz,
da se samo na lijevo gdje smo samo pogledao.
>> Znali smo da je srednji bila previsoka, ili je meta bio manji od sredine,
pa mora postojati, ako je to uopće postoji u nizu,
negdje lijevo od sredine.
I tako ćemo postaviti niz Položaj samo na lijevo
od sredine kao novi krajnje točke.
Suprotno tome, ako je ciljani veća nego što je u sredini,
mi je isti proces, ali umjesto toga smo
promijenite početnu točku se samo desno od sredine
mi samo izračunati.
A onda, ponovno smo započeli proces.
>> Idemo vizualizirati to, u redu?
Dakle, postoji mnogo događa i ovdje, ali ovdje je niz od 15 elemenata.
I mi ćemo biti praćenja od puno više stvari ovaj put.
Tako je u linearno pretraživanje, bili smo Samo brige o cilju.
No, ovaj put želimo stalo gdje smo
počinje izgledati, gdje se zaustavljamo u potrazi,
i što je srednji tekuće polja.
Dakle, ovdje mi ići s binarnim pretraživanja.
Mi smo prilično mnogo dobar to ići, zar ne?
Samo ću staviti dolje ispod ovdje skup indeksa.
To je u osnovi samo ono što je element od niza govorimo o tome.
S linearno pretraživanje, mi briga, budući da mi
trebaju znati koliko Elementi smo Ponavljanje iznad,
ali mi zapravo ne zanima me što Element se trenutno gleda.
U binarnom pretraživanje, činimo.
I tako oni su samo postoji kao mali vodič.
>> Tako možemo početi, zar ne?
Pa, ne baš.
Sjeti se što sam rekao o binarnom pretraživanje?
Ne možemo to učiniti na nesortirani niz inače,
mi ne jamči da je određeni elementi ili vrijednosti nisu
nehotično odbačena kada smo jednostavno
odlučili ignorirati polovice polja.
>> Tako jedan korak s binarnim pretraživanje je morate imati sortiran niz.
A možete koristiti bilo koji od sortiranjem Algoritmi Razgovarali smo o
da bi vas na to mjesto.
Tako sada, mi smo u poziciji gdje možemo izvesti binarni pretragu.
>> Tako ćemo ponoviti postupak korak po korak i držati
pratiti što se događa, kao idemo.
Dakle, prvo što trebate učiniti je izračunati polovište trenutnog polja.
Pa, mi ćemo reći da smo, prije svega, u potrazi za vrijednost 19.
Pokušavamo naći broj 19.
Prvi element ove Niz se nalazi na indeks nula,
i posljednji element ovog Niz se nalazi na indeks 14.
I tako ćemo nazvati one početak i kraj.
>> Tako smo izračunati polovište po dodajući 0 plus 14 podijeljeno s 2;
prilično jednostavan srednji.
I možemo reći da je sredina je sada 7.
Tako je 15 ono što tražite?
Ne, nije.
Tražimo 19.
Ali mi znamo da je 19 veći od onoga što smo pronašli u sredini.
>> Dakle, ono što možemo učiniti je promijeniti početnu točku
da se samo s desne strane srednji, i opet ponovite postupak.
A kad smo to, mi sada reći Novi početak točka je niz lokacija 8.
Ono što smo učinili je uspješno smo ignorirao je sve na lijevoj strani 15.
Mi smo eliminirani pola problema, a sada,
umjesto da se traži više od 15 elemenata u našoj polja,
imamo samo tražiti više od 7.
Dakle 8 je nova polazna točka.
14 je i dalje krajnje točke.
>> A sada, idemo preko toga opet.
Mi izračunati novu središnju točku.
8 plus 14 je 22, podijeljen 2 11.
Je li to ono što tražite?
Ne, nije.
Mi smo u potrazi za vrijednost koja je manje od onoga što smo upravo otkrili.
Tako ćemo ponoviti opet proces.
Idemo promijeniti završne točke do biti samo na lijevo od sredine.
Tako je nova završna točka postaje 10.
A sada, to je jedini dio Niz moramo sortirati kroz.
Dakle, sada smo eliminirani 12 od 15 elemenata.
Znamo da ako 19 postoji u nizu, to
mora postojati negdje između elementa broj 8 i broj 10 elementa.
>> Tako smo ponovno izračunati novu središnju točku.
8 plus 10 je 18, podijeljen 2 9.
I u ovom slučaju, izgledaju, Cilj je na sredini.
Pronašli smo upravo ono što smo tražili.
Možemo zaustaviti.
Uspješno završeno binarni pretraživanja.
U redu.
Tako znamo ovaj algoritam radi ako je meta
negdje unutar polja.
Je li ovaj algoritam raditi ako meta nije u nizu?
Pa, neka je to početak opet, i ovaj put,
pogledajmo za element 16, koji se vizualno možemo vidjeti
ne postoji nigdje u nizu.
>> Početna točka je opet 0.
Krajnja točka je opet 14.
Oni su indeksi prvi i Posljednji elementi kompletnog niza.
A mi ćemo proći kroz proces samo smo opet išli putem, pokušava pronaći 16,
iako vizualno, već možemo reći da to neće biti tamo.
Mi samo želite biti sigurni da taj algoritam će, u stvari, i dalje raditi na neki način
a ne samo nas ostaviti zaglavi u beskonačnu petlju.
>> Dakle, što je korak prvi?
Izračunajte polovište tekuće polja.
Što je srednji trenutnog niza?
Pa, to je 7, zar ne?
14 plus 0 podijeljeno s 2 je 7.
Je li 15 ono što tražite?
Ne.
To je prilično blizu, ali mi smo u potrazi za vrijednosti nešto veće od toga.
>> Dakle, znamo da će to biti nigdje na lijevoj strani 15.
Cilj je veća od što je u središnjoj točki.
I tako smo postavili novu početnu točku biti samo na desnoj sredini.
Središnja točka je trenutno 7, tako recimo nova polazna točka je 8.
A ono što smo uspješno učinio ponovno se ignorira
cijela lijeva polovica polja.
>> Sada ćemo ponoviti proces još jednom.
Izračunajte novu središnju točku.
8 plus 14 je 22, podijeljen 2 11.
Je li 23 ono što tražite?
Nažalost ne.
Mi smo u potrazi za vrijednošću koji je manji od 23.
I tako, u ovom slučaju, idemo za promjenu završne točke da se samo
lijevo tekuće sredine.
Trenutni srednji je 11, a pa ćemo postaviti novu završnu točku
za sljedeći put idemo kroz ovaj proces do 10.
>> Opet ćemo proći kroz proces ponovno.
Izračunajte polovište.
8 plus 10 podijeljeno s 2 je 9.
Je li 19 ono što tražite?
Nažalost ne.
Još uvijek u potrazi za broj manje od toga.
Tako ćemo promijeniti završne točke ovog puta biti samo lijevo od sredine.
Središnja točka je trenutno 9, tako da je krajnja točka će biti 8.
I sada, mi samo tražimo na jedan element niza.
>> Što je srednji ovog niza?
Pa, ona počinje u 8, što završava u 8, sredina je 8.
Je li to ono što tražite?
Jesmo li u potrazi za 17?
Ne, mi smo u potrazi za 16 godina.
Dakle, ako postoji u nizu, mora postojati negdje
s lijeve strane, gdje smo trenutno.
Pa što ćemo učiniti?
Pa, mi ćemo postaviti završne točke da se samo lijevo tekuće sredine.
Tako ćemo mijenjati završne točke do 7.
Vidite li što se upravo dogodilo ovdje, iako?
Potražite ovdje.
>> Početak je sada veći od kraja.
Efektivno, dva kraja našeg polja su prešli,
a početna točka je Sada nakon krajnje točke.
Pa, da ne nikakvog smisla, zar ne?
Tako sada, što možemo reći je da imaju pod niz veličina 0.
I jednom smo dobivši ovom trenutku, sada možemo
jamčiti da element 16 ne postoji u nizu,
jer početne točke i krajnje točke su prešli.
I tako to ne postoji.
Sada primijetite da je to nešto razlikuje od početne točke i na kraju
ukazati se isto.
Ako smo bili u potrazi za 17, to bi
je u nizu, a početne točke i završna točka tog zadnjeg iteracije
Prije te točke prešli, bismo našli 17 tamo.
To je samo kad oni prelaze da možemo jamčiti da se element ne
postoje u nizu.
>> Tako ćemo se puno manje koraka od linearnog pretraživanje.
U najgorem slučaju, imali smo podijeliti popis n elemenata
više puta na pola kako bi pronašli metu, bilo zato što je ciljani element koji
će biti negdje u posljednja podjela, ili to ne postoji.
Dakle, u najgorem slučaju, moramo razišli su array-- znaš?
Prijava od n puta; mi morati smanjiti problem
pola određeni broj puta.
Taj broj puta je log n.
>> Koji je najbolji mogući scenarij?
Pa, prvi put smo izračunati polovište,
možemo pronaći ono što tražite.
U sva prethodna primjeri na binarnom pretraživanje
smo samo otišli preko, ako smo imali u potrazi za element 15,
bismo otkrili da je odmah.
To je na samom početku.
To je polovište prvi pokušaj u Splitu
od podjele u binarnom pretraživanja.
>> I tako je u najgore slučaj, binarno traženje traje
u log N, koji je znatno bolja nego linearno pretraživanje, u najgorem slučaju.
U najboljem slučaju, binarni traži radi omega od 1.
Dakle, binarna traži puno bolji od linearnog pretraživanje,
ali morate se nositi s procesom sortiranje svoj niz prije nego što možete
iskoristiti snagu binarnog pretraživanja.
>> Ja sam Doug Lloyd.
To je CS 50.