К содержимому

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

Как в учебнике

Бинарный поиск находит индекс точного совпадения в массиве, отсортированном по неубыванию. В рассматриваемой реализации элементы и цель — . Функция возвращает один подходящий индекс или −1, если совпадения нет; первый или последний индекс среди повторов не обещается.

Включительные границы хранятся в left и right. Инвариант: если цель присутствует и ещё не найдена, хотя бы один её индекс находится внутри текущего диапазона. Середина — (left + right) / 2. Если среднее значение меньше цели, все индексы до середины включительно исключаются; новая левая граница — middle + 1. При большем значении симметрично устанавливается right = middle − 1.

Отсортированность доказывает безопасность исключения. Каждый неуспешный шаг строго уменьшает диапазон, поэтому поиск завершается. При left > right диапазон пуст: инвариант означает, что совпадения нет. На пустом массиве это условие выполнено сразу.

Для массива длины $n\ge2$ худшее время — $O(\log n)$ при постоянной стоимости сравнения и доступа по индексу. Итеративная версия хранит фиксированное число переменных: дополнительная память $O(1)$. Проверка или получение исходной сортировки в эти затраты не входят.

Размер непустого диапазона равен right − left + 1. После неуспешного сравнения остаётся не больше половины прежнего размера: середина уже исключена. Это связывает завершение с оценкой числа шагов. Неизменность исходного списка существенна для доказательства: если во время поиска переставить элементы или изменить их порядок, ранее исключённая половина уже не обязана оставаться безопасной.

На пальцах

В упорядоченном телефонном справочнике сравнение с фамилией посередине сразу исключает одну половину страниц. После сравнения исключается и сама середина, иначе поиск способен вечно открывать последнюю страницу и называть это настойчивостью. Две закладки сохраняют границы оставшегося участка, поэтому помнить все просмотренные записи не нужно. Порядок записей должен сохраняться на всём протяжении поиска: переклеенные между шагами страницы расторгают договор со справочником без уведомления.

Пример

В отсортированном учебном массиве [2, 5, 8, 12, 17, 23, 31] цель равна 17. Индексы начинаются с нуля. Ниже — состояния того же алгоритма, который записан в коде.

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

Начальный диапазон

Левая граница 0, правая 6. Все семь позиций ещё возможны.

Шаг 1 из 4: Начальный диапазон

Все шаги текстом
  1. Начальный диапазон

    Левая граница 0, правая 6. Все семь позиций ещё возможны.

    Значения
    25812172331
    Границы
    left = 0текущийright = 6текущий
  2. Середина равна 12

    Индекс 3 содержит 12, что меньше 17. Индексы 0–3 исключаются; left = 4.

    Значения
    2исключён5исключён8исключён12текущий172331
    Остаются
    17включён23включён31включён
  3. Середина равна 23

    В диапазоне 4–6 середина имеет индекс 5. Значение 23 больше цели, поэтому right = 4.

    Значения
    2исключён5исключён8исключён12исключён1723текущий31исключён
    Остаётся
    17включён
  4. Совпадение

    Границы встретились на индексе 4. Значение 17 равно цели: результат равен 4.

    Значения
    2исключён5исключён8исключён12исключён17включён23исключён31исключён
    Индекс
    4включён

Для отсутствующего 18 первые исключения оставляют тот же индекс 4 со значением 17. Следующее сравнение двигает left на 5 при right = 4, и функция возвращает −1. Это обозначение отсутствия, а не пригодный индекс результата: в Python индекс −1 выбрал бы последний элемент списка. Обращение numbers[index] допустимо только после проверки, что поиск действительно нашёл совпадение.

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

Функция binary_search принимает отсортированный список numbers и цель target, возвращает индекс либо −1 и не изменяет список. На пустом входе right равен −1, поэтому цикл не запускается. Для отсутствующего 18 диапазон в конце пустеет; для одного элемента выполняется не больше одного сравнения с серединой.

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

Авторский текст этой бесплатной статьи опубликован по лицензии CC BY-NC-ND 4.0.

Предыдущая / следующая

Предыдущая
Θ-большое: точный порядок роста
Следующая
Среднее арифметическое наблюдений
  • Натуральные числа: счёт отдельных объектов

    Какие значения подходят для счёта и почему включение нуля нужно оговаривать.

    Читать статью
    Математика
  • Целые числа: счёт по обе стороны нуля

    Положительные и отрицательные целые, ноль и граница целочисленного деления.

    Читать статью
    Математика
  • Рациональные числа: отношение целых

    Число как отношение целых: равные дроби и обязательный ненулевой знаменатель.

    Читать статью
    Математика