Searching
Binary Search on the Answer
Written by Swapnil RajaPublished
Binary search is not really about arrays. It is about any question where, once something becomes true, it stays true - and that covers far more problems than sorted lists.
The pattern
Some problems ask for a minimum or maximum value satisfying a condition. If you can write a function canDo(x) that answers yes or no, and that function is monotonic - false, false, false, then true forever - you can binary search over the answer range instead of over data.
The search space is now a range of numbers you never build. You only need its lower and upper bounds.
Minimum speed to finish in time
javascript
// Piles of bananas; eat at speed s per hour; one pile per hour maximum.
// Find the smallest speed that finishes within h hours.
function minEatingSpeed(piles, hours) {
const hoursNeeded = (speed) =>
piles.reduce((total, pile) => total + Math.ceil(pile / speed), 0)
let low = 1
let high = Math.max(...piles)
while (low < high) {
const mid = (low + high) >>> 1
if (hoursNeeded(mid) <= hours) {
high = mid // fast enough — try slower
} else {
low = mid + 1 // too slow
}
}
return low
}
console.log(minEatingSpeed([3, 6, 7, 11], 8)) // 4