Jak funguje algoritmus binárního vyhledávání?

Binární vyhledávání funguje analýzou seřazeného pole a opakovaným dělením vyhledávacího intervalu na poloviny.

1. Inicializace: Určí se levý a pravý okraj vyhledávacího intervalu (obvykle začátek a konec pole).
2. Porovnání: Vypočítá se index středu intervalu. Hodnota na tomto indexu se porovná s hledaným prvkem.
3. Zmenšení intervalu:
   • Pokud se hodnota uprostřed shoduje s hledaným, prvek byl nalezen.
   • Pokud je hodnota uprostřed větší než hledaný, pokračuje se v levé polovině intervalu. Pravý okraj se posune na střed - 1.
   • Pokud je hodnota uprostřed menší než hledaný, pokračuje se v pravé polovině intervalu. Levý okraj se posune na střed + 1.
4. Opakování: Kroky 2 a 3 se opakují, dokud se prvek nenajde nebo intervalu nezbývá.

Složitost algoritmu je O(log n), což je mnohem efektivnější než lineární vyhledávání u velkých polí.

Příklad implementace v Pythonu:

def binary_search(arr, target):
    """
    Implementace binárního vyhledávání.
    Přijímá seřazené pole a hledanou hodnotu.
    Vrací index prvku nebo -1, pokud není nalezen.
    """
    levá, pravá = 0, len(arr) - 1

    while levá <= pravá:
        střed = (levá + pravá) // 2  # Výpočet indexu středu
        střední_hodnota = arr[střed]      # Získání hodnoty uprostřed

        if střední_hodnota == target:
            return střed  # Prvek nalezen
        elif střední_hodnota < target:
            levá = střed + 1  # Hledaný je větší, hledání v pravé části
        else: # střední_hodnota > target
            pravá = střed - 1 # Hledaný je menší, hledání v levé části

    return -1 # Prvek nenalezen