Searching on the answer

Some of the most useful binary searches do not search a list at all. They search through the possible answers, using a test that says whether an answer is good enough.

Binary search without a list

The last lesson ended with first_at_least. It needs three things: candidates in order, a yes-or-no question about each one, and answers that go F F … F T T … T. In that lesson, the list gave the candidates and a[i] >= t was the question. But the candidates can be any range of numbers, and the question can be any test, as long as the answers follow that pattern.

The monotone test

These problems usually ask for the smallest value that works, or the largest. Suppose that making the value bigger can only help. Then the answers to “does x work?” go F … F T … T across the range, and the smallest value that works is the first T. A test like this is called monotone.

So searching on the answer needs three things, and you must check each one:

1. A range [lo, hi] that is sure to contain the answer, where hi is known to work.
2. A test works(x) that is correct and fast.
3. A proof that the test is monotone: if works(x) is true, then works(x + 1) is true.

The parcel van

A railway parcel office must send a row of parcels with weights parcels. They must go in the order they were booked. One van leaves each day. It carries the next few parcels in the row, as long as their total weight is at most its capacity C. What is the smallest C that sends all the parcels within days days?

The range. The van must be able to carry the heaviest parcel, so C ≥ max(parcels). A van that can carry sum(parcels) takes everything on the first day, so that capacity always works.

The test. For a given C, fill each day’s van as full as possible and count the days. Filling the van as much as possible each day is the best plan: holding a parcel back for a later day can only push the later parcels further back. If the count is at most days, then capacity C works.

Monotone. Any loading plan that fits a van of capacity C also fits a bigger van. So if C works, C + 1 works.

def days_needed(parcels, cap):
    days, load = 1, 0
    for w in parcels:
        if load + w > cap:        # this parcel waits for tomorrow
            days, load = days + 1, 0
        load += w
    return days

def min_capacity(parcels, days):
    lo, hi = max(parcels), sum(parcels)   # hi always works
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(parcels, mid) <= days:
            hi = mid                      # mid works: answer is mid or less
        else:
            lo = mid + 1                  # mid fails: answer is more
    return lo

This loop is first_at_least from the last lesson, without the list. Line 13 asks the question instead of a[mid] >= t.

How long it takes

Each test goes through the parcels once, which takes O(n) time. The range has about S = sum − max + 1 possible capacities, so the search runs about log₂ S tests. That is O(n log S) in total. Trying each capacity one by one from the smallest would take O(n · S). With 50,000 parcels of up to 500 kg each, S can be 25 million. Binary search needs about 25 tests instead of up to 25 million.

Note that log S depends on how large the numbers are, not on how many there are. If every weight doubles, the search needs just one more test.

Recognising this kind of problem

Look for questions like “the minimum value such that…” or “the maximum value such that…”, where checking one value is much easier than finding the best value directly. For example:

• the slowest reading speed that finishes a syllabus before the exam;
• the largest gap you can keep between people placed on given seats;
• splitting a list into k parts so that the largest part-sum is as small as possible;
• the smallest number of days after which enough trains have arrived to run a timetable.

For a maximum, the answers go T … T F … F, and you want the last T. You can change the question so that it becomes a first-T search. Or you can search for the last T directly, which needs one extra step with rounding that lesson 6 explains.