Бинарный поиск

За O(log n) находим элемент в отсортированном массиве из миллиона за 20 шагов.

Бинарный поиск — поиск в отсортированном массиве, при котором на каждом шаге диапазон поиска делится пополам.

Как это работает

Берём середину диапазона. Если там искомое — нашли. Если середина меньше цели — цель правее, отбрасываем левую половину. Иначе отбрасываем правую. Каждый шаг уменьшает диапазон вдвое: для миллиона элементов хватит около 20 шагов.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

data = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(data, 7))
print(binary_search(data, 1))
print(binary_search(data, 8))

Вывод:

3
0
-1

Поиск позиции вставки

Часто нужно не «есть ли элемент», а «куда его вставить, сохранив порядок». В стандартной библиотеке это bisect.

import bisect

arr = [1, 3, 5, 7, 9]
print(bisect.bisect_left(arr, 5))   # позиция для 5
print(bisect.bisect_left(arr, 6))   # 6 встал бы сюда
print(bisect.bisect_right(arr, 5))  # позиция после 5

Вывод:

2
3
3

Как работает под капотом

Главная тонкость — инвариант границ. В варианте с left <= right границы включительные: искомое всегда внутри [left, right], если оно вообще есть. Поэтому при arr[mid] < target мы пишем left = mid + 1 (mid уже проверен, исключаем его), а не left = mid — иначе при двух элементах цикл зациклится. Число шагов равно log2(n), округлённому вверх: каждый шаг ровно вдвое сокращает диапазон.

Частые ошибки

mid = mid вместо mid + 1/mid - 1 — бесконечный цикл.
Применять к неотсортированному массиву — результат бессмысленный.
Путать < и <= в условии цикла: при включительных границах нужно <=, иначе пропустите крайний элемент.
Переполнение left + right в языках с фиксированными int (в Python неактуально, но на собеседовании пишут left + (right - left) // 2).

Итог

Бинарный поиск — O(log n) на отсортированных данных.
Сдвигайте границы за mid (mid + 1/mid - 1), чтобы не зациклиться.
bisect из stdlib решает задачу позиции вставки.