Bináris keresés

Rendezett halmazban a bináris keresés hatékony algoritmus arra, hogy egy adott elemet megtaláljunk. Úgy működik, hogy ismételten megfelezi azt a tartományt, ahol a keresett elem előfordulhat, mindaddig, amíg a lehetséges pozíciók száma le nem csökken egyre. Bináris keresést használtunk a kitalálós játék fejezetben a bevezetőben.

A leggyakrabban akkor használnak bináris keresést, ha egy tömbben kell egy elemet megtalálni. Például a Tycho-2 csillagkatalógus tartja nyilván galaxisunk 2 539 913 legfényesebb csillagának adatait. Tegyük fel, hogy a csillag neve alapján meg szeretnéd találni a katalógusban egy adott csillag adatait. Ha a program az első bejegyzéstől kezdve sorban végignézi a katalógusban szereplő összes csillagot a lineáris keresés nevű algoritmus szerint, akkor a legrosszabb esetben 2 539 913 csillagot kell megvizsgálnia, mire rábukkan a keresett csillagra. Ha a katalógus a csillagokat név szerint rendezve tárolja, akkor bináris keresést alkalmazva még a legrosszabb esetben is maximum 22 csillagot kell megvizsgálni.

A következő néhány fejezetben alaposan megtárgyaljuk az algoritmust, megbeszéljük, hogyan lehet a JavaScriptbe beültetni, és hogyan kell az algoritmus hatékonyságát elemezni.

Amikor valaki másnak akarunk egy algoritmust megmagyarázni, akkor általában egy hozzávetőleges magyarázat is megteszi. Egy sütemény receptjéből kimaradhatnak egyes részletek; a receptíró feltételezi, hogy tudod, hogyan kell kinyitni a hűtőt, hogy kivedd a tojást, és azt is tudod, hogyan kell a tojást feltörni. Az emberek többsége tudja, hogyan töltse ki a hiányzó részleteket, de a számítógépes programok erre nem képesek. Ezért a számítógépes algoritmusokat minden részletre vonatkozóan le kell írni.

Ahhoz, hogy egy algoritmust programnyelvvel írj le, teljes részletességgel meg kell értened azt. Mik a bemenetek (az inputok)? Mik a kimenetek (az outputok)? Milyen változókat kell létrehozni, és azokhoz milyen kezdeti értéket kell rendelni? Milyen közbeeső lépésekre van szükség értékek kiszámításához, és mi kell a végső kimenet előállításához? Tartalmaznak ezek a lépések olyan ismétlődő utasításokat, amik leegyszerűsített formában megírhatók egy ciklusban?

Vizsgáljuk meg alaposan, hogyan lehetne leírni a bináris keresést! A bináris keresésnél alapvető fontosságú a szóbajöhető találgatások intervallumának folyamatos követése. Tegyük fel, hogy 1 és 100 közötti számra gondolok, mint a kitalálós játékban. Ha már tippeltél 25-öt, és azt válaszoltam, hogy a gondolt szám nagyobb, utána tippeltél 81-et, amire azt válaszoltam, hogy a gondolt szám kisebb, akkor csak a 26 és 80 közötti számok intervallumában észszerű tippelni. Az alábbi ábrán pirossal az észszerű, feketével pedig a már kiküszöbölt tippeket jelöltük:

Minden fordulóban úgy tippelsz, hogy a szóbajöhető tippeket két, nagyjából egyenlő halmazra bontod. Ha nem találtad el a gondolt számot, akkor megmondom neked, hogy a tipped túl magas, vagy túl alacsony, és így körülbelül ki tudod küszöbölni a szóbajöhető tippek felét. Például ha a pillanatnyi szóbajöhető tippek tartománya 26-tól 80-ig tart, akkor a középső pontot tippelnéd, $(26 + 80) / 2$left parenthesis, 26, plus, 80, right parenthesis, slash, 2, azaz 53-at. Ha ezután azt mondom, hogy 53 túl magas, akkor kizárhatod az 53 és 80 közötti összes számot, így az új intervallum 26-tól 52-ig terjed, amivel az intervallum a felére csökken.

A találgatós játék esetében a szóbajöhető tippeket néhány változóval nyomon követhetjük. Legyen a $min$m, i, n változó a szóbajöhető tippek pillanatnyi tartományának alsó határa, és legyen a $max$m, a, x változó a jelenlegi legnagyobb szóbajöhető tipp értéke. A feladat bemenete $n$n, ami a partnered által gondolható szám maximuma. Feltételezzük, hogy a legalacsonyabb szám egy, de könnyű úgy módosítani az algoritmust, hogy a legalacsonyabb szám egy második bemenet legyen.

Íme a találgatós játék lépésenkénti leírása a bináris keresés alkalmazásával:

Ezt a leírást tovább pontosítjuk úgy, hogy világosan meghatározzuk az algoritmus bemeneteit és kimeneteit, és megadjuk, hogy mit értünk az alatt, hogy „tippelj”, meg „állj le”. De egyelőre ennyi elég lesz.

A következőkben megnézzük, hogyan alkalmazhatjuk a bináris keresést egy tömbön, majd megbeszéljük, hogyan alakíthatjuk át a leírást programmá.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tantervfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.