Koji algoritam ima logaritamsku složenost 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), јер се у сваком кораку простор претраге дели на пола.