Hogyan működik a bináris keresőalgoritmus?

A bináris keresés egy rendezett tömb elemzésével működik, folyamatosan felosztva a keresési intervallumot feleire.

1. Inicializálás: Meghatározza a keresési intervallum bal és jobb határát (általában a tömb kezdete és vége).
2. Összehasonlítás: Számolja ki az intervallum középső indexét. Ennek az indexnek az értékét összehasonlítja a keresett elemmel.
3. Az intervallum csökkentése:
   • Ha a középső érték megegyezik a keresett elemmel, az elem megtalálva.
   • Ha a középső érték nagyobb, mint a keresett, a keresés folytatódik az intervallum bal felében. A jobb határ a közép - 1 lesz.
   • Ha a középső érték kisebb, mint a keresett, a keresés folytatódik a jobb felében. A bal határ a közép + 1 lesz.
4. Ismétlés: A 2. és 3. lépések addig ismétlődnek, amíg az elem megtalálásra kerül vagy az intervallum üres lesz.

Az algoritmus összetettsége O(log n), ami sokkal hatékonyabb, mint a lineáris keresés nagy tömbök esetén.

Python példakód:

def binary_search(arr, target):
    """
    A bináris keresés megvalósítása.
    Egy rendezett tömböt és a keresett értéket veszi be.
    Visszaadja az elem indexét vagy -1-et, ha nem található.
    """
    bal, jobb = 0, len(arr) - 1

    while bal <= jobb:
        közép = (bal + jobb) // 2  # A középső index számítása
        közép_érték = arr[közép]      # A középen lévő érték

        if közép_érték == target:
            return közép  # Elem megtalálva
        elif közép_érték < target:
            bal = közép + 1  # Keresés jobbra
        else: # közép_érték > target
            jobb = közép - 1 # Keresés balra

    return -1 # Elem nem található