Бинарный поиск по ответу: как решать задачи на минимум и максимум

Коротко

Обычный бинарный поиск ищет элемент в отсортированном массиве. Бинарный поиск по ответу ищет само значение ответа в диапазоне возможных значений — даже если никакого массива нет.

Приём превращает задачи вида «найдите минимальное X, при котором всё получится» из перебора за O(n) в поиск за O(log n · стоимость проверки).

Когда это работает

Условие ровно одно: ответ должен обладать свойством монотонности. Если значение X подходит, то все значения больше X тоже подходят (или наоборот — все меньшие).

Нарисуем это:

значение:  1    2    3    4    5    6    7    8
подходит:  нет  нет  нет  ДА   ДА   ДА   ДА   ДА
                        ↑
                   ищем эту границу

Если картинка выглядит так — бинарный поиск применим. Если «подходит» разбросано вперемешку, приём не сработает.

Проверить монотонность — первое, что нужно сделать. Формулировка вслух: «если я справлюсь за X минут, справлюсь ли я за X+1?» Если ответ очевидное «да», монотонность есть.

Универсальный шаблон

Вместо поиска точного значения ищем границу между "нет" и "да".

def binary_search_answer(low: int, high: int, check) -> int:
    """Находит минимальное значение в [low, high], для которого check() истинно."""
    while low < high:
        mid = (low + high) // 2

        if check(mid):
            high = mid       # mid подходит, но, может, есть меньше
        else:
            low = mid + 1    # mid не подходит, ответ строго правее

    return low

Три детали, которые делают этот шаблон надёжным.

Условие low < high, а не low <= high. Цикл заканчивается, когда границы сошлись, и low — это и есть ответ. Не нужно отдельной переменной для запоминания результата.

При успехе high = mid, а не mid - 1. Значение mid подходит и остаётся кандидатом — выбрасывать его нельзя.

При неудаче low = mid + 1. Здесь mid точно не подходит, поэтому смело исключаем.

Такая комбинация гарантирует, что цикл всегда завершится: диапазон уменьшается на каждом шаге.

Задача 1: минимальная скорость

Классика. Есть n куч бананов, обезьяна ест со скоростью k бананов в час — за час она съедает k бананов из одной кучи, и если куча меньше, остаток часа простаивает. Найти минимальную скорость, при которой она успеет съесть всё за h часов.

Перебирать скорость от 1 до максимума — до 10⁹ итераций. А монотонность очевидна: если успевает при скорости k, то при k+1 тем более.

import math


def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        # на каждую кучу уходит ceil(размер / скорость) часов
        return sum(math.ceil(pile / speed) for pile in piles)

    low, high = 1, max(piles)

    while low < high:
        mid = (low + high) // 2
        if hours_needed(mid) <= h:
            high = mid       # успеваем, пробуем медленнее
        else:
            low = mid + 1    # не успеваем, надо быстрее

    return low


print(min_eating_speed([3, 6, 7, 11], 8))       # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5)) # 30

Сложность — O(n log(max)). Вместо миллиарда итераций около тридцати, и в каждой линейная проверка.

Границы поиска выбираются так: минимум — 1 (медленнее нельзя), максимум — самая большая куча (быстрее бессмысленно, за час и так съедается целая куча).

Задача 2: разделить массив на k частей

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

Здесь ответ — не элемент массива, а некоторое число. Ищем его.

def split_array(nums: list[int], k: int) -> int:
    def can_split(limit: int) -> bool:
        """Хватит ли k частей, если сумма каждой не больше limit?"""
        parts = 1
        current = 0

        for num in nums:
            if current + num > limit:
                parts += 1
                current = num
                if parts > k:
                    return False
            else:
                current += num

        return True

    # минимум: хотя бы один элемент должен влезть
    # максимум: одна часть на весь массив
    low, high = max(nums), sum(nums)

    while low < high:
        mid = (low + high) // 2
        if can_split(mid):
            high = mid
        else:
            low = mid + 1

    return low


print(split_array([7, 2, 5, 10, 8], 2))  # 18

Монотонность: чем больше разрешённый лимит, тем меньше частей нужно. Если при лимите X уложились в k частей, при большем лимите тем более уложимся.

Обратите внимание на нижнюю границу: max(nums), а не 0 или 1. Лимит меньше самого большого элемента невозможен — этот элемент никуда не влезет.

Задача 3: вещественный ответ

Иногда ответ не целое число. Тогда вместо схождения границ делают фиксированное число итераций.

def sqrt_binary(x: float, precision: float = 1e-9) -> float:
    low, high = 0.0, max(x, 1.0)

    # 100 итераций уменьшают отрезок в 2^100 раз — с запасом
    for _ in range(100):
        mid = (low + high) / 2
        if mid * mid < x:
            low = mid
        else:
            high = mid

    return low


print(round(sqrt_binary(2), 6))  # 1.414214

Почему фиксированное число итераций, а не условие high - low > precision: с вещественными числами такое условие может не выполниться никогда из-за ошибок округления, и цикл зависнет. Сто итераций гарантированно дают точность, недостижимую для float.

Как распознать задачу

Маркеры в условии:

• «найдите минимальное X, при котором…»;
• «найдите максимальное X, при котором…»;
• «минимизируйте максимум» или «максимизируйте минимум»;
• ответ — число из большого диапазона, а прямой перебор слишком медленный;
• есть быстрая проверка «а подходит ли конкретное значение X».

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

Алгоритм действий

1. Понять, что именно является ответом, и в каком диапазоне он лежит.
2. Написать функцию check(x) — подходит ли значение x.
3. Убедиться в монотонности: проговорить «если x подходит, подходит ли x+1».
4. Аккуратно выбрать границы low и high.
5. Применить шаблон.

Самый частый провал — на третьем шаге. Если монотонности нет, код всё равно что-то вернёт, но это будет неверный ответ, и найти ошибку будет тяжело.

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

Неправильные границы. Если истинный ответ вне отрезка [low, high], поиск вернёт границу, а не решение. Всегда берите заведомо достаточный диапазон — лишние итерации почти ничего не стоят, их логарифм.

Условие low <= high вместе с high = mid. Приведёт к бесконечному циклу: при low == high значение mid совпадёт с ними, и границы перестанут двигаться.

high = mid - 1 при успешной проверке. Выбрасывает корректный ответ. Классический симптом — результат всегда на единицу меньше правильного.

Переполнение при (low + high) // 2. В Python не проблема, целые числа неограниченные. В C++ или Java для больших значений нужно low + (high - low) // 2.

Проверка монотонности «на глаз». Проверяйте рассуждением, а не интуицией. Особенно в задачах, где условие содержит несколько ограничений сразу.

Что запомнить

• Ищем не элемент, а значение ответа в диапазоне возможных значений.
• Обязательное условие — монотонность: подходит X, значит подходит и всё, что больше.
• Шаблон: while low < high, при успехе high = mid, при неудаче low = mid + 1.
• Сложность O(log(диапазон) × стоимость проверки).
• Для вещественного ответа делайте фиксированные 100 итераций вместо сравнения с точностью.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→