Кой алгоритъм има логаритмична сложност O(log n)?

Алгоритъмът за двоично търсене има логаритмична времева сложност O(log n).

Принцип на работа на двоичното търсене:

1. Изисква сортиран масив (или списък).
2. На всяка стъпка сравнява търсения елемент с елемента в средата на текущия диапазон.
3. Ако елементите съвпадат, търсенето приключва.
4. Ако търсеният елемент е по-малък от средния, продължава в лявата половина.
5. Ако е по-голям, продължава в дясната половина.
6. Диапазонът се намалява наполовина на всяка стъпка.

Пример за реализация на Python:

# Функция за двоично търсене
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  # Намерен елемент, връща индекс
        elif mid_val < target:
            low = mid + 1  # Игнорира лявата половина
        else:
            high = mid - 1  # Игнорира дясната половина

    return -1  # Елемент не е намерен

# Пример за използване
# сортиран_масив = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# цел = 23
# резултат = binary_search(сортиран_масив, цел)
# if резултат != -1:
#     print(f"Елементът е намерен на индекс: {резултат}")
# else:
#     print("Елементът не е намерен")

Логаритмичната сложност се дължи на факта, че броят на операциите е пропорционален на логаритъма на размера на входните данни (n), тъй като на всяка стъпка пространството за търсене се намалява наполовина.