---
title: "Binary search on the answer"
url: https://algopath.pro/patterns/binary-search-on-answer
language: en
summary: "The thing you search here is the range of every possible answer. A yes-or-no test decides which half of it to throw away."
updated: 2026-08-24
---

# Binary search on the answer

The thing you search here is the range of every possible answer. A yes-or-no test decides which half of it to throw away.

## How does Binary search on the answer work?

Name the smallest and largest value the answer could take. That pair is the search range.

Write a test that asks whether one candidate works. It answers only yes or no.

The test must be monotone: once it says yes, every larger candidate says yes. Without that, halving is invalid.

Take the middle candidate and run the test. Note that this is a value, not an index.

On a yes, remember it and search the smaller half. On a no, search the larger half.

The range halves every round. Thirty rounds cover a billion candidates.

- `range = 1 to 11` Eating piles [3, 6, 7, 11] within 8 hours. Speed is the answer.
- `speed 6 takes 6 hours` Six hours is inside the limit. A slower speed might still fit.
- `range = 1 to 5` Speed 6 is kept as the best so far. Now try the lower half.
- `speed 3 takes 10 hours` That is over the limit. Everything below 3 is worse.
- `speed 4 takes 8 hours` It fits exactly, and nothing smaller fits. The answer is 4.

## When should you use Binary search on the answer?

- minimize the maximum / maximize the minimum
- smallest value that satisfies a condition
- find the smallest capacity/speed/days that works
- answer lies in a numeric range, not an array position
- a feasibility check is monotonic (true after some point)

## What is Binary search on the answer confused with?

- **Binary search (array)** - There the range holds real stored data. Here it holds every value the answer might take.
- **Greedy (exchange argument)** - The feasibility test is often greedy itself. The search only decides which candidate to test.
- **Linear search** - Trying candidates one by one is correct but slow. A monotone test lets you skip half of them.
- **Dynamic programming (1-D)** - DP builds the answer up from smaller answers. Here the answer is guessed and then checked.

## What is the time and space complexity of Binary search on the answer?

A range of 1e9 needs about 30 tests. Total cost is O(n log range) when one test costs O(n).

## A worked example of Binary search on the answer

### Ship every package within d days

Packages must ship in the given order across d days. Pick the smallest daily capacity that still finishes in time.

A package can never be split across two days.

The answer lies between the largest single package and the sum of them all.

For one candidate capacity, fill each day greedily and count the days. Compare that count against d.

```javascript
function shipWithinDays(weights, days) {
    let lo = Math.max(...weights);              // one day must hold the biggest package
    let hi = weights.reduce((a, b) => a + b, 0); // one day holds everything

    const fits = (capacity) => {
        let used = 1;
        let load = 0;

        for (const w of weights) {
            if (load + w > capacity) {
                used++;   // start a new day
                load = 0;
            }
            load += w;
        }

        return used <= days;
    };

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

    return lo;
}
```

## Common mistakes with Binary search on the answer

- **Starting the range at zero** The low bound should be a value that could actually work. For a capacity that is the largest item.
- **A test that is not monotone** If a larger candidate can fail after a smaller one passed, halving is wrong. Check the direction first.
- **Losing the last candidate that worked** Either store it in a variable, or move high to mid rather than past it.
- **Looping forever on a decimal answer** With real numbers lo never passes hi exactly. Run a fixed hundred rounds instead.

## Which interview problems use Binary search on the answer?

- **Koko eating bananas** The candidate is a speed, the test counts hours.
- **Capacity to ship packages within D days** The candidate is a daily load.
- **Split array largest sum** The candidate is the largest sum any part may reach.
- **Minimum days to make m bouquets** The candidate is a day, the test counts finished bouquets.
- **Magnetic force between two balls** Maximise the smallest gap instead of minimising a maximum.
- **Find the smallest divisor given a threshold** The candidate is the divisor.
- **Minimise max distance to gas station** A decimal answer, so the loop runs a fixed count.

## JavaScript

```javascript
function smallestFeasible(lo, hi, canDo) {
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// canDo(x) must be monotonic: false...false, true...true
```

## Python

```python
def smallest_feasible(lo, hi, can_do):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_do(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
# can_do(x) must be monotonic: False...False, True...True
```

## PHP

```php
function smallestFeasible(int $lo, int $hi, callable $canDo): int {
    while ($lo < $hi) {
        $mid = $lo + intdiv($hi - $lo, 2);
        if ($canDo($mid)) $hi = $mid;
        else $lo = $mid + 1;
    }
    return $lo;
}
// canDo($x) must be monotonic: false...false, true...true
```