Aký algoritmus má logaritmickú zložitosť O(log n)?

Algoritmus binárne (alebo dichotómne) vyhľadávanie má logaritmickú časovú zložitosť O(log n).

Princíp fungovania binárneho vyhľadávania:

1. Vyžaduje zoradený poľ (alebo zoznam).
2. Pri každom kroku porovná hľadaný prvok s prvkom uprostred aktuálneho rozsahu vyhľadávania.
3. Ak sa prvky zhodujú, vyhľadávanie sa ukončí.
4. Ak je hľadaný prvok menší ako stredný, pokračuje v ľavej polovici rozsahu.
5. Ak je väčší, pokračuje v pravej polovici rozsahu.
6. Rozsah vyhľadávania sa pri každom kroku zmenšuje na polovicu.

Príklad implementácie v Pythone:

# Funkcia binárneho vyhľadávania
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Prvok nájdený, vráti index
        elif mid_val < target:
            low = mid + 1  # Ignoruje ľavú polovicu
        else:
            high = mid - 1  # Ignoruje pravú polovicu

    return -1  # Prvok nenájdený

# Príklad použitia
# zoradený_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# cieľ = 23
# výsledok = binary_search(zoradený_list, cieľ)
# if výsledok != -1:
#     print(f"Prvok nájdený na indexe: {výsledok}")
# else:
#     print("Prvok nenájdený")

Logaritmická zložitosť je spôsobená tým, že počet operácií je úmerný logaritmu veľkosti vstupných dát (n), pretože pri každom kroku sa vyhľadávací priestor zmenšuje na polovicu.