Двоичный поиск (binary search) в Python
В этом уроке вы реализуете двоичный поиск, чтобы быстро находить значение в отсортированном списке.
Введение
Какую задачу это решает
Поиск одного значения в списке из миллиона элементов перебором может занять миллион сравнений. Если список отсортирован, можно сделать гораздо лучше: хватит примерно 20 сравнений, потому что каждая проверка отбрасывает половину оставшегося.
Пример из жизни
Бинарный поиск - это то, как ищут слово в бумажном словаре. Вы открываете его посередине, смотрите, идёт ли ваше слово до или после этой страницы, и отбрасываете половину, где его быть не может. Повторяете с оставшейся половиной, пока не попадёте на слово.
low, high = 0, len(values) - 1📖 Страницы, которые ещё нужно просмотретьmiddle = (low + high) // 2👆 Открыть посерединеlow = middle + 1➡️ Слово дальше: отбросить первую половинуhigh = middle - 1⬅️ Слово раньше: отбросить вторую половинуБинарный поиск находит значение в отсортированном списке, многократно раз за разом сравнивая искомое со средним элементом и отбрасывая половину, где его быть не может. На это уходит O(log n) шагов.
Главное
lowиhighотмечают часть списка, где искомое ещё может быть.middle = (low + high) // 2выбирает средний индекс этой части.- Если
values[middle] < target, искомое справа, поэтомуlow = middle + 1; иначеhigh = middle - 1. while low <= high:останавливается, когда диапазон пуст, и функция возвращает-1, если ничего не найдено.- Для 17 поиск проверяет 12, потом 25, потом 17: три сравнения вместо четырёх.
Когда это нужно?
- Поиск в больших отсортированных данных: ID, словари, отсортированные логи.
- Поиск места для вставки значения, чтобы список остался отсортированным.
- Игры в угадайку и любые задачи, где ответ можно сузить по «больше» или «меньше».
Когда это не нужно
- Данные не отсортированы: сортировка ради одного поиска стоит дороже линейного поиска.
- Небольшие списки или разовый поиск:
inили словарь проще. Если искать по ключу нужно много раз, словарь (dict) или множество (set) работают ещё быстрее.
Визуализация: Двоичный поиск (binary search) в Python
O(log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
< вместо <= в цикле
При условии low < high последняя оставшаяся позиция так и не проверяется, даже если искомое стоит именно там.
while low < high:
while low <= high:
Граница не сдвигается за середину
С low = middle цикл может без конца проверять одну и ту же середину.
low = middle
low = middle + 1
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Время производства на фабрике Найдите минимальное время, за которое параллельные машины смогут изготовить заданное количество изделий. Средне
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Сложно