Binary search on the answer

The problem: how big a truck?

A distribution company must move a warehouse's backlog of parcels to a hub within 5 days. The parcels sit on a conveyor in a fixed order and must be loaded in that order (the ones at the front block the rest). Each day the truck takes parcels from the front of the line until the next one would exceed its capacity, then drives to the hub. Trucks are rented by capacity, in kilograms, and bigger ones cost more. The operations manager asks: "What is the smallest capacity that ships everything within 5 days?"

This does not look like searching. There is no sorted array and no target value to find. Yet binary search, which you wrote in Linear and binary search, is exactly the tool, once you see what is being searched: not the parcels, but the possible answers.

A naive solution: try every capacity

With a check in hand, the first working solution tries capacities from the smallest possible upwards and stops at the first one that works:

function daysNeeded(weights, capacity) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    if (load + w > capacity) {  // this parcel starts the next day
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

function minCapacityNaive(weights, maxDays) {
  let capacity = Math.max(...weights);
  while (daysNeeded(weights, capacity) > maxDays) capacity++;
  return capacity;
}

const parcels = [30, 25, 40, 10, 35, 20, 45, 15, 30, 25]; // kg, in conveyor order
console.log(minCapacityNaive(parcels, 5), daysNeeded(parcels, 60), daysNeeded(parcels, 59));
console.log(minCapacityNaive(parcels, 1), minCapacityNaive(parcels, 10));

60 5 6
275 45

It works: 60 kg is the smallest capacity that ships these ten parcels in 5 days, and 59 kg needs 6. With one day allowed the answer is the total, and with ten days (one parcel a day) it is the heaviest parcel, exactly the two ends from the reason block.

What is wrong with it: count the operations

The real backlog is thousands of parcels, and the number of candidate capacities grows with the total weight. Count how many parcels the naive search simulates loading, over all the capacities it tries:

function daysNeeded(weights, capacity, counter) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    counter.loads++;
    if (load + w > capacity) {
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

function minCapacityNaive(weights, maxDays, counter) {
  let capacity = Math.max(...weights);
  counter.checks++;
  while (daysNeeded(weights, capacity, counter) > maxDays) {
    capacity++;
    counter.checks++;
  }
  return capacity;
}

for (const n of [100, 1000, 10000]) {
  const weights = Array.from({ length: n }, (_, i) => 1 + ((i * 37) % 50)); // 1 to 50 kg
  const counter = { checks: 0, loads: 0 };
  const capacity = minCapacityNaive(weights, 5, counter);
  console.log(`n=${String(n).padEnd(6)} capacity=${String(capacity).padEnd(6)} checks=${String(counter.checks).padEnd(6)} parcel loads=${counter.loads}`);
}

n=100    capacity=524    checks=475    parcel loads=47500
n=1000   capacity=5100   checks=5051   parcel loads=5051000
n=10000  capacity=51000  checks=50951  parcel loads=509510000

The number of checks grows with the answer (roughly total weight / days), and each check walks all n parcels. Both grow with n, so the work grows like n²: 10,000 parcels already cost about half a billion simulated loads. The waste is that each failed check teaches you more than "not this capacity": it teaches you "not this one, and not any smaller one". Stepping up by 1 kg throws that away.

The pattern: find where false turns into true

Write the check's answer for every capacity in order and you get a very particular shape:

capacity:   45    50    55    59    60    61    65    70   ...  275
days:        8     8     6     6     5     5     5     5   ...    1
works?      no    no    no    no    YES   YES   YES   YES  ...  YES
                                   ^
                        the first yes is the answer

A yes/no function whose answers, over an ordered range, go false, false, …, false, true, true, …, true and switch exactly once is called a monotonic predicate ("predicate" means a function that returns true or false; "monotonic" means it only ever changes in one direction). Binary search does not need a sorted array. It needs exactly this: a range where one test at the middle tells you which half the switch point is in.

• If the middle is true, the first true is the middle or somewhere to its left.
• If the middle is false, the first true is somewhere to its right.

Every problem in this lesson is solved by one small function, firstTrue(lo, hi, test): the smallest number in lo to hi for which test is true. It uses the half-open style of lowerBound in Linear and binary search, with hi one past the last candidate, and returns hi itself if no candidate passes:

export function firstTrue(lo, hi, test, counter = { checks: 0 }) {
  // Invariant: every number below lo is false; every number from hi on is true (or past the end).
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    counter.checks++;
    if (test(mid)) hi = mid;     // mid is true: the first true is mid or before it
    else lo = mid + 1;           // mid is false: the first true is after it
  }
  return lo;                     // lo === hi: the first true, or the original hi if none
}

The invariant is what makes it correct. At the start nothing is known, so it holds trivially: there is nothing below lo in the range and nothing from hi on. Each step keeps it: a true middle becomes the new hi, a false middle moves lo past it. Each step also shrinks the range, because mid is strictly below hi. When lo meets hi, the invariant says everything below is false and everything from there on is true: that point is the switch.

The lower bound from the searching lesson is the special case where the test is "is this item at least the target?":

import { firstTrue } from "./first-true.js";

const orderIds = [1004, 1011, 1011, 1011, 1015, 1020];
const lowerBound = (items, target) => firstTrue(0, items.length, (i) => items[i] >= target);
const upperBound = (items, target) => firstTrue(0, items.length, (i) => items[i] > target);

console.log(lowerBound(orderIds, 1011), upperBound(orderIds, 1011), upperBound(orderIds, 1011) - lowerBound(orderIds, 1011));
console.log(lowerBound(orderIds, 1000), lowerBound(orderIds, 1013), lowerBound(orderIds, 9999));

1 4 3
0 4 6

The first and last position of 1011 are 1 and 3 (upper bound minus one), it appears 3 times, a new id 1013 would be inserted at position 4, and 9999 would go past the end (6). One function, many questions.

How to recognise it

• The question asks for the minimum (or maximum) value such that something is possible: the smallest capacity, the lowest speed, the fewest servers, the largest loan.
• You can write a check for one candidate answer ("can it be done with this capacity?") much more easily than you can compute the answer directly.
• The check is monotonic: if a value works, every bigger (or every smaller) value works too.
• Something is ordered in time and changes once: the first bad version, the first day stock ran out, the first log line after a timestamp.

The improved solution

Search capacities from max(weights) to sum(weights) with the loading simulation as the test. Because firstTrue treats hi as exclusive, pass sum + 1:

import { firstTrue } from "./first-true.js";

export function daysNeeded(weights, capacity, counter = { loads: 0 }) {
  let days = 1;
  let load = 0;
  for (const w of weights) {
    counter.loads++;
    if (load + w > capacity) {
      days++;
      load = 0;
    }
    load += w;
  }
  return days;
}

export function minCapacity(weights, maxDays, counter = { checks: 0, loads: 0 }) {
  if (weights.length === 0) return 0;
  if (!Number.isInteger(maxDays) || maxDays < 1) throw new RangeError("maxDays must be a positive integer");
  const heaviest = Math.max(...weights);
  const total = weights.reduce((a, b) => a + b, 0);
  return firstTrue(heaviest, total + 1, (c) => daysNeeded(weights, c, counter) <= maxDays, counter);
}

Try it on the ten parcels, and count the work as before:

import { minCapacity } from "./capacity.js";

const parcels = [30, 25, 40, 10, 35, 20, 45, 15, 30, 25];
console.log(minCapacity(parcels, 5), minCapacity(parcels, 1), minCapacity(parcels, 10), minCapacity([], 3));

for (const n of [100, 1000, 10000]) {
  const weights = Array.from({ length: n }, (_, i) => 1 + ((i * 37) % 50));
  const counter = { checks: 0, loads: 0 };
  const capacity = minCapacity(weights, 5, counter);
  console.log(`n=${String(n).padEnd(6)} capacity=${String(capacity).padEnd(6)} checks=${String(counter.checks).padEnd(3)} parcel loads=${counter.loads}`);
}

60 275 45 0
n=100    capacity=524    checks=11  parcel loads=1100
n=1000   capacity=5100   checks=15  parcel loads=15000
n=10000  capacity=51000  checks=18  parcel loads=180000

The same capacities as the naive version, with 11 to 18 checks instead of hundreds or tens of thousands. At 10,000 parcels, 180,000 simulated loads instead of about 510 million. The number of checks is log₂(total − heaviest + 1), rounded up: doubling the total weight adds just one check.

Notice the division of labour. The check contains all the knowledge about trucks and parcels; the search knows nothing about them. That separation is what makes the pattern reusable: change the check and the same firstTrue finds a minimum rider speed, a minimum server count, or a minimum interest rate.

Its complexity

Let n be the input size, R the number of candidate answers (here total − heaviest + 1), and C the cost of one check (here O(n)).

The range R can be huge (billions of kobo, years of seconds) and it barely matters: log₂ of a billion is about 30. What matters is the cost of each check, which is why the pattern shines when a check is expensive, as in the next problem.

The first failing build

On Monday the checkout tests passed. Today, 1,000 commits later, they fail. Running the full test suite for one commit takes about 8 minutes. Which commit broke checkout?

import { firstTrue } from "./first-true.js";

const commits = Array.from({ length: 1001 }, (_, i) => ({ id: `c${String(i).padStart(4, "0")}`, index: i }));
const brokenFrom = 637; // unknown to the search: only the test knows

function testsFail(commit, log) {
  log.push(commit.id); // in real life: check out, build, run the suite (8 minutes)
  return commit.index >= brokenFrom;
}

const log = [];
const first = firstTrue(1, commits.length, (i) => testsFail(commits[i], log));
console.log(`first failing commit: ${commits[first].id} after ${log.length} test runs (about ${log.length * 8} minutes)`);
console.log(log.join(" "));

let linearRuns = 0;
for (const commit of commits.slice(1)) {
  linearRuns++;
  if (commit.index >= brokenFrom) break;
}
console.log(`walking forwards from Monday: ${linearRuns} test runs (about ${linearRuns * 8} minutes)`);

first failing commit: c0637 after 10 test runs (about 80 minutes)
c0501 c0751 c0626 c0689 c0658 c0642 c0634 c0638 c0636 c0637
walking forwards from Monday: 637 test runs (about 5096 minutes)

Ten test runs, 80 minutes, instead of 637 runs and about three and a half days. The log shows the search homing in: a run in the middle, then a quarter, then an eighth. This is exactly what git bisect does. You mark one commit good and one bad; git checks out the middle commit; you (or a script with git bisect run) report good or bad; and it halves again. The Git lesson covers git itself, and Debugging practice uses bisect on a real bug hunt.

Searching a rotated list

A delivery tracker keeps the last 12 hours of GPS pings in a ring buffer: a fixed-size array that is written in a circle, overwriting the oldest entry once full (you built one in Stacks and queues). The timestamps inside are sorted, but the sorted order starts somewhere in the middle of the array and wraps around:

positions:   0     1     2     3     4     5     6     7
minutes:   [610,  615,  620,  580,  590,  595,  600,  605]
                         ^     ^
                   newest       oldest: the array is sorted, then "rotated" at 3

Such an array is called a rotated sorted array. Support asks for the ping at minute 595. Plain binary search fails: at the middle (position 3, value 580) it would conclude that 595, being bigger, lies to the right, which here happens to be true, but for 615 it would also go right and miss it.

function searchRotated(items, target, counter = { steps: 0 }) {
  let lo = 0;
  let hi = items.length - 1;           // inclusive bounds this time
  while (lo <= hi) {
    counter.steps++;
    const mid = Math.floor((lo + hi) / 2);
    if (items[mid] === target) return mid;
    if (items[lo] <= items[mid]) {       // left half lo..mid is sorted
      if (items[lo] <= target && target < items[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                             // right half mid..hi is sorted
      if (items[mid] < target && target <= items[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

const pings = [610, 615, 620, 580, 590, 595, 600, 605];
console.log(pings.map((m) => searchRotated(pings, m)).join(" "));
console.log(searchRotated(pings, 597), searchRotated([], 1), searchRotated([580], 580));

const big = Array.from({ length: 1000000 }, (_, i) => (i + 400000) % 1000000); // rotated at 600000
const counter = { steps: 0 };
console.log(searchRotated(big, 123456, counter), counter.steps, "steps for a million pings");

0 1 2 3 4 5 6 7
-1 -1 0
723456 20 steps for a million pings

This version uses inclusive bounds (lo <= hi, mid ± 1), like the classic search in the searching lesson; firstTrue uses half-open bounds. Both are correct on their own terms; mixing them is the bug. Every value is found, a missing minute returns −1, and a million entries take about 20 steps.

Failure cases

• A test that is not monotonic. Binary search assumes one switch. With a flaky test, or a condition like "the truck is exactly full on the last day" (true, false, true…), the result is an arbitrary switch point, returned with total confidence. Before searching, argue that "works for x" implies "works for every bigger x".
• Bounds that do not contain the answer. Starting at 1 kg instead of the heaviest parcel is harmless (the check fails there), but ending below the total can mean no capacity passes, and firstTrue returns hi, a value you never tested. Choose an lo that is a valid lower limit and an hi that certainly works, or check the result before trusting it.
• A check that is wrong at the edges. daysNeeded must handle a parcel exactly equal to the capacity (load + w > capacity, not >=). A bug in the check becomes a bug in the answer, and the search hides it.
• Mixing bound styles. hi = mid belongs with lo < hi and an exclusive hi; hi = mid − 1 belongs with lo <= hi. Mixing them loops forever or skips answers, as the searching lesson's classic bugs showed.
• Searching real numbers. On decimals, lo < hi may never become false. Search integers in the smallest unit (kobo, grams, seconds) whenever you can, or run a fixed number of halvings.
• Rotated arrays with duplicates lose the O(log n) guarantee.

Testing a search on the answer

The naive version, "try every candidate from the bottom", is the perfect reference: slow, but its correctness is obvious. Compare on many small random inputs, including single parcels, parcels of equal weight and a day limit larger than the number of parcels:

import { daysNeeded, minCapacity } from "./capacity.js";

function minCapacitySlow(weights, maxDays) {
  if (weights.length === 0) return 0;
  let c = Math.max(...weights);
  while (daysNeeded(weights, c) > maxDays) c++;
  return c;
}

function xorshift(seed) {
  return () => {
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) / 4294967296;
  };
}

const random = xorshift(2026);
let agree = 0, oneDay = 0, onePerDay = 0;
for (let t = 0; t < 3000; t++) {
  const weights = Array.from({ length: Math.floor(random() * 9) }, () => 1 + Math.floor(random() * 20));
  const days = 1 + Math.floor(random() * 10);
  const fast = minCapacity(weights, days);
  if (fast === minCapacitySlow(weights, days)) agree++;
  if (weights.length > 0 && fast === weights.reduce((a, b) => a + b, 0)) oneDay++;
  if (weights.length > 0 && fast === Math.max(...weights)) onePerDay++;
}
console.log(`${agree}/3000 agree; ${oneDay} answers at the top bound, ${onePerDay} at the bottom bound`);

3000/3000 agree; 580 answers at the top bound, 1964 at the bottom bound

Counting how many answers landed on each bound shows the test reached both ends of the search range, where off-by-one bugs live. The test imports minCapacity from capacity.js, the file written earlier in this project, so the code you tested is the code you ship. It also borrows that file's daysNeeded for the reference, so the test checks the search; the check itself was verified by hand on the ten-parcel example.

Binary search in production

• git bisect run. Give git a script that exits 0 for good and non-zero for bad, and it bisects unattended. Make the script deterministic; one flaky run sends it down the wrong half.
• Capacity planning. "The fewest servers that keep response times under 300 ms at peak" is a search on the answer, with a load test as the check. Each check is expensive, so halving the range matters.
• Logs and time series. Log files and metrics are sorted by time; tools jump to the first line after a timestamp with a binary search over the file's byte offsets instead of reading gigabytes.
• Database indexes. A B-tree index is a very wide, shallow search tree; each level is a small binary search. It is why WHERE created_at >= … on an indexed column is fast.
• Configuration bisecting. When one of 40 feature flags breaks a page, turning half of them off at a time finds it in about 6 tries.

New problems to practise

import { firstTrue } from "./first-true.js";

function hoursAt(jobs, speed) {
  let hours = 0;
  for (const pages of jobs) hours += Math.ceil(pages / speed);
  return hours;
}

function slowestSpeed(jobs, maxHours) {
  if (jobs.length > maxHours) return null; // at least one hour per job
  return firstTrue(1, Math.max(...jobs) + 1, (s) => hoursAt(jobs, s) <= maxHours);
}

const jobs = [120, 45, 300, 80, 210];
const speed = slowestSpeed(jobs, 10);
console.log(speed, hoursAt(jobs, speed), hoursAt(jobs, speed - 1));
console.log(slowestSpeed(jobs, 5), slowestSpeed(jobs, 4));

100 10 11
300 null

import { firstTrue } from "./first-true.js";

function balanceAfter(principalKobo, monthlyRate, payment, months) {
  let balance = principalKobo;
  for (let m = 0; m < months; m++) {
    balance += Math.round(balance * monthlyRate);
    balance -= payment;
  }
  return balance;
}

const principal = 500000 * 100;
const payment = firstTrue(0, principal * 2, (p) => balanceAfter(principal, 0.03, p, 12) <= 0);
console.log(`₦${(payment / 100).toFixed(2)} a month`);
console.log(balanceAfter(principal, 0.03, payment, 12) <= 0, balanceAfter(principal, 0.03, payment - 1, 12) <= 0);

₦50231.05 a month
true false

import { firstTrue } from "./first-true.js";

function oldestPosition(items) {
  if (items.length === 0) return -1;
  const last = items[items.length - 1];
  return firstTrue(0, items.length - 1, (i) => items[i] <= last);
}

console.log(oldestPosition([610, 615, 620, 580, 590, 595, 600, 605]));
console.log(oldestPosition([580, 590, 600]), oldestPosition([600, 580]), oldestPosition([580]));

3
0 1 0

Summary

• Binary search needs a monotonic yes/no test over an ordered range, not a sorted array: false, …, false, true, …, true. It finds the switch in ⌈log₂ R⌉ tests.
• Write one firstTrue(lo, hi, test) with a clear invariant (everything below lo is false, everything from hi on is true) and reuse it: lower and upper bound, minimum capacity, first failing build.
• For "the minimum value such that…", write a check for one candidate, argue it is monotonic, pick bounds that surely contain the answer, and search them.
• Total cost is the cost of one check times log of the range, so even huge ranges are cheap; expensive checks (builds, load tests) benefit most.
• In a rotated sorted array, one half is always sorted; a range check on it decides which half to keep.
• Test against a linear scan of every candidate, and make sure the tests land on both bounds.

Next: Pattern practice, where the problems no longer tell you which pattern to use.