Какой алгоритм имеет логарифмическую сложность O(log n)?

Алгоритм бинарного (двоичного) поиска имеет логарифмическую временную сложность O(log n).

Принцип работы бинарного поиска:

1. Требует отсортированного массива (или списка).
2. На каждом шаге сравнивает искомый элемент с элементом в середине текущего диапазона поиска.
3. Если элемент совпадает, поиск завершен.
4. Если искомый элемент меньше среднего, поиск продолжается в левой половине диапазона.
5. Если искомый элемент больше среднего, поиск продолжается в правой половине диапазона.
6. Диапазон поиска сокращается вдвое на каждом шаге.

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

python