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

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

Идея поиска пополам

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

Официально этот приём называется бинарным поиском (англ. binary search, «поиск делением пополам»). Это алгоритм, который ищет элемент в отсортированном списке, сравнивая искомое значение со средним элементом оставшегося диапазона и каждый раз отбрасывая ровно половину вариантов. Слово «бинарный» здесь означает не двоичные числа, а именно деление на две части на каждом шаге.

Посмотрим на один шаг такого поиска, пока без цикла — просто чтобы увидеть механику:

items = [2, 4, 6, 8, 10, 12, 14]
low = 0
high = len(items) - 1
mid = (low + high) // 2
print(mid, items[mid])

Разберём, что здесь происходит:

• items = [2, 4, 6, 8, 10, 12, 14] — отсортированный по возрастанию список, в котором будем искать. Это обязательное условие бинарного поиска, к нему вернёмся в следующем разделе.
• low = 0 — левая граница диапазона, в котором ещё может находиться искомое число. Сначала это самый первый индекс списка.
• high = len(items) - 1 — правая граница диапазона: функция len() уже знакома вам, она возвращает количество элементов, а минус один даёт индекс последнего элемента (индексы в Python начинаются с нуля).
• mid = (low + high) // 2 — индекс среднего элемента диапазона. Складываем границы и делим пополам оператором целочисленного деления //: он отбрасывает дробную часть, так что mid всегда получается целым индексом, а не дробным числом. Здесь (0 + 6) // 2 даёт 3.
• print(mid, items[mid]) — печатаем индекс середины и значение по этому индексу. Выведется 3 8: средний элемент списка — число 8 с индексом 3.

Если бы мы искали число 8, поиск закончился бы на этом шаге. Если искомое больше 8, отбрасываем всю левую половину вместе со средним элементом и работаем только с правой частью, а если меньше — наоборот, отбрасываем правую половину. Одно сравнение — и вариантов для проверки вдвое меньше.

Почему список обязательно должен быть отсортирован

Вернёмся к справочнику. Приём «откроем на середине и отбросим половину» работает только потому, что фамилии идут по алфавиту. Если бы страницы были перемешаны случайно, открыв книгу на середине, вы бы вообще ничего не могли сказать о том, в какой половине искать дальше.

Бинарный поиск полагается на то, что список отсортирован — каждый следующий элемент больше или равен предыдущему. Именно упорядоченность позволяет по одному сравнению с серединой понять, где искать: если искомое число больше среднего элемента, оно точно не может быть левее него, ведь слева все элементы ещё меньше.

messy = [12, 3, 8, 1, 14, 6, 10]
low = 0
high = len(messy) - 1
mid = (low + high) // 2
print(messy[mid])

Разберём этот пример:

• messy = [12, 3, 8, 1, 14, 6, 10] — те же семь чисел, но в случайном порядке, без сортировки.
• mid = (low + high) // 2 — вычисляется так же и снова даёт индекс 3.
• print(messy[mid]) — выведет 1: по индексу 3 в этом списке стоит число 1. Но из того, что средний элемент маленький, нельзя понять, в какой половине искать — порядка здесь нет, и вывод о «половине, которую можно отбросить», был бы просто неверным.

Пишем функцию бинарного поиска

Один шаг мы уже разобрали, но настоящий поиск повторяет его снова и снова, пока не найдёт число или пока границы не «сойдутся», то есть low не станет больше high — значит, искать больше негде. Это классическая ситуация для цикла while: повторяем, пока условие верно, а внутри на каждом шаге двигаем одну из границ.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Разберём построчно:

• def binary_search(items, target): — объявляем функцию с двумя параметрами: список items, в котором ищем, и число target, которое ищем.
• low = 0 и high = len(items) - 1 — начальные границы диапазона поиска: весь список целиком.
• while low <= high: — пока левая граница не превышает правую, диапазон не пуст и есть смысл проверять дальше. Как только low станет больше high, значит, все варианты перебраны и элемента в списке нет.
• mid = (low + high) // 2 — индекс середины текущего диапазона, пересчитывается заново на каждом шаге, потому что границы меняются.
• if items[mid] == target: return mid — если средний элемент и есть искомое число, сразу возвращаем его индекс и выходим из функции.
• elif items[mid] < target: low = mid + 1 — если средний элемент меньше искомого, оно может быть только правее середины: сдвигаем левую границу сразу за середину, левую половину отбрасываем.
• else: high = mid - 1 — иначе средний элемент больше искомого, значит, оно может быть только левее: сдвигаем правую границу перед серединой.
• return -1 — выполнится, только если цикл закончился сам, без совпадения: границы «сошлись», а элемента так и не нашлось. Число -1 здесь означает «не найден», как и во многих встроенных инструментах Python.

scores = [10, 25, 30, 47, 52, 68, 71, 89]
print(binary_search(scores, 47))
print(binary_search(scores, 100))

3
-1

Сложность: O(log n)

В прошлом уроке вы уже встречали запись вида O(n) и O(n²) — оценку того, как растёт число операций вместе с размером списка. У бинарного поиска своя оценка: O(log n), где log — логарифм. Читается это так: «столько раз, сколько n можно поделить пополам, прежде чем получится единица».

Список из 8 элементов делится пополам 3 раза (8, потом 4, потом 2, потом 1), список из 1000 — около 10 раз, а из миллиона — около 20 раз. Линейному перебору для тех же элементов в худшем случае нужен миллион сравнений. Разница между «20 шагов» и «миллион шагов» и объясняет, почему бинарный поиск так важен.

numbers = list(range(1, 17))
low, high, steps = 0, len(numbers) - 1, 0
target = 13
while low <= high:
    steps = steps + 1
    mid = (low + high) // 2
    if numbers[mid] == target:
        break
    elif numbers[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print(steps)

Разберём, что здесь добавилось по сравнению с функцией выше:

• numbers = list(range(1, 17)) — уже знакомая функция range() создаёт последовательность чисел от 1 до 16, а list() превращает её в список.
• steps = 0 и steps = steps + 1 — счётчик шагов, увеличивается на единицу на каждом проходе цикла.
• break — уже знакомое слово: как только нашли число, сразу выходим из цикла, дальше считать шаги незачем.
• print(steps) — выведет 4: для списка из 16 элементов хватило четырёх делений пополам, тогда как перебор по одному занял бы до 16 сравнений.

Задача посложнее: первое вхождение среди повторов

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

Это называется поиском первого (самого левого) вхождения. Идея: найдя совпадение, не спешим возвращать результат, а запоминаем индекс отдельно и продолжаем искать в левой половине — вдруг там есть ещё одно такое же число, но раньше. Поиск останавливается, когда границы сходятся, и возвращается последний запомненный индекс.

def find_first(items, target):
    low = 0
    high = len(items) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            result = mid
            high = mid - 1
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

Разберём, чем эта функция отличается от обычного бинарного поиска:

• result = -1 — заранее готовим ответ на случай, если числа в списке вообще не окажется.
• if items[mid] == target: — нашли совпадение, но, в отличие от прошлой функции, не выходим сразу.
• result = mid — запоминаем этот индекс как лучший известный ответ на текущий момент.
• high = mid - 1 — сужаем диапазон до ЛЕВОЙ половины, включая саму середину: вдруг там найдётся более раннее совпадение. Причина сдвига та же граница, что и при «средний элемент больше искомого», но смысл другой — мы не отбрасываем найденное значение, а перепроверяем, нет ли такого же раньше.
• return result — когда границы сойдутся, возвращаем самый левый из найденных индексов, а если совпадений не было — так и останется -1.

Проверим: find_first([1, 2, 2, 2, 5, 9], 2) должна вернуть 1 — индекс самой первой двойки, хотя в списке их целых три подряд.

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