Bináris keresési algoritmus EXAMPLE-vel

Mielőtt belemerülnénk a bináris keresésbe, nézzük meg, mi is az a keresés.

Mi az a Keresés?

A keresés egy olyan segédprogram, amely lehetővé teszi a felhasználók számára, hogy dokumentumokat, fájlokat, adathordozókat vagy bármilyen más típusú adatot találjanak az adatbázisban. A keresés azon az egyszerű elven működik, hogy a kritériumokat össze kell egyeztetni a rekordokkal, és megjeleníteni a felhasználó számára. Ily módon a legalapvetőbb keresési funkció működik.

Mi az a bináris keresés?

A bináris keresés egy fejlett keresési algoritmus, amely rendezett listákból keres és kér le adatokat. Alapvető működési elve, hogy a listában szereplő adatokat kettéosztja, amíg a kívánt értéket meg nem találja, és meg nem jeleníti a felhasználónak a keresési eredmények között. A bináris keresés közismert nevén egy félintervallumú keresés vagy logaritmikus keresés.

Hogyan működik a bináris keresés?

A bináris keresés a következő módon működik:

• A keresési folyamat a rendezett adattömb középső elemének megkeresésével kezdődik.
• Ezt követően a kulcs értékét összehasonlítják az elem értékével.
• Ha a kulcs értéke kisebb, mint a középső elem értéke, akkor a keresés a felső értékeket elemzi a középső elemhez képest összehasonlítás és egyeztetés céljából.
• Abban az esetben, ha a kulcs értéke nagyobb, mint a középső elem értéke, akkor a keresés az alacsonyabb értékeket elemzi a középső elemhez képest összehasonlítás és egyeztetés céljából.

Bináris keresési algoritmus (pszeudokód)

A bináris keresés egy rövid, iteratív rutinként írható fel. Két mutatót tart meg, az alsó és a felső értéket, és szűkíti a tartományt, amíg a célt meg nem találja, vagy a tartomány kiürül.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

A rutin sikeres végrehajtás esetén a cél indexét adja vissza, és -1-et, ha az érték hiányzik. Mivel a tartomány minden menetben feleződik, a ciklus legfeljebb log₂(n) alkalommal fut le.

Példa bináris keresésre

Nézzünk egy szótár példáját. Ha meg kell találnia egy bizonyos szót, senki nem megy végig az egyes szavakon egymás után, hanem véletlenszerűen megkeresi a legközelebbi szavakat, hogy megkeresse a kívánt szót.

A fenti kép a következőket szemlélteti:

1. Van egy 10 számjegyű tömbje, és meg kell találni az 59-es elemet.
2. Minden elemet 0-tól 9-ig terjedő indexszel jelölünk. Most kiszámítjuk a tömb közepét. Ehhez az index bal és jobb szélső értékét elosztjuk 2-vel. Az eredmény 4.5, de mi az alsó értéket vesszük. Ezért a középpont 4.
3. Az algoritmus a középső (4) és az alsó határ között lévő összes elemet elhagyja, mivel az 59 nagyobb, mint 24, és így a tömbben csak 5 elem marad.
4. Most az 59 nagyobb, mint 45 és kisebb, mint 63. A középső érték 7. Ezért a jobb oldali indexérték középső − 1 lesz, ami 6-tal egyenlő, a bal oldali indexérték pedig ugyanaz marad, mint korábban, ami 5.
5. Ezen a ponton tudja, hogy az 59 a 45 után következik. Így a bal oldali index, amely 5, szintén középsővé válik.
6. Ezek az iterációk mindaddig folytatódnak, amíg a tömb egyetlen elemre csökken, vagy a keresendő elem a tömb közepe lesz.

Példa 2

A bináris keresés működésének megértéséhez nézzük meg a következő példát.

1. Rendezett értékek tömbje 2 és 20 között van, és meg kell találnia a 18-at.
2. Az alsó és felső határ átlaga (l + r) / 2 = 4. A keresett érték nagyobb, mint a középső érték, ami 4.
3. A középső értéknél kisebb tömbértékeket kihagyja a keresésből, a középső értéknél nagyobb értékeket pedig keresi a rendszer.
4. Ez egy ismétlődő felosztási folyamat mindaddig, amíg a tényleges keresendő elem meg nem található.

Miért van szükségünk bináris keresésre?

A következő okok miatt a bináris keresés jobb választás keresési algoritmusként:

• A bináris keresés hatékonyan működik rendezett adatokon, az adatok méretétől függetlenül.
• Ahelyett, hogy a keresést úgy hajtaná végre, hogy sorozatban végigmenne az adatokon, a bináris algoritmus véletlenszerűen hozzáfér az adatokhoz, hogy megtalálja a kívánt elemet. Ez rövidebbé és pontosabbá teszi a keresési ciklusokat.
• A bináris keresés a rendezett adatok összehasonlítását rendezési elv alapján végzi el, ahelyett, hogy egyenlőség-összehasonlításokat használna, amelyek lassabbak és többnyire pontatlanok.
• Minden keresési ciklus után az algoritmus a tömb méretét felére osztja; így a következő iterációban csak a tömb fennmaradó felében fog dolgozni.

Ismerd meg a következő oktatóanyagunkat a témában Lineáris keresés: Python, C++ Példa.

Bináris keresés vs. lineáris keresés

A bináris és a lineáris keresés a két leggyakoribb módszer egy érték megtalálására egy gyűjteményben. Az alábbi táblázat bemutatja a különbségeket:

Röviden, a bináris keresés sokkal gyorsabb nagyméretű rendezett adatokon, míg a lineáris keresés egyszerűbb, és az egyetlen lehetőség, ha az adatok nincsenek rendezve.

GYIK