Алгоритмы на Python

Двоичный поиск (binary search) в Python

В этом уроке вы реализуете двоичный поиск, чтобы быстро находить значение в отсортированном списке.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

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

Пример из жизни

Бинарный поиск - это то, как ищут слово в бумажном словаре. Вы открываете его посередине, смотрите, идёт ли ваше слово до или после этой страницы, и отбрасываете половину, где его быть не может. Повторяете с оставшейся половиной, пока не попадёте на слово.

От бумажного словаря к коду
low, high = 0, len(values) - 1📖 Страницы, которые ещё нужно просмотреть
middle = (low + high) // 2👆 Открыть посередине
low = middle + 1➡️ Слово дальше: отбросить первую половину
high = middle - 1⬅️ Слово раньше: отбросить вторую половину
Каждое сравнение делит оставшееся пополам, поэтому даже огромным спискам нужно мало шагов.
Одним предложением

Бинарный поиск находит значение в отсортированном списке, многократно раз за разом сравнивая искомое со средним элементом и отбрасывая половину, где его быть не может. На это уходит O(log n) шагов.

Главное

  1. low и high отмечают часть списка, где искомое ещё может быть.
  2. middle = (low + high) // 2 выбирает средний индекс этой части.
  3. Если values[middle] < target, искомое справа, поэтому low = middle + 1; иначе high = middle - 1.
  4. while low <= high: останавливается, когда диапазон пуст, и функция возвращает -1, если ничего не найдено.
  5. Для 17 поиск проверяет 12, потом 25, потом 17: три сравнения вместо четырёх.

Когда это нужно?

  • Поиск в больших отсортированных данных: ID, словари, отсортированные логи.
  • Поиск места для вставки значения, чтобы список остался отсортированным.
  • Игры в угадайку и любые задачи, где ответ можно сузить по «больше» или «меньше».

Когда это не нужно

  • Данные не отсортированы: сортировка ради одного поиска стоит дороже линейного поиска.
  • Небольшие списки или разовый поиск: in или словарь проще. Если искать по ключу нужно много раз, словарь (dict) или множество (set) работают ещё быстрее.

Визуализация: Двоичный поиск (binary search) в Python

O(log n)

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

Пример кода

Запустить код →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
Получить кнопку запуска для этого примера

Результат выполнения

3

Разбор кода

Переменные low и high задают область, которую ещё осталось проверить. Если средний элемент меньше искомого значения, алгоритм отбрасывает левую половину через low = middle + 1, иначе отбрасывает правую. Временная сложность O(log n) при условии, что входной список уже отсортирован.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

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

< вместо <= в цикле

При условии low < high последняя оставшаяся позиция так и не проверяется, даже если искомое стоит именно там.

Ошибка
while low < high:
Исправление
while low <= high:

Граница не сдвигается за середину

С low = middle цикл может без конца проверять одну и ту же середину.

Ошибка
low = middle
Исправление
low = middle + 1

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи