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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;
}

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

Эти формулировки в условии ведут сюда:

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

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

• Бинарный поиск (массив) (Binary search (array)): Там отрезок состоит из реально лежащих данных. Здесь из всех значений, какими ответ может быть.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Сама проверка часто и есть жадный алгоритм. Поиск лишь выбирает, какого кандидата проверить.
• Линейный поиск (Linear search): Перебирать кандидатов подряд верно, но долго. Монотонная проверка позволяет отбросить половину.
• Динамическое программирование (1-D) (Dynamic programming (1-D)): DP собирает ответ из ответов поменьше. Здесь ответ угадывается и затем проверяется.

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

• Начинают диапазон с нуля

  Нижняя граница должна быть значением, которое в принципе может сработать. Для вместимости это самый большой предмет.

• Проверка не монотонна

  Если больший кандидат может провалиться после прошедшего меньшего, делить пополам нельзя. Сначала проверьте направление.

• Теряют последнего сработавшего кандидата

  Либо сохраните его в переменной, либо двигайте верх в mid, а не за него.

• Зацикливаются на дробном ответе

  На вещественных числах низ никогда не обгонит верх. Сделайте фиксированные сто раундов.

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

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

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

O(n log(range))

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