>> [Muusika mängib]
>> DOUG LLOYD: Okei.
Nii Kahendotsingupuu on algoritmi saame kasutada
leida elemendi sees massiivi.
Erinevalt lineaarne otsing, see nõuab eritingimuse olema täidetud enne,
aga see on nii palju tõhusam, kui see tingimus on tegelikult täidetud.
>> Mis siis mõte siin?
see on jaga ja valitse.
Me tahame vähendada suurus otsingu ala poole võrra iga kord,
et leida sihtmärk number.
See on koht, kus see tingimus tuleb mängu, kuigi.
Me võime ainult võimendavat võimu kaotades pool elemendid
isegi ilma vaadates neid, kui massiiv on järjestatud.
>> Kui see on täielik mix up, Me ei saa lihtsalt käest
visake poole elemente, sest Me ei tea, mida me sellest vabaneda.
Aga kui massiiv on järjestatud, saame teha, sest me
tean, et kõik on vasakule, kus me praegu oleme
peab olema väiksem kui väärtus oleme praegu.
Ja kõik, et õigust, kus me oleme
peab olema suurem kui väärtus me praegu vaadates.
>> Mis siis pseudokoodi sammud Kahendotsingupuu?
Me kordame seda protsessi, kuni massiiv või kui astume läbi,
sub massiivid, väiksemateks tükkideks originaal massiivi, on suurus 0.
Arvuta keskpunktis Praeguse alamjärjestuse.
>> Kui väärtus, mida otsid, on et massiivi element, peatus.
Sa leidsid.
See on suurepärane.
Vastasel juhul, kui eesmärgiks on vähem, kui on keskel,
nii et kui väärtus ootame on madalam kui see, mida me näeme,
Seda protsessi korratakse taas, kuid muuta lõpp-punkti, vaid
olemise originaal täitma täies massiiv,
olla lihtsalt vasakule kus me lihtsalt vaatasin.
>> Me teadsime, et keset oli liiga kõrge, või siht oli alla keskmise,
ja nii see peab eksisteerima kui see üldse eksisteerib massiiv,
kusagil vasakul keskpunktis.
Ja nii me määrata massiivi Vaid vasakule
keskpunkti uueks lõpp-punkti.
Vastupidisel juhul, kui eesmärgiks on suurem kui see, mida on keskel,
meil täpselt sama Meetod, kuid selle asemel me
muuta alguspunkt olla lihtsalt paremal keskpunktis
me lihtsalt arvutada.
Ja siis me protsessi uuesti alustama.
>> Teeme seda visualiseerida, OK?
Nii et palju läheb ja siin, kuid siin hulgaliselt 15 elementi.
Ja me ei kavatse olla kursis hoida on palju rohkem asju seekord.
Nii lineaarne otsing olime lihtsalt hooliv sihtmärk.
Aga seekord me tahame hoolivad, kus me oleme
hakkame vaatama, kus me lõpetamist vaadates,
ja mis on keskpunktis Praeguse massiivi.
Nii et siin me läheme Kahendotsingupuu.
Oleme päris palju hea minna, eks?
Ma lihtsalt panema Alljärgnevalt kogum näitajaid.
See on põhimõtteliselt just see element massiivi me räägime.
Mis lineaarne otsing me huvita, sest me
vaja teada, kui palju elementide me iterating üle,
aga me tegelikult ei huvita, mida element me praegu vaadates.
In Kahendotsingupuu, mida me teeme.
Ja nii need on vaid seal nagu väike juhend.
>> Nii saame alustada, eks?
Noh, mitte päris.
Pea meeles, mida ma ütlesin umbes Kahendotsingupuu?
Me ei saa seda teha kohta sorteerimata massiivi või muud,
me ei taga, et teatud elemente või väärtused ei ole
Juhuslike visata, kui me lihtsalt
otsustab ignoreerida pool massiivi.
>> Nii samm üks binaarne otsing on sul peab olema järjestatud hulga.
Ja mida saab kasutada ükskõik millise sorteerimine algoritme me rääkisime
sulle seda seisukohta.
Nüüd, oleme olukorras, kus saame täita Kahendotsingupuu.
>> Nii saab protsessi korrata Samm-sammult ja hoida
jälgida, mis toimub nagu me minna.
Nii et esimese peame tegema, on arvutada keskpunktis praeguse massiivi.
Noh, ütleme me, esimene kõik, kes otsivad väärtus 19.
Me püüame leida number 19.
Esimene element käesoleva massiiv asub index null,
ja viimane osa sellest massiiv asub indeks 14.
Ja nii me kutsume neid alguse ja lõpu.
>> Nii me arvutada keskpunktis poolt Lisades 0 pluss 14 jagatud 2;
üsna lihtne keskpunktis.
Ja me ei saa öelda, et keskpunktis on nüüd 7.
Nii on 15, mida me otsime?
Ei see ei ole.
Otsime 19.
Aga me teame, et 19 on suurem kui see, mida me leidsime keskel.
>> Mida me saame teha, on muuta alguspunkt
olema lihtsalt paremal keskpunktis, ja korrake protsessi uuesti.
Ja kui me seda teeme, oleme nüüd öelda uus alguspunkt on massiiv asukoha 8.
Mida me oleme tegelikult teinud on ignoreeritakse kõike vasakul 15.
Me oleme kõrvaldanud poole probleemi, ja nüüd,
selle asemel, et otsida Üle 15 elementi meie massiiv,
meil on ainult otsida üle 7.
Nii 8 on uus alguspunkt.
14 on ikka lõpp-punkti.
>> Ja nüüd, me läheme üle selle uuesti.
Me arvutame uue keskpunkti.
8 plus 14 on 22 jagatuna 2 on 11.
Kas see, mida me otsime?
Ei see ei ole.
Otsime väärtus, mis on vähem kui see, mida me lihtsalt leida.
Nii et me läheme kordama protsessi uuesti.
Me läheme muuta lõpp-punkt olla just vasakul keskpunktis.
Nii et uue lõpp-punkt muutub 10.
Ja nüüd, see on ainult osa massiivi meil sorteeri.
Nii oleme nüüd kõrvaldatud 12 15 elementi.
Me teame, et kui 19 olemas massiiv, siis
peab olemas olema kusagil element number 8 ja element number 10.
>> Nii me arvutada uue keskpunkti uuesti.
8 pluss 10 on 18 jagatuna 2 on 9.
Ja sel juhul, otsida, siis Eesmärgiks on keskel.
Leidsime täpselt, mida me otsime.
Me ei saa peatada.
Me edukalt binaarne otsing.
Hästi.
Nii et me teame, et see algoritm töötab kui eesmärgiks on
kusagil sees massiiv.
Kas see algoritm töö kui eesmärk ei ole massiivi?
Noh, alustame siis uuesti ja seekord
Vaatame elemendi 16, mis visuaalselt näeme
ei ole kuhugi massiivi.
>> Alguspunkt on jälle 0.
Lõpp-punkt on jälle 14.
Need on indeksid esimese ja viimase elementide täielik array.
Ja me minna läbi protsessi me lihtsalt läbis uuesti, püüdes leida 16
kuigi visuaalselt, saame juba öelda, et ta ei kavatse olla seal.
Me lihtsalt tahame veenduda selle algoritmi siis tegelikult töötavad endiselt mingil moel
ja ei jäta meile kinni lõputu silmuse.
>> Mis siis samm esimesena?
Arvuta keskpunktis Praeguse massiivi.
Mis keskpunktis Praeguse massiivi?
Noh, see on 7, eks?
14 plus 0 jagatuna 2 on 7.
Kas 15, mida me otsime?
Ei.
See on üsna lähedal, kuid ootame jaoks väärtus veidi suurem kui see.
>> Nii et me teame, et see läheb saab kuhugi vasakul 15.
Eesmärk on suurem kui Mis keskpunktis.
Ja nii me seame uue alguspunkti just paremal keskel.
Keskpunktis on praegu 7, nii et oletame uus alguspunkt on 8.
Ja me oleme tegelikult kordama ignoreeritakse
kogu vasak pool massiivi.
>> Nüüd, me kordame töödelda veel üks kord.
Arvutage uue keskpunkti.
8 plus 14 on 22 jagatuna 2 on 11.
Kas 23, mida me otsime?
Kahjuks mitte.
Otsime väärtus mis on väiksem kui 23.
Ja nii sel juhul, me ei kavatse muuta lõpp-punkt on lihtsalt
vasakul praeguse keskpunktis.
Praegune keskpunktis on 11, ja nii me seada uusi lõpp-punkti
järgmine kord läheme selle protsessi kaudu 10.
>> Jällegi, me minna läbi protsessi uuesti.
Arvuta keskpunktis.
8 pluss 10 jagatud 2 on 9.
Kas 19, mida me otsime?
Kahjuks mitte.
Me otsid veel number väiksem.
Nii muudame lõpp-punkti seekord olevat vaid vasakul keskpunktis.
Keskpunktis on praegu 9, nii lõpp-punkt on 8.
Ja nüüd, me lihtsalt otsin ühes element massiivi.
>> Mis keskpunktis seda valikut?
Noh, see algab kell 8, siis lõpeb kell 8, keskpunktis on 8.
Kas see, mida me otsime?
Kas me otsime 17?
Ei, me otsitavat 16.
Nii et kui see on olemas massiiv, see peab olemas olema kuskil
vasakul kus me praegu oleme.
Mida me siis teeme?
Noh, me määrata lõpp-punkt on lihtsalt vasakul praeguse keskpunktis.
Nii muudame lõpp-punkt 7.
Kas sa näed, mida lihtsalt siin juhtus, kuigi?
Vaata siin nüüd.
>> Start on nüüd suurem kui lõpus.
Tõhusalt on kaks otsa meie massiivi ületanud,
ja alguspunkt on nüüd pärast punkti.
Noh, et ei mingit mõtet, eks?
Nüüd, mida me ei saa öelda, me on sub massiivi suurus 0.
Ja kui me õppinud Sel hetkel, saame nüüd
tagada, et element 16 ei ole olemas massiiv,
sest alguspunkt ja lõpp-punkti ületanud.
Ja nii see ei ole.
Nüüd, märkate, et see on veidi teistsugune kui alguspunkt ja lõpp
juhtida on sama.
Kui me otsinud 17, see oleks
olnud massiivi ning alguspunkt ja lõpp-punkt, et viimase iteratsiooni
Enne neid punkte ületanud, meil oleks olnud 17 seal.
See on ainult siis, kui nad ületavad et suudame tagada, et andmeid ei ole
olemas massiiv.
>> Võtame palju vähem samme kui lineaarne otsing.
In halvimal juhul oli meil lahku nimekirja n elemendid
korduvalt pooleks leida sihtmärk, kas sellepärast, et siht element
kusagil viimase jagunemise või seda ei ole olemas üldse.
Nii et halvimal juhul tuleb meil lahku array-- sa tead?
Logi n korda; me on vähendada probleemi
pooleks teatud arv kordi.
See, mitu korda on log n.
>> Milline on parim stsenaarium?
Noh, esimene kord, kui me arvutada keskpunktis,
leiame, mida me otsime.
Kõikidel eelmise näiteid Kahendotsingupuu
oleme läinud üle, kui meil oleks otsinud element 15,
me leidsime, et kohe.
See oli alguses.
See oli keskpunktis esimene katse lõhestatud
Jaoskonnakomisjoni binaarne otsing.
>> Ja nii halvimal Juhul, Kahendotsingupuu jookseb
log n, mis on märksa paremini kui lineaarset otsingut, halvimal juhul.
Parimal juhul binaarne Otsing töötab omega 1.
Nii Kahendotsingupuu on palju parem kui lineaarne otsing,
aga sa pead tegelema protsessi sorteerimine oma rida, enne kui saab
võimendavat võimu Kahendotsingupuu.
>> Ma olen Doug Lloyd.
See on CS 50.