Binary Search on the Answer

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.

// 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

Faster is always at least as good, so hoursNeeded decreases as speed rises - that is the monotonicity. The loop then narrows to the boundary where the answer flips.

Getting the loop right

Off-by-one errors are the main hazard. Two habits remove most of them: use while (low < high) with no -1 on the true branch when searching for a minimum, and compute the midpoint with (low + high) >>> 1 so it cannot overflow or drift negative.

• Searching for a minimum true - on true set high = mid, on false set low = mid + 1.
• Searching for a maximum true - bias the midpoint upward with (low + high + 1) >>> 1, then on true set low = mid.
• Terminate with low === high and return either.

Recognising it

The giveaway is a question of the form "the smallest capacity / largest minimum / minimum time such that…" together with a cheap way to test a candidate. If checking one candidate is O(n) and the range is a million wide, the whole search is only about twenty checks - roughly O(n log range).