ЯдроКодаподготовка к экзаменам
Учебная платформа

Загружаем материалы

Подготавливаем материалы и навигацию по разделу.

Бинарный поиск в Python: идея поиска в отсортированном списке

Автор: · Обновлено

Бинарный поиск работает только на данных, упорядоченных по тому же правилу, которое используется в сравнении. На каждом шаге выбирается середина текущего полуинтервала: если цель…

Бинарный поиск работает только на данных, упорядоченных по тому же правилу, которое используется в сравнении. На каждом шаге выбирается середина текущего полуинтервала: если цель меньше, правая граница сдвигается; если больше — левая.

Полуинтервал left:right

def binary_search(values, target):
    left = 0
    right = len(values)

    while left < right:
        middle = (left + right) // 2
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle

    if left < len(values) and values[left] == target:
        return left
    return -1


print(binary_search([2, 5, 8, 12, 16], 12))

Результат равен 3. Правая граница не включается, поэтому начальное right равно длине списка. Вариант находит первое подходящее место и затем проверяет точное совпадение.

Инвариант границ

Возможная позиция остаётся внутри [left, right). Команда left = middle вместо middle + 1 может не уменьшить диапазон и создать бесконечный цикл. Смешивание включённой и невключённой правой границы — главный источник ошибок.

Нельзя применять алгоритм к [8, 2, 12, 5], не отсортировав данные. Но сортировка копии меняет индексы относительно исходника, поэтому это не бесплатное исправление. Для одного поиска в коротком списке линейный алгоритм может быть проще.

Границы и отсутствие

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

Сопоставление с bisect

Импортируйте модуль bisect и сравните bisect_left с собственной функцией на отсортированном списке с повторами. Полученная позиция является местом вставки и не гарантирует наличие цели, поэтому после неё нужна проверка границы и равенства. Вставьте новое значение через insort и подтвердите сохранение порядка. Затем передайте несортированный список и зафиксируйте, что модуль не обязан сообщать об ошибке, но результат теряет смысл. Этот опыт закрепляет контракт бинарного поиска и показывает, как стандартная библиотека отделяет поиск позиции от проверки точного совпадения.

Практикум: bisect и обязательная сортировка

Сравните собственный бинарный поиск с bisect_left на списке 1, 3, 3, 7, 9. Для целей 3, 4, 0 и 10 получите позицию вставки, затем отдельно проверьте границу и равенство, чтобы установить наличие. Вставьте 4 через insort и подтвердите сохранение порядка. Передайте несортированную копию и зафиксируйте, что библиотека не обязана обнаружить нарушение предпосылки. В тестах храните как данные, так и утверждение об их сортировке.

Контрольная точка

Почему найденная позиция ещё не доказывает наличие цели? Она может указывать место будущей вставки в конце или перед большим элементом; требуется безопасная проверка индекса и равенства.

Частые вопросы

Как бинарный поиск работает с повторами?

Нужно заранее определить требуемую позицию. bisect_left находит левую границу равных элементов, bisect_right — позицию после них. Произвольный учебный поиск может вернуть любое совпадение, если контракт не уточнён.

Источники