Ako funguje algoritmus binárneho vyhľadávania?

Binárne vyhľadávanie funguje analýzou zoradeného poľa a opakovaným delením vyhľadávacieho intervalu na polovice.

1. Inicializácia: Určí sa ľavý a pravý okraj vyhľadávacieho intervalu (zvyčajne začiatok a koniec poľa).
2. Porovnanie: Vypočíta sa index stredu intervalu. Hodnota na tomto indexe sa porovná s hľadaným prvkom.
3. Zmenšenie intervalu:
   • Ak sa hodnota uprostred zhoduje s hľadaným, prvok je nájdený.
   • Ak je hodnota uprostred väčšia ako hľadaný, vyhľadávanie pokračuje v ľavej polovici intervalu. Pravý okraj sa posunie na stred - 1.
   • Ak je hodnota uprostred menšia ako hľadaný, vyhľadávanie pokračuje v pravej polovici intervalu. Ľavý okraj sa posunie na stred + 1.
4. Opakovanie: Kroky 2 a 3 sa opakujú, kým sa nenájde prvok alebo intervalu sa nezmení na prázdny.

Zložitosť algoritmu je O(log n), čo je oveľa efektívnejšie ako lineárne vyhľadávanie pre veľké polia.

Príklad implementácie v Pythone:

def binary_search(arr, target):
    """
    Implementácia binárneho vyhľadávania.
    Prijíma zoradené pole a hľadanú hodnotu.
    Vráti index prvku alebo -1, ak nie je nájdený.
    """
    ľavá, pravá = 0, len(arr) - 1

    while ľavá <= pravá:
        stred = (ľavá + pravá) // 2  # Výpočet indexu stredu
        stredná_hodnota = arr[stred]      # Získanie hodnoty uprostred

        if stredná_hodnota == target:
            return stred  # Prvok nájdený
        elif stredná_hodnota < target:
            ľavá = stred + 1  # Vyhľadávanie vpravo
        else: # stredná_hodnota > target
            pravá = stred - 1 # Vyhľadávanie vľavo

    return -1 # Prvok nenájdený