Který algoritmus má logaritmickou složitost O(log n)?

Binární vyhledávací algoritmus (nebo dichotomické hledání) má logaritmickou časovou složitost O(log n).

Princip fungování binárního hledání:

1. Vyžaduje se seřazený pole (nebo seznam).
2. V každém kroku porovnává hledaný prvek s prvkem uprostřed aktuálního rozsahu hledání.
3. Pokud se prvky shodují, hledání končí.
4. Pokud je hledaný prvek menší než prostřední, pokračuje se v levé polovině rozsahu.
5. Pokud je hledaný prvek větší než prostřední, pokračuje se v pravé polovině rozsahu.
6. Rozsah hledání se při každém kroku zmenšuje na polovinu.

Příklad implementace v Pythonu:

# Funkce binárního hledání
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  # Prvek nalezen, vrací index
        elif mid_val < target:
            low = mid + 1  # Ignoruje levou polovinu
        else:
            high = mid - 1  # Ignoruje pravou polovinu

    return -1  # Prvek nenalezen

# Příklad použití
# seřazený_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# cíl = 23
# výsledek = binary_search(seřazený_list, cíl)
# if výsledek != -1:
#     print(f"Prvek nalezen na indexu: {výsledek}")
# else:
#     print("Prvek nenalezen")

Logaritmická složitost je způsobena tím, že počet operací je úměrný logaritmu velikosti vstupních dat (n), protože při každém kroku se vyhledávací prostor zmenšuje na polovinu.