Что такое binary search по ответу?
На этой странице
Binary search по ответу - техника, где бинарный поиск идет не по индексу массива, а по диапазону возможных ответов. Она работает, если условие монотонное: до некоторой границы false, после нее true, или наоборот.
Вопрос
Что такое binary search по ответу и как узнать задачу на этот прием?
Обычный 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
^ ответ 4function 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:
| left | right | mid | Часов при скорости mid | can(mid) | Действие |
|---|---|---|---|---|---|
| 1 | 11 | 6 | 1 + 1 + 2 + 2 = 6 | true | right = 6 |
| 1 | 6 | 3 | 1 + 2 + 3 + 4 = 10 | false | left = 4 |
| 4 | 6 | 5 | 1 + 2 + 2 + 3 = 8 | true | right = 5 |
| 4 | 5 | 4 | 1 + 2 + 2 + 3 = 8 | true | right = 4 |
| 4 | 4 | - | - | - | 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)).