Бинарный поиск на Python: как не потерять нужный элемент

Представьте телефонный справочник, отсортированный по фамилии. Чтобы найти «Петрова», нет смысла листать его с первой страницы: откройте середину и посмотрите, в какой половине может остаться фамилия. Бинарный поиск делает то же с массивом. Но у этого сокращения есть условие: порядок элементов должен позволять отбросить половину без риска потерять ответ.

Зачем нужен отсортированный массив

Пусть numbers = [2, 5, 8, 12, 17, 23, 31], а цель — 17. Середина массива содержит 12. Все элементы левее не больше 12, поэтому 17 там быть не может. Оставляем правую часть. Если бы значения стояли в случайном порядке, вывод был бы неверным.

После каждого сравнения остаётся не больше половины прежнего диапазона. Для массива из n элементов это даёт время O(log n); дополнительная память у итеративной версии — O(1). Сортировка исходных данных в эту оценку не входит.

Какие границы хранить

Возьмём две включительные границы: left — первый ещё возможный индекс, right — последний. Пока left <= right, диапазон не пуст. Середина — (left + right) // 2.

Если средний элемент меньше цели, отбрасываем его и всё слева: left = middle + 1. Если больше — отбрасываем его и всё справа: right = middle - 1. Равенство означает, что ответ найден. Строгий сдвиг на единицу важен: иначе на диапазоне из одного элемента цикл может не закончиться.

Простая реализация на Python

def binary_search(numbers: list[int], target: int) -> int:
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2
        value = numbers[middle]

        if value == target:
            return middle
        if value < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

numbers = [2, 5, 8, 12, 17, 23, 31]
print(binary_search(numbers, 17))  # 4
print(binary_search(numbers, 18))  # -1

Индекс начинается с нуля. На пустом массиве right сразу равен -1, цикл не запускается и функция возвращает -1. Если одинаковое значение встречается несколько раз, эта версия возвращает один из его индексов, без обещания найти первый или последний.

Здесь мы искали точное совпадение в обычном отсортированном массиве. Когда нужно найти границу повторов, работать с повёрнутым массивом или искать минимальное допустимое число, правило выбора половины меняется. Эти три случая последовательно разобраны в закрытом материале «Бинарный поиск на Python». На его карточке указаны состав, цена и условия доступа; продажи пока закрыты.