Care algoritm are o complexitate logaritmică O(log n)?

Algoritmul de căutare binară (sau dicotomică) are o complexitate temporară logaritmică O(log n).

Principiul de funcționare al căutării binare:

1. Necesită un array (sau listă) sortat.
2. La fiecare pas, compară elementul căutat cu elementul din mijlocul intervalului de căutare curent.
3. Dacă elementele coincid, căutarea se încheie.
4. Dacă elementul căutat este mai mic decât cel din mijloc, continuă în jumătatea stângă a intervalului.
5. Dacă elementul căutat este mai mare decât cel din mijloc, continuă în jumătatea dreaptă a intervalului.
6. Intervalul de căutare se reduce la jumătate la fiecare pas.

Exemplu de implementare în Python:

# Funcție de căutare binară
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  # Element găsit, returnează indexul
        elif mid_val < target:
            low = mid + 1  # Ignoră jumătatea stângă
        else:
            high = mid - 1  # Ignoră jumătatea dreaptă

    return -1  # Element negăsit

# Exemplu de utilizare
# list_sortată = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# valoare_căutată = 23
# rezultat = binary_search(list_sortată, valoare_căutată)
# if rezultat != -1:
#     print(f"Element găsit la index: {rezultat}")
# else:
#     print("Element negăsit")

Complexitatea logaritmică se datorează faptului că numărul de operații este proporțional cu logaritmul dimensiunii datelor de intrare (n), deoarece la fiecare pas, spațiul de căutare se reduce la jumătate.