Алгоритмы с нуля

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

Суть Бинарный поиск работает не только для поиска значения в отсортированном массиве — он работает на любом отсортированном пространстве. Ищи по возможным ответам, когда ты можешь спросить «этот ответ выполнимый?» и ответ монотонный: ложь, ложь, …, ложь, потом истина, истина, …

◷ 20 min

Ты выучил бинарный поиск для поиска значения в отсортированном массиве — индекс, где живёт цель. Но бинарный поиск более универсален: это способ найти лучший ответ в отсортированном пространстве возможных ответов. Представь задачу: «Какая минимальная скорость, при которой я могу закончить задачу?» или «Какая самая маленькая грузоподъёмность контейнера позволит мне доставить все пакеты вовремя?» Это не индексы массива. Это значения в диапазоне. Трюк в том, что выполнимость ответа монотонна — если один ответ работает, все большие ответы тоже работают. Эта монотонная свойство — то, что использует бинарный поиск. Вместо слепого угадывания или проверки каждого возможного ответа один за раз (O(n)), бинарный поиск сужает диапазон ответов вдвое на каждом шаге: O(log(диапазон)).

Цель

После этого урока ты разбираешься в бинарном поиске по ответу: что это значит (поиск в диапазоне возможных ответов вместо индексов массива), предусловие (монотонный предикат: тест да/нет, который переходит от ложи к истине ровно один раз при увеличении ответа), метод (ищи диапазон ответов; на каждом шаге проверь, выполним ли кандидат), почему это работает (монотонное свойство гарантирует, что если ответ x работает, все большие ответы работают; если x не работает, все меньшие ответы не работают), классический пример (минимальная грузоподъёмность или скорость еды), и как распознать, когда это использовать (задача просит минимальное или максимальное значение, выполнимость проверяется, и ответ монотонный).

Идея

Что такое «бинарный поиск по ответу»?

В классическом бинарном поиске ты ищешь индекс в отсортированном массиве: [1, 3, 5, 7, 9]. Но иногда задача не «найди индекс» — это «найди значение, которое удовлетворяет условию».

Пример: «Какова минимальная грузоподъёмность корабля (в кг), чтобы я мог доставить все пакеты за 5 дней?»

Ответ — не индекс массива. Это значение в диапазоне [вес_самого_тяжёлого_пакета, сумма_всех_весов]. Например, [10 кг, 100 кг]. У тебя нет явного отсортированного массива для поиска. Вместо этого ты ищешь пространство возможных ответов. Если грузоподъёмность 40 кг позволяет доставить за 5 дней, позволяет ли 41 кг? Да, всегда. Если 39 кг не позволяет, позволяет ли 38 кг? Нет, никогда. Это монотонное свойство.

Предусловие: монотонный предикат

Для работы бинарного поиска по ответу нужен монотонный предикат выполнимо(x):

Функция, что возвращает истину или ложь.
При увеличении x результат изменяется с ложи на истину не более раза. Пример: ложь, ложь, ложь, ложь, истина, истина, истина.
Как только переключается на истину, остаётся истиной (или: как только переключается на ложь, остаётся ложью).

Пример: выполнимо(грузоподъёмность) = «Могу ли я доставить все пакеты за 5 дней с этой грузоподъёмностью?» При увеличении грузоподъёмности ответ остаётся ложью до порога, потом остаётся истиной.

Почему монотонность важна

Если предикат монотонный, ты можешь выполнить бинарный поиск в пространстве ответов. Если не монотонный (например, иногда истина, иногда ложь, иногда истина снова), бинарный поиск не работает, потому что левая и правая половины не дают тебе информацию.

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

Определи диапазон поиска. Установи lo и hi как минимальный и максимальный возможные ответы.
- Пример: lo = max_пакета (самый тяжёлый пакет должен влезть), hi = сумма_всех_пакетов (худший случай: всё сразу).
Бинарный поиск в диапазоне.
- Вычисли mid = lo + (hi - lo) / 2.
- Проверь, верна ли выполнимо(mid).
- Если верна: ответ mid или меньше. Установи hi = mid (или hi = mid - 1, чтобы найти точную границу).
- Если не верна: ответ больше. Установи lo = mid + 1.
- Повторяй, пока lo == hi (самое маленькое значение, для которого выполнимо верна).

Рабочий пример: минимальная грузоподъёмность

У тебя есть пакеты с весами [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], и ты должен доставить их все за D = 5 дней. Пакеты загружаются по порядку; ты не можешь их переставлять. Какова минимальная грузоподъёмность?

Определи выполнимо(грузоподъёмность):

function canShipInDays(weights, capacity, days) {
  let currentDayWeight = 0;
  let daysNeeded = 1;
  
  for (const weight of weights) {
    if (currentDayWeight + weight > capacity) {
      // Текущий пакет не влезает; начни новый день
      daysNeeded++;
      currentDayWeight = weight;
    } else {
      currentDayWeight += weight;
    }
  }
  
  return daysNeeded <= days;
}

Бинарный поиск:

lo = 10 (самый тяжёлый пакет).
hi = 55 (сумма всех весов).

Шаг 1: mid = 32. Можем ли доставить за 5 дней с грузоподъёмностью 32?

День 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Не влезает 8 (28 + 8 = 36 > 32).
День 2: 8 + 9 = 17. Влезает 10 (17 + 10 = 27 ≤ 32).
День 2: 8 + 9 + 10 = 27. Готово.
Всего: 2 дня ≤ 5 дней. Выполнимо. Установи hi = 32.

Шаг 2: mid = 21. Можем ли доставить за 5 дней с грузоподъёмностью 21?

День 1: 1 + 2 + 3 + 4 + 5 + 6 = 21. Не влезает 7.
День 2: 7 + 8 = 15. Не влезает 9 (15 + 9 = 24 > 21).
День 3: 9 + 10 = 19. Готово.
Всего: 3 дня ≤ 5 дней. Выполнимо. Установи hi = 21.

Шаг 3: mid = 15. Можем ли доставить за 5 дней с грузоподъёмностью 15?

День 1: 1 + 2 + 3 + 4 + 5 = 15. Не влезает 6.
День 2: 6 + 7 = 13. Не влезает 8.
День 3: 8. День 4: 9. День 5: 10. Всего: 5 дней. Выполнимо. Установи hi = 15.

Шаг 4: mid = 12. Можем ли доставить за 5 дней с грузоподъёмностью 12?

День 1: 1 + 2 + 3 + 4 = 10. Не влезает 5.
День 2: 5 + 6 = 11. Не влезает 7.
День 3: 7. День 4: 8. День 5: 9. День 6: 10.
Всего: 6 дней > 5 дней. Не выполнимо. Установи lo = 13.

Шаг 5: mid = 14. Можем ли доставить за 5 дней с грузоподъёмностью 14?

День 1: 1 + 2 + 3 + 4 = 10. Не влезает 5.
День 2: 5 + 6 = 11. Не влезает 7.
День 3: 7. День 4: 8. День 5: 9. День 6: 10.
Всего: 6 дней > 5 дней. Не выполнимо. Установи lo = 15.

Шаг 6: lo = 15, hi = 15. Ответ: 15.

Минимальная грузоподъёмность корабля — 15 кг.

Код

Напишем бинарный поиск по ответу. Используем пример с грузоподъёмностью.

function canShipInDays(weights, capacity, days) {
  let currentDayWeight = 0;
  let daysNeeded = 1;

  for (const weight of weights) {
    if (currentDayWeight + weight > capacity) {
      // Начни новый день
      daysNeeded++;
      currentDayWeight = weight;
      
      // Проверка здравомыслия: ни один пакет не превышает грузоподъёмность
      if (weight > capacity) return false;
    } else {
      currentDayWeight += weight;
    }
  }

  return daysNeeded <= days;
}

function minShipCapacity(weights, days) {
  // Бинарный поиск в диапазоне грузоподъёмности
  let lo = Math.max(...weights);  // По крайней мере самый тяжёлый пакет
  let hi = weights.reduce((a, b) => a + b, 0);  // По крайней мере сумма всех

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    
    if (canShipInDays(weights, mid, days)) {
      // mid работает; попробуй меньше
      hi = mid;
    } else {
      // mid не работает; попробуй больше
      lo = mid + 1;
    }
  }

  return lo;  // lo == hi; минимальная выполнимая грузоподъёмность
}

Ключевые идеи:

canShipInDays — проверка выполнимости. Она моделирует доставку и считает дни.
Условие цикла lo < hi сужает, пока не сойдутся.
Если выполнимо(mid) верна, мы устанавливаем hi = mid (может быть меньше). Если не верна, мы устанавливаем lo = mid + 1 (нужно больше).
Ответ — lo при выходе из цикла.

Протестируем:

function canShipInDays(weights, capacity, days) {
let currentDayWeight = 0;
let daysNeeded = 1;

for (const weight of weights) {
  if (currentDayWeight + weight > capacity) {
    daysNeeded++;
    currentDayWeight = weight;
    if (weight > capacity) return false;
  } else {
    currentDayWeight += weight;
  }
}

return daysNeeded <= days;
}

function minShipCapacity(weights, days) {
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b, 0);

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

return lo;
}

// Тест 1
const weights1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const days1 = 5;
console.log("Веса:", weights1);
console.log("Дни:", days1);
console.log("Мин. грузоподъёмность:", minShipCapacity(weights1, days1), "(ожидается 15)");

// Проверка: можем ли доставить с грузоподъёмностью 15 за 5 дней?
console.log("Можем доставить с грузоподъёмностью 15?", canShipInDays(weights1, 15, days1));

// Тест 2
const weights2 = [3, 2, 2, 4, 1, 4];
const days2 = 3;
console.log("\nВеса:", weights2);
console.log("Дни:", days2);
console.log("Мин. грузоподъёмность:", minShipCapacity(weights2, days2), "(ожидается 6)");
console.log("Можем доставить с грузоподъёмностью 6?", canShipInDays(weights2, 6, days2));

// Тест 3: один день
const weights3 = [1, 2, 3];
const days3 = 1;
console.log("\nВеса:", weights3);
console.log("Дни:", days3);
console.log("Мин. грузоподъёмность:", minShipCapacity(weights3, days3), "(ожидается 6)");
console.log("Можем доставить с грузоподъёмностью 6?", canShipInDays(weights3, 6, days3));

Вывод

Пошаговый разбор

Трассируем бинарный поиск в пространстве ответов для weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5.


      1
      lo = max(weights) = 10
    

      2
      hi = sum(weights) = 55
    

      3
      while (lo < hi) {
    

      4
        mid = lo + floor((hi - lo) / 2)
    

      5
        if (canShipInDays(..., mid, 5)) hi = mid
    

      6
        else lo = mid + 1
    

      7
      }

Разбор:

Мы начинаем с огромного диапазона [10, 55].
На каждой итерации мы проверяем кандидата ответа и сужаем диапазон вдвое.
После ~3 шагов мы сужаем с 45 кандидатов до нескольких.
После ~6 шагов мы находим точный ответ.

Диапазон ответов такой же, как данные: сумма весов не более 55. Поэтому log₂(55) ≈ 6 шагов.

Сложность

Аспект	Значение
Время: цикл бинарного поиска	O(log(hi - lo))
Время: каждая проверка выполнимости	O(n) (сканирование всех весов)
Полное время	O(n · log(hi - lo))
Память	O(1)

Почему O(n · log(hi - lo))?

Цикл бинарного поиска выполняется O(log(hi - lo)) раз, где hi - lo — диапазон возможных ответов. Для задачи о грузоподъёмности это O(log(сумма_весов)). На каждой итерации мы вызываем canShipInDays, что сканирует все n весов: O(n). Всего: O(n · log(сумма)).

Для примера [1, 2, …, 10] диапазон — [10, 55]. log₂(55) ≈ 6. Так что 6 итераций × 10 весов = 60 операций. Намного лучше, чем проверять все 45 возможных грузоподъёмностей одну за раз (что было бы 45 × 10 = 450 операций).

Сравнение с грубой силой:

Грубая сила: проверим грузоподъёмность 10, 11, 12, …, 55. Это O(сумма) проверок выполнимости = O(n · сумма) время.
Бинарный поиск: O(log(сумма)) проверок выполнимости = O(n · log(сумма)) время.

Для суммы = 1 000 000, log₂(1 000 000) ≈ 20. Грубая сила: 1 000 000 × n операций. Бинарный поиск: 20 × n операций. Ускорение в 50 000 раз.

Память: O(1)

Алгоритм использует только несколько переменных (lo, hi, mid). Проверка выполнимости сканирует веса, но не хранит дополнительные данные.

Практика 0 / 5

Почему бинарный поиск по ответу требует монотонный предикат?

Для задачи о грузоподъёмности, почему lo установлено на max(weights)?

Для задачи о грузоподъёмности, почему hi установлено на sum(weights)?

Веса [1, 2, 3], дни = 2. Какова минимальная грузоподъёмность? (Подсказка: День 1: [1, 2], День 2: [3].)

Что означает условие цикла `lo < hi` в бинарном поиске по ответу?

lesson.inset.leap

От индексов к пространствам ответов. Бинарный поиск не ограничен индексами массива. Ключевая идея в том, что ты можешь выполнить бинарный поиск в любом отсортированном пространстве — пока ты можешь монотонно тестировать выполнимость. Индексы — это просто простой случай. Но пространства ответов (грузоподъёмности, скорости, расстояния, количество монет) одинаково действительны. Как только ты интернализуешь этот скачок, ты будешь распознавать возможности бинарного поиска во многих задачах «найди минимум/максимум значение такое что…».

Частая ошибка

Спутанное условие цикла. Частая ошибка — использовать lo <= hi (подходит для бинарного поиска по массиву) вместо lo < hi (подходит здесь). При поиске в пространствах ответов используй lo < hi, потому что lo == hi означает, что ответ пойман. Не проверяй его дважды.

Проверь себя

Викторина

У тебя есть веса [1, 2, 3, 4, 5], дни = 3, и нужно найти минимальную грузоподъёмность. Какой ответ?

Итог

Бинарный поиск по ответу — это способ найти оптимальное значение в отсортированном пространстве ответов, не отсортированном массиве.

Предусловие: Монотонный предикат — тест да/нет, что переходит с ложи на истину (или истину на ложь) ровно один раз при увеличении ответа.

Метод: Бинарный поиск в диапазоне ответов [lo, hi]. На каждом шаге проверь, выполним ли кандидат ответа. Если да и ты хочешь минимум, попробуй меньше (hi = mid). Если нет, попробуй больше (lo = mid + 1). Когда lo == hi, ты нашёл ответ.

Классический пример: Минимальная грузоподъёмность. Дано: пакеты и срок (дни), найди самую маленькую грузоподъёмность, чтобы все пакеты могли доставиться в сроке. Проверка выполнимости O(n) (моделирование доставки). Бинарный поиск в диапазоне грузоподъёмности: O(log(сумма_весов)). Всего: O(n · log(сумма)).

Почему это важно? Много задач на «найди минимум/максимум такой что…» сводятся к бинарному поиску по ответу, как только ты распознаешь монотонный предикат. Это меняет линейный или экспоненциальный поиск на логарифмический.

Ошибки:

Проверь, что предикат действительно монотонный. Если нет, бинарный поиск не работает.
Правильно установи lo и hi: lo должно быть выполнимой нижней границей, hi — верхней границей.
Используй lo < hi (не lo <= hi) при поиске в пространствах ответов.

Распознавание: Когда видишь «найди минимум/максимум значение такое что условие C выполняется», и проверка C быстра и монотонна, бинарный поиск по ответу — твой инструмент.

Продолжить восхождение ↑Сортировка и поиск: тест с выбором