Binary Search on the Answer Space
I had to bin-pack 5M jobs across N machines under a wall-time budget; sort-and-greedy timed out. The fix was binary searching the makespan: a `feasible(m)` predicate plus the standard lo/hi loop turns an NP-hard scheduler into O(N log range).
By @rohaneriksson
January 12, 2026
·
Updated May 18, 2026
647 views
21
4.4 (13)
// Binary-search the smallest 'capacity' (makespan) such that we can pack all
// jobs into N machines without any one machine exceeding capacity.
// The trick: instead of searching for the right schedule, search for the
// answer (max load) and ask 'can we hit this?' as a yes/no predicate.
function minMakespan(jobs, machines) {
// The answer lies between max(job) (one job alone) and sum(jobs) (one machine).
let lo = 0;
let hi = 0;
for (const j of jobs) { if (j > lo) lo = j; hi += j; }
function feasible(capacity) {
let used = 1;
let load = 0;
for (const j of jobs) {
if (load + j <= capacity) {
load += j;
} else {
used += 1;
load = j;
if (used > machines) return false;
}
}
return true;
}
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
const jobs = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log('1 machine :', minMakespan(jobs, 1)); // 44
console.log('2 machines:', minMakespan(jobs, 2)); // 23
console.log('3 machines:', minMakespan(jobs, 3)); // 17
console.log('5 machines:', minMakespan(jobs, 5)); // 11
console.log('11 machines:', minMakespan(jobs, 11)); // 9 (one job per machine, biggest singleton is 9)The template is the reason this pattern is in my permanent toolkit. The outer loop is the standard lo < hi binary search; the only project-specific logic is feasible(capacity), which decides whether the candidate answer is achievable. For makespan the predicate is greedy first-fit: walk jobs in order, push onto the current machine if it fits, otherwise start a new one. Because feasible is monotonic (if m works, every m+1 also works), binary search converges in log(sum - max) iterations. The bounds are deliberate: lo starts at the largest single job (you can never go below it) and hi starts at the sum (one machine taking everything is always feasible).
// Koko-eats-bananas, the LeetCode that is the cleanest illustration of the
// pattern. Given piles[] and h hours, find the minimum k (bananas/hour) such
// that Koko finishes every pile within h hours, eating at most one pile per hour.
function minEatingSpeed(piles, hours) {
let lo = 1;
let hi = 0;
for (const p of piles) { if (p > hi) hi = p; }
function hoursAt(speed) {
let h = 0;
for (const p of piles) {
h += Math.ceil(p / speed);
}
return h;
}
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (hoursAt(mid) <= hours) hi = mid;
else lo = mid + 1;
}
return lo;
}
console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30
console.log(minEatingSpeed([30, 11, 23, 4, 20], 6)); // 23
// Why this is binary-search-on-the-answer rather than binary-search-on-an-array:
// the array of piles is unsorted and immutable; the search axis is the answer
// itself (speed in 1..max(pile)).
console.log('search axis: speed; predicate: hoursAt(speed) <= hours');Koko is the example I use to teach the pattern because the predicate is a one-liner and the bounds are obvious. The lower bound is 1 (you must eat something each hour), the upper bound is max(piles) (eating any faster is wasted, since you cannot start a new pile mid-hour). hoursAt(speed) sums the ceiling of each pile divided by speed, which is the cost function the problem hands you. The same shape solves capacity-of-ship-to-ship-packages, split-array-largest-sum, and aggressive-cows; once you can write the predicate, the binary search is mechanical.
// When the answer is real-valued, the loop becomes 'iterate enough times to
// hit the desired precision' instead of 'lo < hi'. Fixed iteration count is
// safer than a relative-epsilon termination because float math near the
// boundary can cycle.
function sqrtBinary(target, precision = 1e-9) {
if (target < 0) throw new Error('target must be >= 0');
let lo = 0;
let hi = target < 1 ? 1 : target;
// 64 iterations halves the range to 2^-64 of the original; way more than 1e-9.
for (let i = 0; i < 64; i++) {
const mid = (lo + hi) / 2;
if (mid * mid <= target) lo = mid;
else hi = mid;
if (hi - lo < precision) break;
}
return lo;
}
console.log('sqrt(2) =', sqrtBinary(2).toFixed(9)); // 1.414213561
console.log('sqrt(0.25)=', sqrtBinary(0.25).toFixed(9)); // 0.500000000
console.log('sqrt(1e6) =', sqrtBinary(1e6).toFixed(9)); // 999.999999999
// Same predicate (mid*mid <= target), same monotonicity, just continuous range.
console.log('Math.sqrt(2):', Math.sqrt(2));For continuous answer spaces I drop the integer-specific lo + 1 step and instead halve until the gap is below the requested precision. Capping at 64 iterations is a safety net: in pathological cases (denormals, near-zero targets) the relative epsilon never converges, and I would rather return an answer of bounded staleness than spin forever. Picking hi = target < 1 ? 1 : target covers the corner case where target = 0.25 and sqrt(target) > target. The same template handles minimize-distance-to-the-mean, minimize-max-distance-between-cows, and any other problem with a real-valued, monotonic predicate.