Ha ezt az üzenetet látod, az annak a jele, hogy külső anyagok nem töltődnek be hibátlanul a honlapunkra.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Fő tartalom

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.

A keresés leírása

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, 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 változó a szóbajöhető tippek pillanatnyi tartományának alsó határa, és legyen a max változó a jelenlegi legnagyobb szóbajöhető tipp értéke. A feladat bemenete 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:
  1. Legyen min=1 és max=n.
  2. Tippeld meg max és min átlagát, lefelé kerekítve, hogy egész számot kapj!
  3. Ha rájöttél a számra, állj le, kitaláltad!
  4. Ha a tipped túl alacsony, állítsd be min értékét a tippednél eggyel magasabb értékre.
  5. Ha a tipped túl magas, állítsd be max értékét a tippednél eggyel kisebb értékre.
  6. Folytasd a kettes lépéssel!
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.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.