Binárne vyhľadávanie

Binárne vyhľadávanie je dramaticky efektívnejšie ako lineárne — ale funguje len na zoradenom zozname. Princíp je genialálne jednoduchý: vždy sa pozri do stredu a podľa výsledku porovnania vylúč polovicu.

Princíp — hra "hádaj číslo"

Predstav si, že niekto myslí číslo od 1 do 100 a ty ho musíš uhádnuť. Pri každom pokuse ti povie "väčšie", "menšie" alebo "správne".

Najlepšia stratégia:

1. Povedz 50. "Väčšie" → hľadaj len v 51–100.
2. Povedz 75. "Menšie" → hľadaj len v 51–74.
3. Povedz 62. "Väčšie" → hľadaj len v 63–74.
4. ...a tak ďalej.

Touto stratégiou uhádneš akékoľvek číslo od 1 do 100 v najviac 7 pokusoch! (log₂(100) ≈ 7)

Implementácia v Pythone

def binarne_vyhladavanie(zoznam, ciel):
    lava = 0
    prava = len(zoznam) - 1
    
    while lava <= prava:
        stred = (lava + prava) // 2   # celočíselné delenie
        
        if zoznam[stred] == ciel:
            return stred               # nájdené!
        elif zoznam[stred] < ciel:
            lava = stred + 1           # hľadaj v pravej polovici
        else:
            prava = stred - 1          # hľadaj v ľavej polovici
    
    return -1   # nenájdené

zoradene = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print(binarne_vyhladavanie(zoradene, 7))    # 3 (index)
print(binarne_vyhladavanie(zoradene, 10))   # -1 (nenájdené)

Vizualizácia vyhľadávania čísla 7

Zoznam: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] (indexy 0–9)

Krok 1: lava=0, prava=9, stred=4, zoznam[4]=9
        9 > 7 → hľadaj vľavo, prava=3

Krok 2: lava=0, prava=3, stred=1, zoznam[1]=3
        3 < 7 → hľadaj vpravo, lava=2

Krok 3: lava=2, prava=3, stred=2, zoznam[2]=5
        5 < 7 → hľadaj vpravo, lava=3

Krok 4: lava=3, prava=3, stred=3, zoznam[3]=7
        7 == 7 → NÁJDENÉ! Vrát 3

Lineárne vyhľadávanie by potrebovalo 4 porovnania, binárne tiež — ale pri väčšom zozname je rozdiel obrovský.

Porovnanie s lineárnym vyhľadávaním

Podmienka použitia

Binárne vyhľadávanie vyžaduje zoradený zoznam. Ak zoznam nie je zoradený, musíš ho najprv usporiadať.

nezoradeney = [5, 1, 8, 3, 9]
zoradeney = sorted(nezoradeney)

# Teraz môžeš použiť binárne vyhľadávanie
index = binarne_vyhladavanie(zoradeney, 8)
print(f"8 je na indexe {index} zoradeného zoznamu")   # index 3

Vstavané nástroje v Pythone

Modul bisect poskytuje binárne vyhľadávanie:

import bisect

zoradeney = [1, 3, 5, 7, 9, 11]
pozicia = bisect.bisect_left(zoradeney, 7)
print(pozicia)   # 3 — index kde sa nachádza alebo kam by sa vložilo