>> [Zenelejátszási]
>> DOUG LLOYD: Rendben.
Tehát bináris keresés egy algoritmust tudjuk használni
találni egy elem belsejében egy tömbben.
Ellentétben a lineáris keresési van szükség, mert különleges feltételt kell teljesíteni előre,
de ez annyira sokkal hatékonyabb, ha ez a feltétel, sőt, teljesülnek.
>> Tehát mi az ötlet?
ez Oszd meg és uralkodj.
Azt akarjuk, hogy csökkentsék a méretét A keresési terület felére minden alkalommal
annak érdekében, hogy megtalálják a célszámot.
Ez az, ahol ez a feltétel jön szóba, mégis.
Mi csak kihasználja az erejét kiküszöbölve a fele az elemek
Anélkül, hogy megvizsgálnák azokat, ha a tömb rendezve.
>> Ha ez egy komplett mix, Nem lehet csak a kezét
dobja a fele a elemek, mert nem tudjuk, hogy mi vagyunk elöntve.
De ha a tömb rendezve, tehetünk, hogy azért, mert
tudni, hogy minden a balra, ahol jelenleg is
kell lennie, alacsonyabb, mint a értéke vagyunk jelenleg.
És mindent az jobbra, hol vagyunk
nagyobbnak kell lennie, mint az az érték mi jelenleg keresi a.
>> Szóval mi a pszeudokódja lépések bináris keresés?
Mi ismételje meg ezt a folyamatot, amíg a tömb vagy, ahogy haladunk keresztül,
sub tömbök, kisebb darabok Az eredeti tömb, a 0-ás méretű.
Számolja ki a középpont Az aktuális al tömb.
>> Ha az érték, amit keres abban a tömb elemének, hagyja abba.
Megtaláltad.
Az remek.
Ellenkező esetben, ha a cél az, kevesebb, mint mi a középső,
így ha az érték keresünk A kisebb, mint amit látunk,
ismételje meg ezt a folyamatot újra, de változtatni a végpont helyett
az, hogy az eredeti befejezni a teljes tömb,
hogy csak a bal A ahol csak nézett.
>> Tudtuk, hogy a középső túl magas volt, vagy a cél volt, kisebb, mint a középső,
és így is léteznie kell, ha egyáltalán létezik a tömbben,
valahol a bal oldalon a középpont.
És így fogunk állítani a tömb helyen, csak a bal
A középpont az új végpontot.
Ezzel szemben, ha a cél az, nagyobb, mint mi a középső,
mi pontosan ugyanazt folyamat, de ehelyett
változtatni a kezdőpontot, hogy csak a jobb oldalon a középpont
mi csak kiszámítani.
És akkor kezdjük újra az eljárást.
>> Nézzük elképzelni, rendben?
Szóval van egy csomó folyik, és itt, de itt van egy tömbben a 15 elemet.
És mi lesz, hogy nyomon követhetőek sokkal több dolgot ebben az időben.
Tehát a lineáris keresés voltunk Csak törődve a cél.
De ezúttal szeretnénk törődnek hol vagyunk
kezdi meg, ahol álltunk keres,
és mi van a középpont A jelenlegi tömb.
Tehát itt vagyunk a bináris keresés.
Nem vagyunk elég sok jó menni, igaz?
Csak megyek letenni Az alábbi Itt egy sor mutatót.
Ez alapvetően csak mi elem A tömb beszélünk.
A lineáris keresés, akkor érdekel, mivel azt
tudnia kell, hogy hány elemek mi az iterációt,
de valójában nem érdekel, mit eleme, hogy jelenleg további nézi.
A bináris keresés, amit csinálunk.
És így ezek csak ott, mint egy kis útmutató.
>> Így tudjuk kezdeni, ugye?
Nos, nem egészen.
Emlékszel, mit mondtam a bináris keresés?
Nem tehetjük meg egy szétválogatás nélkül tömb vagy más,
mi nem garantálja, hogy a Bizonyos elemek vagy értékek nem
véletlen dobni, amikor már csak
úgy dönt, hogy figyelmen kívül hagyja a fele a tömbben.
>> Szóval lépés egy bináris keresés ez kell egy rendezett tömbben.
És akkor használja a válogatás algoritmusok beszéltünk
rávenni, hogy ezt az álláspontot.
Tehát most vagyunk abban a helyzetben, ahol tudjuk elvégezni bináris keresés.
>> Úgyhogy ismételje meg a folyamatot lépésről lépésre, és tartsa
követni, hogy mi történik, ahogy haladunk.
Tehát az első meg kell tennie, hogy számítani a középpontját a jelenlegi tömb.
Nos, azt fogjuk mondani vagyunk, először is Az összes, keresi az értéket 19.
Megpróbáljuk megtalálni a 19-es szám.
Az első elem az e tömb található index nulla,
és az utolsó eleme ennek tömb található index 14.
És így hívjuk azokat a kezdete és vége.
>> Tehát kiszámítja a középpont által hozzátéve 0 plusz 14 osztva 2;
elég egyértelmű középpontját.
És azt mondhatjuk, hogy A középpont most 7.
Tehát 15 amit keresett?
Nem ez nem.
Keresünk 19.
De tudjuk, hogy 19 nagyobb mint amit találtunk a közepén.
>> Tehát mit tehetünk, megváltoztatni a kezdőpont
hogy csak a jobb oldalon a középpontját, és ismételjük meg a folyamatot újra.
És ha ezt tesszük, akkor most azt mondják, a új kiindulási pont tömb helyen 8.
Arra jöttünk hatékonyan tenni, figyelmen kívül mindent balra 15.
Végre megszabadultunk a fele A probléma, és most,
ahelyett, hogy keresni Több mint 15 elem a tömbben,
csak azt kell keresni több mint 7.
Tehát 8 új kiindulási pontot.
14 még mindig a végpontot.
>> És most át megint.
Kiszámítjuk az új középpontját.
8 plusz 14 22, osztva 2-11.
Ez az, amit keresünk?
Nem ez nem.
Keresünk egy értéket, ami kevesebb, mint amit most találtam.
Mi is így fogjuk megismételni A folyamat újra.
Fogunk változtatni a végpont lehet csak a bal oldalon a középpont.
Így az új végpont lesz 10.
És most, hogy ez az egyetlen része A tömb van kereshetőség.
Tehát most már megszűnt 12 a 15 elemekkel.
Tudjuk, hogy ha 19 létezik a tömbbel,
léteznie kell valahol elem száma 8 és elemszám 10.
>> Tehát számítani az új középpontját újra.
8 plusz 10 18, osztva 2-9.
És ebben az esetben, nézd, a cél a közepén.
Találtunk pontosan mit is keresünk.
Meg tudjuk állítani.
Sikeresen befejeződött bináris kereső.
Minden rendben.
Tehát tudjuk, hogy ez az algoritmus akkor működik, ha a cél
valahol a tömb.
Vajon ez az algoritmus munkát, ha a cél nem a tömbben?
Nos, kezdjük meg újra, és ebben az időben,
nézzük meg az elem 16, amely vizuálisan láthatjuk
nem létezik sehol a tömbben.
>> A kiindulási pont újra 0.
A végpontot újra 14.
Ezek az indexek az első és utolsó elemei a teljes tömb.
És akkor megy át a folyamat már csak ment át újra, hogy kitalálja 16,
még ha vizuálisan, akkor már mondd, hogy ez nem lesz ott.
Csak azt akarjuk, hogy győződjön meg arról, ez az algoritmus majd, sőt, még mindig működik valamilyen módon
és nem csak hagyja nekünk beragadt egy végtelen ciklusban.
>> Szóval mi a lépést az első?
Számolja ki a középpont A jelenlegi tömb.
Mi a középpontját A jelenlegi tömb?
Nos, ez 7, ugye?
14 plusz 0 osztva 2 7.
15 amit keresett?
Nem.
Ez elég közel, de keressük értéknél valamivel nagyobb annál.
>> Tehát tudjuk, hogy ez meg fog hová balra 15.
A cél nagyobb, mint mi van a középpont.
És így meg az új kiindulási pont, hogy lehet csak a jobb oldalon a középső.
A felezőpontja jelenleg 7, így mondjuk az új kezdőpont 8.
És mi már hatékonyan én ismét figyelmen kívül hagyja
a teljes bal fele a tömbben.
>> Most ismételje meg a feldolgozására még egyszer.
Számolja az új középpontját.
8 plusz 14 22, osztva 2-11.
23 amit keresett?
Sajnos nincs.
Keresünk egy értéket amely kevesebb, mint 23.
És így ebben az esetben, megyünk változtatni a végpont, hogy csak
hogy a bal oldalon a jelenlegi felezőpontja.
A jelenlegi középpontját 11 és így fogunk állítani az új végpont
A következő alkalommal megyünk ezen a folyamaton keresztül a 10.
>> Ismét végig a folyamatot újra.
Számolja ki a középpont.
8 plusz 10 osztva 2 9.
19 amit keresett?
Sajnos nincs.
Még mindig keresi Számos kisebb.
Így fogunk változtatni a végpontja ezúttal hogy csak a bal oldalon a középpont.
A középpont jelenleg 9, így a végpont lesz 8.
És most, átnézünk egyetlen elem tömb.
>> Mi a középpontját ez a tömb?
Nos, indul 8, akkor végződik 8, a középpont 8.
Ez az, amit keresünk?
Keresünk 17?
Nem, keresünk 16.
Tehát ha létezik a tömbben, léteznie kell valahol
balra, ahol jelenleg is.
Szóval mit fogunk csinálni?
Hát, majd adja meg a végpontot, hogy csak hogy a bal oldalon a jelenlegi felezőpontja.
Így fogunk változtatni a végpontja a 7.
Látod, amit csak történt itt, igaz?
Nézz fel itt.
>> Indítás most nagyobb, mint végéig.
Hatékonyan, a két végét a mi tömb átlépték,
és a kiindulási pont Most, miután a végpont.
Nos, ez nem semmi értelme, igaz?
Tehát most, hogy mit tudunk mondani, mi van egy al tömb mérete 0.
És ha egyszer mi ütött Ezen a ponton, mi most
Garantáljuk, hogy 16 elem nem létezik a tömbben,
mert a kezdőpont és végpontja keresztezték.
És így már nincs ott.
Most vegyük észre, hogy ez valamivel más, mint a kiindulási pont és vége
a pont jelentése azonos.
Ha már keres 17, ez volna
volt a tömbben, és a kezdőpont és végpontja, hogy az utolsó iterációs
mielőtt azokat a pontokat keresztbe, azt találta volna 17 van.
Csak amikor átkelnek, hogy mi lehet Garantáljuk, hogy az elem nem
létezzen a tömbben.
>> Szóval vessünk egy csomó kevesebb lépések, mint a lineáris keresést.
A legrosszabb forgatókönyv esetén, mi volt szétbontani egy listát az n elem
többször félbe, hogy megtalálja a cél, vagy azért, mert a cél elem
lesz valahol az utolsó osztály vagy nem is létezik egyáltalán.
Tehát a legrosszabb esetben, meg kell osszuk el a array-- tudod?
Bejelentkezés n-szer; mi kell vágni a problémát
fél egy bizonyos számú alkalommal.
Hogy több alkalommal is log n.
>> Mi a legjobb esetben?
Nos, az első alkalom, kiszámítja a középpont,
megtaláljuk, amit keresünk.
Az összes előző példák a bináris keresés
most már csak ment át, ha volna óta keresi a 15 elem,
azt találta volna, hogy azonnal.
Ez volt a kezdet kezdetén.
Ez volt a középpontban, Az első kísérlet egy osztott
A szétválás bináris keresés.
>> És így a legrosszabb esetben bináris keresés fut
a log n, ami lényegesen jobb, mint a lineáris keresés, a legrosszabb esetben.
A legjobb esetben, bináris keresés fut omegája 1.
Tehát bináris keresés is sok jobb, mint a lineáris keresés,
de meg kell foglalkozni a folyamat válogatás a tömb első, mielőtt
kihasználja az erejét bináris keresés.
>> Én Doug Lloyd.
Ez CS 50.