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

Если проверка «подходит ли значение `x`» монотонна — `false … false true … true`, — то минимальный подходящий `x` находится бинарным поиском по диапазону ответов за `O(log(диапазон) · стоимость проверки)`.

Признаки задачи

• Просят минимизировать максимум или максимизировать минимум.
• Проверить конкретный ответ легко (жадно за O(n)), а найти оптимум напрямую — сложно.
• Примеры: минимальная грузоподъёмность, чтобы перевезти грузы за D дней; минимальная скорость поедания бананов; разбиение массива на k частей с минимальной наибольшей суммой; максимальное минимальное расстояние между k точками.

const minCapacity = (weights, days) => {
  const fits = (cap) => {
    let need = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { need++; load = 0; }
      load += w;
    }
    return need <= days;
  };

  let lo = Math.max(...weights), hi = weights.reduce((s, w) => s + w, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (fits(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
};

Сложность — O(n · log(sum)).

Типичные ошибки

• Немонотонный предикат — поиск молча вернёт мусор.
• Неверная нижняя граница: здесь lo обязан быть ≥ max(weights), иначе fits посчитает невозможное.
• lo = mid при mid = Math.floor((lo + hi) / 2) — бесконечный цикл.

Коротко для собеседования

Бинарный поиск по ответу подходит, когда найти оптимум трудно, а проверить конкретное значение легко и результат проверки монотонен. Типичный сигнал — «минимизировать максимум»; для вещественного ответа делайте фиксированные 60–100 итераций вместо сравнения с eps.