Binary search on the answer

Why this matters

Many problems ask for a number that is the best one in some sense: the smallest truck that can carry all the packages in five trips, the fastest speed that finishes a job in time, or the largest gap you can leave between cows in a barn. You could try every number, but the range can be huge. Binary search can cut that work down to a few dozen checks, even when the range has billions of values.

Lesson 07 of this module showed binary search on a list you can see. This lesson applies the same loop to a range of numbers that you never write down. The list of possible answers is the range from 1 to some maximum. You never build it. You ask one yes-or-no question about a single number, and the answer tells you which half to keep.

This pattern turns a hard search into one simple question: "Does this number work?"

The idea in plain words

Suppose a friend says, "I am thinking of a whole number between 1 and 100. Each time you guess, I will say whether your guess is big enough." You would not guess 1, then 2, then 3. You would guess 50. If 50 is big enough, the answer is 50 or lower, so you throw away the top half. If 50 is too small, the answer is above 50, so you throw away the bottom half. Each guess halves the range.

Binary search on the answer works the same way. The yes-or-no question is called a check. A check takes one candidate number and returns true or false. For this method the check must have one important property: it must be monotone. Monotone means the answers follow one pattern as the candidate grows.

For a least-answer problem, the pattern is no, no, no, then yes, yes, yes. If a candidate works, every larger candidate also works. If a candidate fails, every smaller candidate also fails. For a greatest-answer problem, the pattern is yes, yes, yes, then no, no, no. Lesson 07 calls these the first-true and last-true shapes.

If the pattern is not monotone, the method gives wrong answers. The mistakes section shows a real example.

The three steps

Every problem in this lesson follows the same three steps.

1. Name the answer and the range it can be in. The smallest possible answer goes in lo, and the largest possible answer goes in hi.
2. Write the check. Given one candidate, return true if it is good enough.
3. Run the search loop from lesson 07, using the check as the predicate. The loop shape depends on whether you want the least or the greatest answer.

Most of the work is in steps 1 and 2. The loop is short and it is the same each time.

Worked example 1: the smallest number whose square is large enough

Warm up with a problem you can check by hand. Find the smallest whole number x such that x * x is at least n. For n equal to 50, the answer is 8, because 7 times 7 is 49, which is just short, and 8 times 8 is 64.

The answer can be anywhere from 0 to n, since n squared is always at least n when n is at least 1. So lo starts at 0 and hi starts at n. The check is mid * mid >= n. Its pattern is no, no, then yes, yes, which is monotone. Bigger numbers have bigger squares.

Here is the search for n equal to 50.

Now lo and hi are both 8, so the answer is 8.

The variables are long long, an integer type that holds much larger numbers than int. A square of a large int can pass the largest int value, and long long avoids that wrap-around.

#include <iostream>
using namespace std;
 
long long smallest_root_at_least(long long n) {
    long long lo = 0;
    long long hi = n;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (mid * mid >= n) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
 
int main() {
    cout << "smallest x with x*x >= 50: " << smallest_root_at_least(50) << "\n";
    cout << "smallest x with x*x >= 49: " << smallest_root_at_least(49) << "\n";
    return 0;
}

The output is:

smallest x with x*x >= 50: 8
smallest x with x*x >= 49: 7

The loop is the first-true template from lesson 07. The only new part is that the predicate is a check on a number, not on a list position.

Worked example 2: shipping packages in order

Now a problem with a real story. A warehouse has packages with these weights in kilograms, listed in the order they arrive: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Packages must leave in that order. Each truck trip can carry at most cap kilograms. All packages must leave within days trips. Find the smallest cap that makes this possible.

With days equal to 5, the answer is 15. One way to fill five trips with a cap of 15 is:

• Trip 1: 1, 2, 3, 4, 5, total 15
• Trip 2: 6, 7, total 13
• Trip 3: 8
• Trip 4: 9
• Trip 5: 10

A cap of 14 fails. The first trip stops after 1 to 4, which totals 10, because adding 5 would make 15. The second trip takes 5 and 6, which is 11. Then 7 does not fit, so trip three takes 7 alone, trip four takes 8, trip five takes 9, and 10 needs a sixth trip.

The check

The check answers one question: with a cap of cap kilograms per trip, do the packages fit in days trips? To answer it, fill each trip as far as it goes, then start a new trip. Because the packages must keep their order, filling a trip as far as it can go never leaves a later trip with more to carry than necessary. So this count is the smallest number of trips for that cap.

bool can_ship(const vector<int>& w, int days, long long cap) {
    int trips = 1;
    long long load = 0;
    for (int x : w) {
        if (x > cap) return false;
        if (load + x > cap) {
            ++trips;
            load = 0;
        }
        load += x;
    }
    return trips <= days;
}

The line if (x > cap) return false; handles a package that is heavier than the cap on its own. No trip can carry it, so the cap is too small.

The search

The smallest possible cap is the weight of the heaviest package, because a truck must be able to carry it alone. The largest useful cap is the total weight of all packages, because one trip can carry everything. So lo starts at the largest weight and hi starts at the sum.

long long min_capacity(const vector<int>& w, int days) {
    long long lo = *max_element(w.begin(), w.end());
    long long hi = accumulate(w.begin(), w.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (can_ship(w, days, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

The 0LL in accumulate is a long long zero. It makes the running sum a long long too, so a large total does not wrap around. The loop is the first-true template: the check is true from some cap upward.

Tracing the search with five trips

The weights are 1 to 10 and days is 5. The range starts as 10 to 55.

Now lo equals hi, which is 15. The search needed five checks for a range of 46 values.

Running it

The program below finds the answer for three values of days, and then checks the fast search against a slow one on random inputs.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
 
bool can_ship(const vector<int>& w, int days, long long cap) {
    int trips = 1;
    long long load = 0;
    for (int x : w) {
        if (x > cap) return false;
        if (load + x > cap) {
            ++trips;
            load = 0;
        }
        load += x;
    }
    return trips <= days;
}
 
long long min_capacity(const vector<int>& w, int days) {
    long long lo = *max_element(w.begin(), w.end());
    long long hi = accumulate(w.begin(), w.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (can_ship(w, days, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
 
int main() {
    vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << "min capacity for 10 packages in 5 trips: " << min_capacity(w, 5) << "\n";
    cout << "min capacity for 10 packages in 1 trip:  " << min_capacity(w, 1) << "\n";
    cout << "min capacity for 10 packages in 10 trips: " << min_capacity(w, 10) << "\n";
    return 0;
}

The output is:

min capacity for 10 packages in 5 trips: 15
min capacity for 10 packages in 1 trip:  55
min capacity for 10 packages in 10 trips: 10

With one trip, every package must share a single truck, so the cap is the total, 55. With ten trips, each package can have its own trip, so the cap is the heaviest package, 10.

Worked example 3: cows in stalls, the largest answer

The third problem asks for the greatest answer. A barn has stalls at positions 1, 2, 4, 8 and 9 along a line. You want to place k cows, one in each of k stalls, so that the closest two cows are as far apart as possible. The answer is the largest possible gap between the closest pair.

For k equal to 3, one good placement is stalls 1, 4 and 8. The gaps are 3 and 4, so the closest pair is 3 apart. The answer is 3.

The check

Given a gap d, can you place k cows so that every two neighbouring cows are at least d apart? Use a greedy rule, which means make the choice that looks best right now and never go back. Put the first cow at the first stall. Then go along the stalls in order, and place the next cow at the first stall that is at least d away from the last cow placed. If you place k cows, the check is true.

Greedy works here for the same reason it worked for shipping. Placing each cow as early as possible leaves the most room for the rest.

The check is monotone in the opposite direction from shipping. If a gap of 5 works, a gap of 4 also works, because every pair that was 5 apart is still at least 4 apart. So the pattern is yes, yes, then no, no. We want the last yes.

bool can_place(const vector<long long>& pos, int k, long long d) {
    int placed = 1;
    long long last = pos[0];
    for (size_t i = 1; i < pos.size() && placed < k; ++i) {
        if (pos[i] - last >= d) {
            ++placed;
            last = pos[i];
        }
    }
    return placed >= k;
}

The search for the last yes

The smallest possible gap is 0. The largest is the distance from the first stall to the last stall. For this shape we use the last-true template from lesson 07, with the round-up middle. Round-up matters here for the same reason it mattered there: an update that sets lo to mid must move lo forward.

long long max_min_distance(vector<long long> pos, int k) {
    sort(pos.begin(), pos.end());
    long long lo = 0;
    long long hi = pos.back() - pos.front();
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (can_place(pos, k, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

The sort call is there because the check walks the stalls from left to right. An unsorted list gives wrong gaps.

Tracing the search with three cows

The stalls are 1, 2, 4, 8 and 9. The range for the gap starts at 0 to 8.

Now lo equals hi, which is 3. The first check at gap 4 places only two cows, because after stall 1 the next stall at least 4 away is stall 8, and then stall 9 is too close.

Running it

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
bool can_place(const vector<long long>& pos, int k, long long d) {
    int placed = 1;
    long long last = pos[0];
    for (size_t i = 1; i < pos.size() && placed < k; ++i) {
        if (pos[i] - last >= d) {
            ++placed;
            last = pos[i];
        }
    }
    return placed >= k;
}
 
long long max_min_distance(vector<long long> pos, int k) {
    sort(pos.begin(), pos.end());
    long long lo = 0;
    long long hi = pos.back() - pos.front();
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (can_place(pos, k, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}
 
int main() {
    vector<long long> stalls = {1, 2, 4, 8, 9};
    cout << "max min distance, 3 cows: " << max_min_distance(stalls, 3) << "\n";
    cout << "max min distance, 2 cows: " << max_min_distance(stalls, 2) << "\n";
    cout << "max min distance, 5 cows: " << max_min_distance(stalls, 5) << "\n";
    return 0;
}

The output is:

max min distance, 3 cows: 3
max min distance, 2 cows: 8
max min distance, 5 cows: 1

With two cows, the best choice is stalls 1 and 9, which are 8 apart. With five cows, every stall is used, and the closest pair is 1 apart.

Checking the search against a slow method

A search like this can be wrong on a small case that the examples did not cover. The safest check is a slow method that tries every candidate, run on many random inputs. For shipping, the slow method starts at the heaviest package and counts up one kilogram at a time until the check passes.

Put this main after the can_ship and min_capacity functions from the shipping section. It also needs the brute_min_capacity function shown here.

#include <cstdlib>
 
long long brute_min_capacity(const vector<int>& w, int days) {
    long long cap = *max_element(w.begin(), w.end());
    while (!can_ship(w, days, cap)) ++cap;
    return cap;
}
 
int main() {
    srand(11);
    int checks = 0;
    for (int round = 0; round < 1000; ++round) {
        int m = 1 + rand() % 8;
        vector<int> packages(m);
        for (int& x : packages) x = 1 + rand() % 20;
        int days = 1 + rand() % m;
        if (min_capacity(packages, days) != brute_min_capacity(packages, days)) {
            cout << "FAIL\n";
            return 1;
        }
        ++checks;
    }
    cout << "shipping checks passed: " << checks << "\n";
    return 0;
}

The output is:

shipping checks passed: 1000

The slow method is only a test. In a real program it would be far too slow for large weights, which is why the search exists.

Common mistakes

A range that is too small

If hi is smaller than the true answer, the search cannot find it. The template assumes the answer is inside the range, so it returns hi without checking it. Here is the shipping search with hi set to 20 instead of the total of 55, and one trip allowed:

wrong hi = 20, days 1: 20
correct hi = 55, days 1: 55

The answer 20 is wrong, because twenty kilograms cannot carry all packages in one trip. Always set hi to a value you know is good enough, such as the total weight or the largest gap in the list.

A check that is not monotone

The check must keep one pattern as the candidate grows. Consider a check that asks whether the shipping plan uses exactly five trips. With a cap of 15 the plan uses five trips, but with a cap of 14 it uses six, and with a cap of 17 it uses four. The pattern is not yes, yes, no, no, because it goes no, yes, no. The search gives the wrong answer here:

binary search on 'exactly 5 trips' returns 55
trips at 55 is 1
first cap with exactly 5 trips by scan: 15

The fix is to change the check to "at most five trips", which is monotone. Then the search returns 15.

Mixing the wrong template with the wrong question

Shipping asks for the least answer, so it uses the first-true loop with hi = mid. Cows asks for the greatest answer, so it uses the last-true loop with lo = mid and the round-up middle. If you copy the cows loop into shipping, the search can return a wrong value or get stuck in a loop. Decide first whether the check turns from no to yes, or from yes to no, and then pick the matching loop.

A list of the wrong type

The cows function takes vector<long long> for stall positions. Passing a vector<int> fails to compile. Here is the error from g++ 15 for that call. Your file name and line number will differ:

cows.cpp:31:30: error: could not convert ‘bad’ from ‘vector<int>’ to ‘vector<long long int>’
   31 |     cout << max_min_distance(bad, 3) << "\n";
      |                              ^~~
      |                              |
      |                              vector<int>

The fix is to declare the list with the type the function expects, or to change the function to take the type you have. Mixed int and long long values are a common source of this error in search code.

An empty list

max_element on an empty list returns the end position, and dereferencing that position reads memory that holds no package. Check for an empty list before calling min_capacity, and return a value that makes sense for your problem.

Adding the sum in an int

If accumulate starts from 0 instead of 0LL, the running sum is an int. Two packages of 2,000,000,000 kilograms each add up to more than the largest int, which is 2,147,483,647 on most systems. Signed integer overflow is undefined behaviour in C++, so the result cannot be trusted. Use long long for every value that holds a sum or a distance.

Practice

Exercise 1: smallest root

Use smallest_root_at_least to find the smallest x with x * x at least 200. What is x?

Show the answer

x is 15. The number 14 squared is 196, which is less than 200. The number 15 squared is 225, which is at least 200.

Exercise 2: four equal packages

Four packages each weigh 4 kilograms. Using min_capacity, find the smallest cap for two trips, and then for four trips.

Show the answer

For two trips the answer is 8, because two packages fit on each truck. For four trips the answer is 4, because each package can have its own truck. So min_capacity returns 8 and 4 for these two cases.

Exercise 3: why the trip count is not enough

A friend says the shipping check can start the trip count at 0 instead of 1, because the code only adds a trip when it starts a new one. Explain what goes wrong.

Show the answer

The code adds one trip each time it starts a new truck after the first one. So a plan with six real trips only adds up to five, and the check passes too easily. With the count starting at 0, the search for weights 1 to 10 and five days returns 11, but the true answer is 15. At a cap of 11 the packages need six trips: 1 to 4, then 5 and 6, then 7, 8, 9 and 10 alone. The count starts at 1 because the first truck exists as soon as the first package is loaded.

Exercise 4: cows with four stalls

Stalls are at positions 0, 3, 4, 7, 10 and 12. What is the largest gap that fits four cows? Use the max_min_distance function or work it out by hand.

Show the answer

The answer is 3. A gap of 3 can place cows at 0, 3, 7 and 10, and the gaps between them are 3, 4 and 3. A gap of 4 can place only three cows, for example at 0, 4 and 10, because no stall after 10 is at least 4 away from it.

Exercise 5: one package, three trips

A list holds one package of 5 kilograms, and days is 3. What does min_capacity return, and why?

Show the answer

It returns 5. The range starts at the heaviest package, 5, and the total is also 5, so lo and hi are equal from the start and the loop never runs. A single truck with a cap of 5 carries the one package.

Summary

• Binary search can find the best answer in a range of numbers by asking a yes-or-no check about one candidate at a time.
• The check must be monotone: once a candidate works, every candidate on one side of it works too.
• For the least answer, use the first-true loop from lesson 07. For the greatest answer, use the last-true loop with the round-up middle.
• Set the range so the true answer is always inside it. The lowest and highest sensible values, such as the heaviest package and the total weight, are a good start.
• Test the check on small inputs against a slow method that tries every candidate.