jsschools

Binary Search on Answer

Applies binary search to the answer space (not an array index) by formulating the problem as finding the smallest/largest value satisfying a monotone predicate.

Spec ↗

Syntax

binaryOnAnswer(lo, hi, feasible)

Parameters

NameTypeRequiredDescription
lo number Yes Lower bound of the answer space (inclusive).
hi number Yes Upper bound of the answer space (inclusive).
feasible (mid: number) => boolean Yes A monotone predicate: returns true for all valid answers above (or below) the optimal point. Must be computable in O(f(n)) time.

Returns

number — The smallest value in [lo, hi] for which feasible returns true.

Examples

// Classic: find the minimum capacity to ship packages within D days
function shipWithinDays(weights, days) {
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);

  const canShip = (cap) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d <= days;
  };

  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (canShip(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));
Output 
15

// Find square root via binary search on answer
function sqrtFloor(n) {
  if (n < 2) return n;
  let lo = 1, hi = Math.floor(n / 2);
  while (lo < hi) {
    const mid = (lo + hi + 1) >>> 1; // upper-mid to avoid infinite loop
    if (mid * mid <= n) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

console.log(sqrtFloor(16));
console.log(sqrtFloor(17));
Output 
4
4

Notes

| Case | Time | Space | |---------|-----------------|-------| | Best | O(log k · f(n)) | O(1) | | Average | O(log k · f(n)) | O(1) | | Worst | O(log k · f(n)) | O(1) | where k = hi - lo (the answer range) and f(n) = cost of `feasible`. The predicate must be **monotone**: once it becomes true it stays true (or vice versa). Choose lo/hi carefully to avoid off-by-one errors. Use the upper-mid trick `(lo + hi + 1) >>> 1` when searching for the largest valid value to prevent infinite loops. Common applications: capacity/rate problems, kth-smallest-in-matrix, and sqrt/pow inverses.

See also