---
title: "Бинарный поиск по ответу"
url: https://algopath.pro/ru/patterns/binary-search-on-answer
language: ru
summary: "Искать здесь надо не в данных, а в диапазоне возможных ответов. Проверка да или нет говорит, какую половину можно выбросить."
updated: 2026-08-24
---

# Бинарный поиск по ответу

Искать здесь надо не в данных, а в диапазоне возможных ответов. Проверка да или нет говорит, какую половину можно выбросить.

## Бинарный поиск по ответу: как это работает?

Назовите наименьшее и наибольшее значение, каким ответ может быть. Эта пара и есть диапазон поиска.

Напишите проверку, работает ли один кандидат. Она отвечает только да или нет.

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

Возьмите среднего кандидата и запустите проверку. Это значение, а не индекс.

При ответе да запомните его и ищите в меньшей половине. При ответе нет ищите в большей.

Диапазон делится пополам каждый раунд. Тридцать раундов покрывают миллиард кандидатов.

- `диапазон = от 1 до 11` Съесть кучи [3, 6, 7, 11] за 8 часов. Ответ это скорость.
- `скорость 6 даёт 6 часов` Шесть часов укладываются в лимит. Меньшая скорость может тоже подойти.
- `диапазон = от 1 до 5` Скорость 6 сохранена как лучшая. Теперь пробуем нижнюю половину.
- `скорость 3 даёт 10 часов` Это больше лимита. Всё ниже 3 ещё хуже.
- `скорость 4 даёт 8 часов` Ровно в лимит, а меньшее не проходит. Ответ равен 4.

## Бинарный поиск по ответу: когда применять?

- минимизировать максимум / максимизировать минимум
- наименьшее значение, удовлетворяющее условию
- найти наименьшую вместимость/скорость/число дней, которое подходит
- ответ лежит в числовом диапазоне, а не в позиции массива
- проверка выполнимости монотонна (становится true после некоторой точки)

## Бинарный поиск по ответу: с чем путают?

- **Бинарный поиск (массив)** - Там отрезок состоит из реально лежащих данных. Здесь из всех значений, какими ответ может быть.
- **Жадный алгоритм (обменный аргумент)** - Сама проверка часто и есть жадный алгоритм. Поиск лишь выбирает, какого кандидата проверить.
- **Линейный поиск** - Перебирать кандидатов подряд верно, но долго. Монотонная проверка позволяет отбросить половину.
- **Динамическое программирование (1-D)** - DP собирает ответ из ответов поменьше. Здесь ответ угадывается и затем проверяется.

## Бинарный поиск по ответу: сложность по времени и памяти

Диапазон в 1e9 требует около 30 проверок. Итог O(n log range), если одна проверка стоит O(n).

## Бинарный поиск по ответу: разбор примера

### Отгрузить все посылки за d дней

Посылки отгружаются в заданном порядке за d дней. Выберите наименьшую дневную вместимость, при которой всё успевает.

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

Ответ лежит между самой большой посылкой и суммой всех.

Для одного кандидата заполняйте дни жадно и считайте дни. Сравните это число с d.

```javascript
function shipWithinDays(weights, days) {
    let lo = Math.max(...weights);              // one day must hold the biggest package
    let hi = weights.reduce((a, b) => a + b, 0); // one day holds everything

    const fits = (capacity) => {
        let used = 1;
        let load = 0;

        for (const w of weights) {
            if (load + w > capacity) {
                used++;   // start a new day
                load = 0;
            }
            load += w;
        }

        return used <= days;
    };

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (fits(mid)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}
```

## Бинарный поиск по ответу: частые ошибки

- **Начинают диапазон с нуля** Нижняя граница должна быть значением, которое в принципе может сработать. Для вместимости это самый большой предмет.
- **Проверка не монотонна** Если больший кандидат может провалиться после прошедшего меньшего, делить пополам нельзя. Сначала проверьте направление.
- **Теряют последнего сработавшего кандидата** Либо сохраните его в переменной, либо двигайте верх в mid, а не за него.
- **Зацикливаются на дробном ответе** На вещественных числах низ никогда не обгонит верх. Сделайте фиксированные сто раундов.

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

- **Коко ест бананы** Кандидат это скорость, проверка считает часы.
- **Вместимость для отгрузки за D дней** Кандидат это дневная загрузка.
- **Разбить массив с минимальной большой суммой** Кандидат это предел суммы одной части.
- **Минимум дней для m букетов** Кандидат это день, проверка считает готовые букеты.
- **Магнитная сила между шарами** Здесь максимизируют минимальный зазор, а не наоборот.
- **Наименьший делитель при пороге** Кандидат это сам делитель.
- **Минимизировать расстояние между заправками** Ответ дробный, поэтому цикл делает фиксированное число шагов.

## JavaScript

```javascript
function smallestFeasible(lo, hi, canDo) {
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// canDo(x) must be monotonic: false...false, true...true
```

## Python

```python
def smallest_feasible(lo, hi, can_do):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_do(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
# can_do(x) must be monotonic: False...False, True...True
```

## PHP

```php
function smallestFeasible(int $lo, int $hi, callable $canDo): int {
    while ($lo < $hi) {
        $mid = $lo + intdiv($hi - $lo, 2);
        if ($canDo($mid)) $hi = $mid;
        else $lo = $mid + 1;
    }
    return $lo;
}
// canDo($x) must be monotonic: false...false, true...true
```