re:re:actable
Урок 074 минуты чтения

Что такое binary search по ответу?

На этой странице
Кратко

Binary search по ответу - техника, где бинарный поиск идет не по индексу массива, а по диапазону возможных ответов. Она работает, если условие монотонное: до некоторой границы false, после нее true, или наоборот.

Вопрос

Что такое binary search по ответу и как узнать задачу на этот прием?

Обычный binary search ищет элемент в отсортированном массиве:

function binarySearch(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
 
    if (nums[mid] === target) return mid
    if (nums[mid] < target) left = mid + 1
    else right = mid - 1
  }
 
  return -1
}

Binary search по answer space

Здесь мы ищем не элемент, а минимальное/максимальное значение, которое удовлетворяет условию.

Пример:

Можно ли выполнить задачу за X часов?

Если можно за X, то можно и за любое большее число. Это монотонность.

Шаблон для минимального valid answer

function binarySearchAnswer(left: number, right: number, can: (x: number) => boolean): number {
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
 
    if (can(mid)) {
      right = mid
    } else {
      left = mid + 1
    }
  }
 
  return left
}

Пример: минимальная скорость

Условие (задача Koko Eating Bananas): есть кучки бананов piles. За час можно съесть не больше speed бананов из одной кучки; если в кучке меньше, остаток часа пропадает. Нужно найти минимальную целую скорость speed, чтобы съесть все за hours часов.

Почему здесь работает binary search: если со скоростью speed успеваем, то с любой большей тоже успеем. Значит, все скорости делятся на "не успеваем" слева и "успеваем" справа, и нам нужна граница.

piles = [3, 6, 7, 11], hours = 8
speed:  1  2  3  4  5  6 ... 11
can:    F  F  F  T  T  T ... T
                 ^ ответ 4
function minEatingSpeed(piles: number[], hours: number): number {
  let left = 1
  let right = Math.max(...piles)
 
  function can(speed: number): boolean {
    let spent = 0
 
    for (const pile of piles) {
      spent += Math.ceil(pile / speed)
    }
 
    return spent <= hours
  }
 
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
 
    if (can(mid)) right = mid
    else left = mid + 1
  }
 
  return left
}

Трассировка для piles = [3, 6, 7, 11], hours = 8:

leftrightmidЧасов при скорости midcan(mid)Действие
11161 + 1 + 2 + 2 = 6trueright = 6
1631 + 2 + 3 + 4 = 10falseleft = 4
4651 + 2 + 2 + 3 = 8trueright = 5
4541 + 2 + 2 + 3 = 8trueright = 4
44---left === right, ответ 4

Почему right = mid, а не mid - 1? mid подходит и может оказаться самым маленьким подходящим, его нельзя выкидывать. А left = mid + 1, потому что неподходящий mid точно не ответ.

Перебор всех скоростей от 1 до max стоил бы O(max * n), а binary search - O(n log max).

Как узнать этот паттерн?

В условии часто есть слова:

  • minimum possible;
  • maximum possible;
  • capacity;
  • speed;
  • days;
  • split array;
  • can we do it with X;
  • answer is in numeric range.

Главный вопрос:

Если answer X подходит, что можно сказать про X + 1 или X - 1?

Что отвечать на собеседовании?

Binary search по ответу ищет границу в монотонном пространстве ответов. Мы не ищем элемент массива, а проверяем candidate answer через функцию can. Если can(mid) true, сдвигаем одну границу, если false - другую. Главное - доказать монотонность условия.

Что важно помнить: частые ошибки

  • Не доказать монотонность.
  • Ошибиться, ищем minimum valid или maximum valid.
  • Неправильно обновить left/right.
  • Получить бесконечный цикл.
  • Поставить слишком узкие начальные границы.
  • Сделать can дороже, чем нужно.

Мини-шпаргалка

  • Ищем ответ, не индекс.
  • Нужна монотонность.
  • can(x) проверяет candidate.
  • Minimum valid: true -> right = mid.
  • False -> left = mid + 1.
  • Complexity: O(log range * cost(can)).

Документация

cp-algorithms: Binary search.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам