Tömb bináris keresésének implementálása

Vizsgáljuk meg a bináris keresést rendezett tömbben! Mint tudjuk, a JavaScript (számos más programnyelvhez hasonlóan) rendelkezik már olyan metódusokkal, melyek segítségével megállapítható, hogy egy adott érték szerepel-e a tömbben, és ha igen, akkor az hol található. Ezt azonban most mi magunk akarjuk elkészíteni azért, hogy megértsük, hogyan kell egy ilyen metódust megírni. Ez itt az első 25 prímszámból álló rendezett tömb definíciója JavaScriptben:

Tegyük fel, hogy meg akarjuk állapítani, vajon 67 prímszám-e. Ha a 67 benne van a tömbben, akkor prímszám.

Még arra is kíváncsiak lehetünk, hány olyan prímszám van, ami kisebb, mint 67. Ha megtaláljuk a 67-es szám pozícióját a tömbben, akkor az alapján meg tudjuk határozni, hány ennél kisebb prímszám létezik.

Egy elem pozícióját a tömbben az elem indexének hívják. A tömb indexe 0-tól indul és felfelé növekszik. Ha egy elem indexe 0, akkor az a tömb első eleme. A 3. indexű elemet 3 elem előzi meg az egydimenziós tömbben.

Ha megnézzük az alábbi példát, akkor a prímszámokból álló tömböt balról jobbra egyenként olvasva eljuthatunk a 67-hez (a rózsaszín téglalapban) és leolvashatjuk, hogy az a 18. indexnél található. Ha így nézzük végig a számokat, akkor lineáris keresést végzünk.

Ha tudjuk, hogy 67 a 18. indexnél található, akkor azt is tudjuk, hogy az prímszám. Azt is megállapíthatjuk, hogy 18 elem előzi meg a 67-et a tömbben, ami azt jelenti, hogy 18 olyan prímszám van, amelyik kisebb, mint 67. (A feliratok: search - keresés; next - következő; play - lejátszás; reset - újraindítás)

Láttad, hány lépésre volt szükség? A bináris keresés hatékonyabb lenne. Mivel a primes tömb 25 számot tartalmaz, a tömb indextartománya 0-tól 24-ig terjed. Az előző fejezet lépésenkénti leírását felhasználva min = 0 és max = 24. A bináris keresés első tippje (angolul guess) ezért a 12-es indexű elem (ami (0 + 24) / 2). primes[12] megegyezik 67-tel? Nem, primes[12] értéke 41.

A keresett szám indexe kisebb, vagy nagyobb, mint 12? Mivel a vektor elemei növekvő sorrendben vannak, és 41 < 67, ezért 67 indexe 12-től jobbra lesz. Más szóval, a keresett indexnek 12-nél nagyobbnak kell lennie. Ezért a min értékét beállítjuk 12 + 1-re, azaz 13-ra, a max értékét változatlanul hagyjuk 24-en.

Mi lesz a következő tipp indexe? 13 és 24 átlaga 18,5, amit lefelé kerekítünk 18-ra, mivel a tömb indexének egész számnak kell lennie. Azt kapjuk, hogy primes[18] értéke 67.

A bináris keresési algoritmus itt megáll, mivel megtalálta a megoldást. Csak két találgatásra volt szükség a lineáris keresés 19 tippje helyett. Ha akarod, az alábbi ablakban megnézheted az algoritmus működését. (A feliratok: search - keresés; next - következő; play - lejátszás; reset - újraindítás)

Az előbb szavakkal leírtuk a bináris keresési eljárást, miközben lépésről lépésre végigmentünk egy példán. Ez is egy lehetséges módszer, de az emberi nyelven előadott magyarázat minősége változó lehet. Lehet túl rövid, vagy túl hosszú, de ami a legfontosabb, nem mindig kellően precíz. Akár folytathatnánk azzal is, hogy megmutatjuk a bináris keresés programkódját JavaScriptben vagy Pythonban, de a programok túl sok egyéb részletet tartalmaznak – a programozási nyelv által megkövetelt részleteket, vagy a program által kezelendő hibákat: rossz adatok, felhasználói hiba vagy rendszerhiba kezelését – ezek a részletek megnehezítik az algoritmus lényegének megértését, ha csak a kódot vizsgáljuk. Ezért tartjuk hasznosnak az algoritmusok leírásánál az úgynevezett pszeudokód alkalmazását, ami az emberi nyelvet a programozási nyelvek elemeivel keveri.

Alább látható a bináris keresés pszeudokódja, amit úgy módosítottunk, hogy a keresést egy tömbön hajtjuk végre. A bemenet a tömb, amit array-nek hívunk; az n egy szám, ami az array elemszámát jelöli; és target-tel jelöljük a keresett számot. A kimenet a target indexe az arrayben:

Az elkövetkezendőkben váltogatni fogjuk a szöveges leírást, a pszeudokódot és a JavaScriptet az adott helyzettől függően. Programozóként meg kell tanulnod megérteni a pszeudokódot és átfordítani azt az általad választott nyelvre – bár mi itt JavaScriptet használunk, ugyanolyan egyszerű azt bármilyen másik nyelvre átírni.

Hogyan írjuk át ezt a pszeudokódot JavaScript programra? Függvényt kell írni, mert olyan programot írunk, aminek bemenete és kimenete van, és olyan kódot szeretnénk, ami különböző bemenetekkel újrafuttatható. A függvény – nevezzük binarySearch-nek – paraméterei a tömb és a kitalálandó érték, a visszaadott érték a megtalált szám indexe lesz.

Most nézzük meg, hogyan valósítsuk meg a függvény törzsét! A 6. lépésben azt mondjuk, hogy folytasd a 2. lépéssel. Ez ciklusnak hangzik. For ciklust, vagy while ciklust használjunk? Ha mindenáron ragaszkodsz a for ciklushoz, megteheted, de a bináris keresés során tippelt indexek nem a for ciklust kényelmessé tevő szekvenciális sorrendben követik egymást. Először a számításaink alapján tippelhetjük a 12-es indexet, majd a 18-ast. Úgyhogy a while ciklus jobb megoldásnak tűnik.

Még egy fontos dolog hiányzott a pszeudokódból, ami nem számított a kitalálós játék szempontjából, de fontos a tömb bináris kereséséhez. Mi történjen akkor, ha a keresett szám nincs benne a tömbben? Kezdjük vajon azzal, hogy eldöntjük, milyen indexet adjon vissza a binarySearch függvény ebben az esetben? Olyan számnak kell lennie, ami nem lehet a tömb szabályos indexe. Mi -1-et fogunk használni, mivel az nem lehet a tömb indexe. (Tulajdonképpen bármelyik negatív szám megteszi.)

Akkor nincs a kitalálandó szám a tömbben, ha nem marad több lehetséges tipp. A mi példánkban ez akkor fordul elő, ha például a 10-et keressük a primes tömbben. Ha ott lenne, akkor a 7 és a 11 között lenne, ami a 3-as és 4-es indexű elem. Ha követed a min és max értékét a binarySearch függvény futása során, akkor előbb-utóbb eljutsz arra a pontra, ahol min értéke 3 és max értéke 4 lesz. A következő tipp a 3-as indexű elem lesz (mivel (3 + 4) / 2 értéke 3,5, és lefelé kerekítünk), primes[3] értéke kisebb, mint 10, ezért min 4 lesz. De ha mind min mind max értéke 4, a tippnek a 4-es indexű elemnek kell lennie, és primes[4] értéke nagyobb, mint 10. Ekkor max 3 lesz. Mi történik akkor, amikor min egyenlő 4 és max egyenlő 3? Ez azt jelenti, hogy a lehetséges tipp értéke legalább 4 és legfeljebb 3 lehet. De ilyen szám nincs! Ezen a ponton megállapíthatjuk, hogy a 10 nincs benne a primes tömbben, és a binarySearch függvény -1-gyel fog visszatérni. Általánosságban kijelenthetjük, hogy abban az esetben, amikor max kisebb, mint min, akkor tudjuk, hogy a keresett szám nincs benne a rendezett tömbben. Íme a bináris keresés módosított pszeudokódja, ami kezeli azt az esetet is, amikor a keresett szám nincs benne a tömbben:

Most, hogy együtt végiggondoltuk a pszeudokódot, próbáld meg önállóan implementálni a bináris keresést! Nyugodtan nézz vissza a pszeudokódra, ez kifejezetten hasznos is, mert így jobban megérted, hogyan kell pszeudokódból programot írni.

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