Algorithms from zero

Binary search on the answer

Crux Binary search is not only for finding a value in a sorted array—it works on any sorted space. Search over possible answers when you can ask ''''is this answer feasible?'''' and the answer is monotonic: false, false, …, false, then true, true, …

◷ 20 min

You learned binary search to find a value in a sorted array—an index where the target lives. But binary search is more general: it is a way to find the best answer in a sorted space of possible answers. Imagine a problem: “What is the minimum speed at which I can finish a task?” or “What is the smallest container capacity that allows me to ship all packages on time?” These are not array indices. They are values in a range. The trick is to recognize that the feasibility of an answer is monotonic—once an answer works, all larger answers work too. That monotonic property is what binary search exploits. Instead of guessing blindly or checking every possible answer one by one (O(n)), binary search narrows the answer range by half each step: O(log(range)).

Goal

After this lesson you understand binary search on the answer: what “binary search on the answer” means (searching a range of possible answers instead of array indices), the precondition (a monotonic predicate: a yes/no test that transitions from false to true exactly once as the answer increases), the method (binary search the answer range; at each step, check if the candidate answer is feasible), why it works (the monotonic property ensures that if answer x works, all larger answers work; if x fails, all smaller answers fail), the classic worked example (minimum ship capacity or eating speed), and how to recognize when to use it (the problem asks for a minimum or maximum value, feasibility is checkable, and the answer is monotonic).

The idea

What is “binary search on the answer”?

In the classic binary search, you search for an index in a sorted array: [1, 3, 5, 7, 9]. But sometimes the problem is not “find an index”—it is “find a value that satisfies a condition.”

Example: “What is the minimum ship capacity (in kg) such that I can ship all packages in 5 days?”

The answer is not an array index. It is a value in the range [max_package_weight, sum_of_all_weights]. For example, [10 kg, 100 kg]. You do not have an explicit sorted array to search. Instead, you search the space of possible answers. If capacity 40 kg allows you to ship in 5 days, does capacity 41 kg also allow it? Yes, always. If capacity 39 kg does not allow it, does capacity 38 kg allow it? No, never. This is the monotonic property.

The precondition: a monotonic predicate

For binary search on the answer to work, you need a monotonic predicate feasible(x):

A function that returns true or false.
As x increases, the result changes from false to true at most once. Example: false, false, false, false, true, true, true.
Once it flips to true, it stays true (or: once it flips to false, it stays false).

Example: feasible(capacity) = “Can I ship all packages within 5 days at this capacity?” As capacity increases, the answer stays false until some threshold, then stays true.

Why monotonic matters

If the predicate is monotonic, you can binary search the answer space. If it is not monotonic (e.g., sometimes true, sometimes false, sometimes true again), binary search fails because the left and right halves do not give you information.

The method: binary search the answer range

Define the search range. Set lo and hi to the minimum and maximum possible answers.
- Example: lo = max_package (the heaviest single package must fit), hi = sum_of_all_packages (worst case: take all at once).
Binary search the range.
- Compute mid = lo + (hi - lo) / 2.
- Check if feasible(mid) is true.
- If true: the answer is mid or smaller. Set hi = mid (or hi = mid - 1 to find the exact boundary).
- If false: the answer is larger. Set lo = mid + 1.
- Repeat until lo == hi (the smallest value for which feasible is true).

Worked example: minimum ship capacity

You have packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], and you must ship them all within D = 5 days. Packages are loaded in order; you cannot rearrange them. What is the minimum ship capacity?

Define feasible(capacity):

function canShipInDays(weights, capacity, days) {
  let currentDayWeight = 0;
  let daysNeeded = 1;
  
  for (const weight of weights) {
    if (currentDayWeight + weight > capacity) {
      // Current package does not fit; start a new day
      daysNeeded++;
      currentDayWeight = weight;
    } else {
      currentDayWeight += weight;
    }
  }
  
  return daysNeeded <= days;
}

Binary search:

lo = 10 (the heaviest package).
hi = 55 (sum of all weights).

Step 1: mid = 32. Can we ship in 5 days at capacity 32?

Day 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Cannot fit 8 (28 + 8 = 36 > 32).
Day 2: 8 + 9 = 17. Cannot fit 10 (17 + 10 = 27 ≤ 32, so it fits).
Day 2: 8 + 9 + 10 = 27. Done.
Total: 2 days ≤ 5 days. Feasible. Set hi = 32.

Step 2: mid = 21. Can we ship in 5 days at capacity 21?

Day 1: 1 + 2 + 3 + 4 + 5 + 6 = 21. Cannot fit 7.
Day 2: 7 + 8 = 15. Cannot fit 9 (15 + 9 = 24 > 21).
Day 3: 9 + 10 = 19. Done.
Total: 3 days ≤ 5 days. Feasible. Set hi = 21.

Step 3: mid = 15. Can we ship in 5 days at capacity 15?

Day 1: 1 + 2 + 3 + 4 + 5 = 15. Cannot fit 6.
Day 2: 6 + 7 = 13. Cannot fit 8 (13 + 8 = 21 > 15).
Day 3: 8 + 9 = 17 > 15. Cannot start here because single package 8 > 15? No, 8 ≤ 15, so it fits alone.
Actually: Day 3: 8. Day 4: 9. Day 5: 10. Total: 5 days. Feasible. Set hi = 15.

Step 4: mid = 12. Can we ship in 5 days at capacity 12?

Day 1: 1 + 2 + 3 + 4 = 10. Cannot fit 5 (10 + 5 = 15 > 12).
Day 2: 5 + 6 = 11. Cannot fit 7.
Day 3: 7. Cannot fit 8.
Day 4: 8. Cannot fit 9.
Day 5: 9. Cannot fit 10.
Day 6: 10.
Total: 6 days > 5 days. Not feasible. Set lo = 13.

Step 5: mid = 14. Can we ship in 5 days at capacity 14?

Day 1: 1 + 2 + 3 + 4 = 10. Cannot fit 5 (10 + 5 = 15 > 14).
Day 2: 5 + 6 = 11. Cannot fit 7.
Day 3: 7. Cannot fit 8.
Day 4: 8. Cannot fit 9.
Day 5: 9. Cannot fit 10.
Day 6: 10.
Total: 6 days > 5 days. Not feasible. Set lo = 15.

Step 6: lo = 15, hi = 15. Answer is 15.

The minimum ship capacity is 15 kg.

The code

Let us code binary search on the answer. We will use the ship capacity example.

function canShipInDays(weights, capacity, days) {
  let currentDayWeight = 0;
  let daysNeeded = 1;

  for (const weight of weights) {
    if (currentDayWeight + weight > capacity) {
      // Start a new day
      daysNeeded++;
      currentDayWeight = weight;
      
      // Sanity check: no single package exceeds capacity
      if (weight > capacity) return false;
    } else {
      currentDayWeight += weight;
    }
  }

  return daysNeeded <= days;
}

function minShipCapacity(weights, days) {
  // Binary search the capacity range
  let lo = Math.max(...weights);  // At least the heaviest package
  let hi = weights.reduce((a, b) => a + b, 0);  // At most the sum of all

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    
    if (canShipInDays(weights, mid, days)) {
      // mid works; try smaller
      hi = mid;
    } else {
      // mid does not work; try larger
      lo = mid + 1;
    }
  }

  return lo;  // lo == hi; the minimum feasible capacity
}

Key insights:

canShipInDays is the feasibility check. It simulates shipping and counts days.
The loop condition lo < hi narrows until they meet.
If feasible(mid) is true, we set hi = mid (we might find smaller). If false, we set lo = mid + 1 (we need larger).
The answer is lo when the loop exits.

Let us test it:

function canShipInDays(weights, capacity, days) {
let currentDayWeight = 0;
let daysNeeded = 1;

for (const weight of weights) {
  if (currentDayWeight + weight > capacity) {
    daysNeeded++;
    currentDayWeight = weight;
    if (weight > capacity) return false;
  } else {
    currentDayWeight += weight;
  }
}

return daysNeeded <= days;
}

function minShipCapacity(weights, days) {
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b, 0);

while (lo < hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  
  if (canShipInDays(weights, mid, days)) {
    hi = mid;
  } else {
    lo = mid + 1;
  }
}

return lo;
}

// Test 1
const weights1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const days1 = 5;
console.log("Weights:", weights1);
console.log("Days:", days1);
console.log("Min capacity:", minShipCapacity(weights1, days1), "(expected 15)");

// Verify: can we ship with capacity 15 in 5 days?
console.log("Can ship with capacity 15?", canShipInDays(weights1, 15, days1));

// Test 2
const weights2 = [3, 2, 2, 4, 1, 4];
const days2 = 3;
console.log("\nWeights:", weights2);
console.log("Days:", days2);
console.log("Min capacity:", minShipCapacity(weights2, days2), "(expected 6)");
console.log("Can ship with capacity 6?", canShipInDays(weights2, 6, days2));

// Test 3: single day
const weights3 = [1, 2, 3];
const days3 = 1;
console.log("\nWeights:", weights3);
console.log("Days:", days3);
console.log("Min capacity:", minShipCapacity(weights3, days3), "(expected 6)");
console.log("Can ship with capacity 6?", canShipInDays(weights3, 6, days3));

Output

Step-by-step trace

Let us trace binary search on the answer space for weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5.


      1
      lo = max(weights) = 10
    

      2
      hi = sum(weights) = 55
    

      3
      while (lo < hi) {
    

      4
        mid = lo + floor((hi - lo) / 2)
    

      5
        if (canShipInDays(..., mid, 5)) hi = mid
    

      6
        else lo = mid + 1
    

      7
      }

Breakdown:

We start with a huge range [10, 55].
Each iteration, we check a candidate answer and narrow the range by half.
After ~3 steps, we’ve narrowed from 45 candidates to a few.
After ~6 steps, we find the exact answer.

The answer range is the same as the data: the sum of weights is at most 55. So log₂(55) ≈ 6 steps.

Complexity

Aspect	Value
Time: binary search loop	O(log(hi - lo))
Time: each feasibility check	O(n) (scan all weights)
Total time	O(n · log(hi - lo))
Space	O(1)

Why O(n · log(hi - lo))?

The binary search loop runs O(log(hi - lo)) times, where hi - lo is the range of possible answers. For the ship capacity problem, that is O(log(sum_of_weights)). At each iteration, we call canShipInDays, which scans all n weights: O(n). Total: O(n · log(sum)).

For the example [1, 2, …, 10], the range is [10, 55]. log₂(55) ≈ 6. So 6 iterations × 10 weights = 60 operations. Much better than checking all 45 possible capacities one by one (which would be 45 × 10 = 450 operations).

Comparison to brute force:

Brute force: check capacity 10, 11, 12, …, 55. That is O(sum) feasibility checks = O(n · sum) time.
Binary search: O(log(sum)) feasibility checks = O(n · log(sum)) time.

For sum = 1,000,000, log₂(1,000,000) ≈ 20. Brute force: 1,000,000 × n operations. Binary search: 20 × n operations. The speedup is 50,000×.

Space: O(1)

The algorithm uses only a few variables (lo, hi, mid). The feasibility check scans weights but does not store extra data.

Practice 0 / 5

Why does binary search on the answer require a monotonic predicate?

For the ship capacity problem, why is lo set to max(weights)?

For the ship capacity problem, why is hi set to sum(weights)?

Weights [1, 2, 3], days = 2. What is the minimum ship capacity? (Hint: Day 1: [1, 2], Day 2: [3].)

What does the while loop condition `lo < hi` mean in binary search on the answer?

lesson.inset.leap

From indices to answer spaces. Binary search is not limited to array indices. The key insight is that you can binary search any sorted space—as long as you can test feasibility monotonically. Indices happen to be a simple case. But answer spaces (capacities, speeds, distances, number of coins) are equally valid. Once you internalize this leap, you will recognize binary search opportunities in many “find the minimum/maximum value such that…” problems.

Common mistake

Confusing the loop condition. A common pitfall is using lo <= hi (appropriate for array binary search) instead of lo < hi (appropriate here). When searching answer ranges, use lo < hi because lo == hi means the answer is pinned. Do not double-check it.

Check yourself

Quiz

You have weights [1, 2, 3, 4, 5], days = 3, and must find the minimum ship capacity. What is the answer?

Recap

Binary search on the answer is a way to find an optimal value in a sorted space of answers, not a sorted array.

Precondition: A monotonic predicate—a yes/no test that transitions from false to true (or true to false) exactly once as the answer increases.

The method: Binary search the answer range [lo, hi]. At each step, check if a candidate answer is feasible. If yes and you want the minimum, try smaller (hi = mid). If no, try larger (lo = mid + 1). When lo == hi, you have found the answer.

Classic example: Minimum ship capacity. Given packages and a deadline (days), find the smallest capacity such that all packages can ship within the deadline. The feasibility test is O(n) (simulate shipping). Binary search the capacity range: O(log(sum_of_weights)). Total: O(n · log(sum)).

Why learn it? Many “find the minimum/maximum such that…” problems reduce to binary search on the answer once you recognize the monotonic predicate. It trades off linear or exponential search for logarithmic efficiency.

Pitfalls:

Check that the predicate is truly monotonic. If not, binary search fails.
Set lo and hi correctly: lo must be a feasible lower bound, hi must be an upper bound.
Use lo < hi (not lo <= hi) when searching answer ranges.

Recognition: When you see “find the minimum/maximum value such that condition C holds,” and checking C is fast and monotonic, binary search on the answer is your tool.

Continue the climb ↑Sorting and search: multiple-choice review