Бинарный поиск по ответу: шаблон, инварианты и задачи на Python

От «найти элемент» к монотонному предикату

Классический поиск в отсортированном массиве тоже ищет границу. Возьмём предикат a[i] >= x: на отсортированном массиве он выглядит как False, …, False, True, …, True, и первая позиция с True — ровно то, что возвращает bisect.bisect_left. Документация Go описывает sort.Search так же: функция ищет наименьший индекс в [0, n), где f(i) истинно, при условии, что после первого true значения остаются true.

Функция first_true ниже ничего не знает про массивы: ей нужны диапазон и предикат. Вывод совпадает с bisect_left для всех трёх запросов: 3 1 1, 4 3 3 и 9 5 5. Последняя строка показывает соглашение полуинтервала: если подходящего значения нет, возвращается hi, то есть len(a). Дальше этот же код решает задачи, где «массив» — множество всех возможных ответов.

from bisect import bisect_left

def first_true(lo, hi, ok):
    """Первое x в [lo, hi), для которого ok(x) истинно; hi, если такого нет."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid        # mid подходит: ответ в [lo, mid]
        else:
            lo = mid + 1    # mid не подходит: ответ в [mid + 1, hi)
    return lo

a = [1, 3, 3, 5, 8]
for x in (3, 4, 9):
    mine = first_true(0, len(a), lambda i: a[i] >= x)
    print(x, mine, bisect_left(a, x))

• Python: модуль bisect
• Go: sort.Search

Инвариант lo/hi и выбор интервала

Шаблон держится на двух утверждениях: всё левее lo заведомо не подходит, а hi — подходящее значение или граница «ответа нет». Цикл идёт, пока lo < hi. Середина mid = (lo + hi) // 2 всегда строго меньше hi, поэтому обе ветки сужают интервал: hi = mid уменьшает правую границу, lo = mid + 1 сдвигает левую. Когда lo == hi, инвариант сам даёт ответ, без дополнительной проверки после цикла.

Записей шаблона несколько, и все корректны, если не смешивать их части. Ошибки чаще всего появляются, когда условие цикла взято из одной записи, а обновление границ — из другой. Выберите одну, проговорите инвариант вслух и проверьте на массивах из одного и двух элементов. Запись с открытыми границами, где lo заведомо плохое, а hi заведомо хорошее, подробно разобрана на cp-algorithms, а для теории на русском подойдёт глава о двоичном поиске в хендбуке Яндекса «Основы алгоритмов».

• cp-algorithms: Binary search
• Яндекс, хендбук «Основы алгоритмов»: двоичный поиск

Ошибки на ±1 и бесконечный цикл

Классическая ловушка — искать последнее подходящее значение через lo = mid и при этом округлять середину вниз. Пока интервал широкий, всё работает, но при hi = lo + 1 середина совпадает с lo, и если проверка успешна, интервал больше не меняется. В примере ищется целый корень из 10: начиная с шага 3 значения lo, hi и mid застывают на 3 4 3, и только ограничитель шагов останавливает программу строкой «завис».

Исправлений два, и оба про согласованность. Для поиска последнего true округляйте середину вверх, mid = (lo + hi + 1) // 2, — тогда isqrt_fixed печатает 3 4 0 для 10, 16 и 0. Или переформулируйте задачу как поиск первого false и вычтите единицу. В Python переполнения нет, но в Go и Java сумма lo + hi может выйти за пределы int, поэтому там пишут lo + (hi − lo) / 2; cp-algorithms напоминает, что такая ошибка около девяти лет жила в JDK.

• Каждая ветка должна строго сужать интервал — проверьте это для hi = lo + 1.
• Прогоните пустой диапазон, один элемент и два элемента до того, как скажете «готово».
• Если предикат истинен везде или нигде, ответ — граница по соглашению, а не исключение.

def isqrt_buggy(n, max_steps=6):
    lo, hi = 0, n               # ищем последнее x, где x * x <= n
    for step in range(max_steps):
        if lo >= hi:
            return lo
        mid = (lo + hi) // 2    # округление вниз
        print(step, lo, hi, mid)
        if mid * mid <= n:
            lo = mid            # при hi == lo + 1 получаем mid == lo
        else:
            hi = mid - 1
    return "завис"

def isqrt_fixed(n):
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2   # округление вверх для «последнего true»
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo

print(isqrt_buggy(10))
print(isqrt_fixed(10), isqrt_fixed(16), isqrt_fixed(0))

Задачи 1–2: грузоподъёмность за D дней и минимальная скорость

Первая задача: посылки с весами weights грузят строго по порядку, за день — не больше cap, нужно найти минимальную вместимость, при которой хватит days дней. Ответ лежит в [max(weights), sum(weights)]: меньше максимума не поместится самая тяжёлая посылка, а при сумме хватит одного дня. Предикат fits(cap) монотонен: если груз укладывается в days дней при cap, то при cap + 1 — тем более. Проверка — один жадный проход за O(n).

Вторая задача устроена так же: кучи бананов piles, за час можно съесть не больше k из одной кучи, нужно уложиться в hours часов. Время при скорости k — сумма потолков p / k, и с ростом k оно не растёт. Программа печатает 15, 6, 4 и 23. Схема ответа общая: назвать диапазон, одним предложением доказать монотонность, написать проверку и вызвать first_true. Обе задачи есть на LeetCode под номерами 1011 и 875.

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def ship_within_days(weights, days):
    def fits(cap):                      # хватит ли days дней при вместимости cap
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used, load = used + 1, 0
            load += w
        return used <= days
    return first_true(max(weights), sum(weights), fits)

def min_eating_speed(piles, hours):
    def enough(k):                      # успеем ли за hours часов со скоростью k
        return sum((p + k - 1) // k for p in piles) <= hours
    return first_true(1, max(piles), enough)

print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
print(ship_within_days([3, 2, 2, 4, 1, 4], 3))
print(min_eating_speed([3, 6, 7, 11], 8))
print(min_eating_speed([30, 11, 23, 4, 20], 6))

Задача 3: k-е число в таблице умножения

Иногда ответ — само значение, а не параметр процесса. Нужно найти k-е по возрастанию число в таблице умножения m × n, не строя её. Предикат «чисел, не больших x, хотя бы k» монотонен по x, а посчитать их легко: в строке row таких чисел min(x // row, n). Проверка стоит O(m), поиск идёт по диапазону [1, m · n], итого O(m · log(m · n)) вместо O(mn · log(mn)) для сортировки всей таблицы.

Тонкий момент, о котором спрашивают: почему найденное x вообще есть в таблице? Если бы минимального x с count_le(x) ≥ k в таблице не было, то count_le(x − 1) = count_le(x) ≥ k, и x не было бы минимальным. Программа печатает 3 6 и True: результат совпал с сортировкой полного списка для всех m и n от 1 до 7 и всех допустимых k. Сверка с перебором на маленьких входах ловит ошибку на ±1 раньше интервьюера.

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def kth_in_table(m, n, k):
    """k-е по возрастанию число в таблице умножения m x n (с повторами)."""
    def count_le(x):                    # сколько чисел таблицы <= x
        return sum(min(x // row, n) for row in range(1, m + 1))
    return first_true(1, m * n, lambda x: count_le(x) >= k)

def brute(m, n, k):
    return sorted(i * j for i in range(1, m + 1) for j in range(1, n + 1))[k - 1]

print(kth_in_table(3, 3, 5), kth_in_table(2, 3, 6))
print(all(kth_in_table(m, n, k) == brute(m, n, k)
          for m in range(1, 8) for n in range(1, 8) for k in range(1, m * n + 1)))

Вещественный бинарный поиск и итоговая сложность

Когда ответ — вещественное число, условие «пока hi − lo > eps» выглядит естественно, но цикл может не завершиться. Соседние double около 10¹⁰ отстоят друг от друга примерно на 1,9 · 10⁻⁶: когда lo и hi становятся соседями, середина округляется к одной из границ, и при eps = 10⁻⁹ интервал перестаёт сужаться. Вывод подтверждает: math.ulp(1e10) равен 1.9073486328125e-06, а 1e10 + 1e-9 == 1e10 даёт True. Надёжнее фиксированное число итераций: сотня делений пополам сужает разумный диапазон до точности double.

В примере верёвки длиной 8,02, 7,43, 4,57 и 5,39 режут на 11 одинаковых кусков максимальной длины, и программа печатает 2.005000. Инвариант здесь такой: lo всегда достижимо, hi считаем недостижимым, поэтому возвращаем lo. Итоговая сложность любого поиска по ответу — O(log(R / ε) · C), где R — ширина диапазона, ε — нужная точность (для целых — единица), C — стоимость проверки. Для задачи о грузе это O(n · log(sum(weights))).

import math

def max_piece(ropes, k, iters=100):
    """Максимальная длина L, при которой из верёвок получится k кусков длины L."""
    lo, hi = 0.0, max(ropes)            # инвариант: lo достижимо, hi — нет
    for _ in range(iters):
        mid = (lo + hi) / 2
        if sum(math.floor(r / mid) for r in ropes) >= k:
            lo = mid
        else:
            hi = mid
    return lo

print(f"{max_piece([8.02, 7.43, 4.57, 5.39], 11):.6f}")
print(math.ulp(1e10))     # шаг между соседними double около 1e10
print(1e10 + 1e-9 == 1e10)

• Python: math.ulp
• cp-algorithms: Binary search

Как отвечать на собеседовании и что повторить

Хороший ответ укладывается в четыре фразы до кода: что ищем (минимальное x, при котором выполняется условие), почему условие монотонно, какие границы и почему ответ внутри них, сколько стоит проверка. Если просят оценку, называйте обе части: число итераций — логарифм ширины диапазона, а не длины массива, плюс стоимость одной проверки.

Для повторения восстановите три задачи из статьи без подсказок: диапазон, предикат, проверку. Затем измените условие — например, найти наибольшую скорость, при которой ещё нельзя успеть, — и предскажите, какой шаблон понадобится. Ещё одно упражнение — переписать first_true на Go и сравнить с sort.Search: границы и инвариант должны совпасть. Формулировки и инварианты удобно держать в карточках RecallDeck с интервальными повторениями, а сам код лучше каждый раз писать заново.

• 53 вопроса по структурам данных и алгоритмам
• CodeRun и Яндекс Контест: как готовиться к алгоритмам
• Собеседование в Яндекс: алгоритмы и задачи
• Подготовка к backend-собеседованию

Коротко

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