Какой алгоритм имеет логарифмическую сложность 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  # Элемент не найден

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

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