Binary search on the answer

Code in:JavaC#PythonJavaScript

In short: Binary search on the answer finds the smallest value (such as a capacity) for which the check "is it enough" passes, when the answers line up as "no… no, yes… yes".

Problem

How big a truck to rent

The courier company delivers the parcels along a route: in order, the order they are in along the way. The truck leaves once a day and loads the parcels one after another until the next one does not fit. That one waits for tomorrow. The eight parcels weigh 6, 9, 4, 7, 3, 8, 5 and 2 kg and must reach the customers within 3 days.

The bigger the truck, the higher the daily rent. You are looking for the smallest capacity that gets the parcels there on time. The first solution that comes to mind: try every capacity in turn, from the heaviest parcel up.

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days

weights = [6, 9, 4, 7, 3, 8, 5, 2]
capacity = max(weights)
tries = 1
while days(weights, capacity) > 3:
    capacity += 1
    tries += 1
print(f"Tries: {tries}")
print(f"Capacity: {capacity} kg")

Output

Tries: 7
Capacity: 15 kg

For eight parcels that takes 7 tries. But the warehouse in town has 1000 parcels a day (from 1 to 30 kg) for 5 working days. One by one, the checks load 3,089,000 parcels before they reach the answer, and with twice as many parcels the work grows about four times. You will measure it below.

The idea

The answer is what is sorted

The parcels are not sorted. Something else is. Ask every capacity "is it enough?" and line up the answers:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
for capacity in range(9, 19):
    d = days(weights, capacity)
    answer = "yes" if d <= 3 else "no"
    print(f"{capacity:2} kg: {d} days, {answer}")

Output

 9 kg: 7 days, no
10 kg: 6 days, no
11 kg: 5 days, no
12 kg: 5 days, no
13 kg: 5 days, no
14 kg: 5 days, no
15 kg: 3 days, yes
16 kg: 3 days, yes
17 kg: 3 days, yes
18 kg: 3 days, yes

The answers are "no", "no", … and then only "yes". Once capacity X is enough, every larger one is enough too: a bigger truck can carry exactly the same loads. A check like this is called monotone: from some point on, the answer does not change.

And in a line "no… no, yes… yes" the first "yes" is found with binary search, the same way as the first price ≥ €20 in the previous lesson: you try the middle and throw away half. This is binary search on the answer: you do not search an array, you search the range of possible answers.

The range is clear. The capacity is at least the heaviest parcel, otherwise that parcel never fits. And it does not need to be more than the sum of all of them: then everything leaves in one day.

See it

The probes along the line

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"The smallest capacity: {min_capacity(weights, 3)} kg")

Output

The smallest capacity: 15 kg

def days(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = 0
        load += weight
    return days


def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

Step by step, in words

1. 8 parcels, at most 3 days. The capacity is at least 9 kg (the heaviest parcel) and at most 44 kg (everything in one day). The answer is one of these 36 values.
2. mid = 26 kg: the truck loads in order, 2 days. 2 ≤ 3: yes. Every capacity above 26 is a yes too, so hi = 26.
3. mid = 17 kg: the truck loads in order, 3 days. 3 ≤ 3: yes. Every capacity above 17 is a yes too, so hi = 17.
4. mid = 13 kg: 5 days, more than 3: no. Every capacity below 13 is a no too, so lo = 14.
5. mid = 15 kg: the truck loads in order, 3 days. 3 ≤ 3: yes. Every capacity above 15 is a yes too, so hi = 15.
6. mid = 14 kg: 5 days, more than 3: no. Every capacity below 14 is a no too, so lo = 15.
7. lo and hi meet at 15 kg: the first "yes" on the line. 5 checks instead of trying the capacities one by one.

This is the lower bound from the previous lesson. Only instead of prices[mid] < target there is a question answered by a whole function: days(weights, mid) <= max_days. If the answer is "yes", mid may be the smallest "yes" and it stays: hi = mid. If it is "no", mid and everything below it go: lo = mid + 1.

The check days goes over all n parcels, and there are about log₂ of the total weight probes. In total O(n log S), where S is the total. One by one it would be up to S probes of n parcels each.

Try it

Predict the answer

The same eight parcels, but now for 8 days. What does the program print?

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"The smallest capacity: {min_capacity(weights, 8)} kg")

Answer

The smallest capacity: 9 kg

The smallest capacity: 6 kg

The smallest capacity: 2 kg

Check

Try it

Fill in

The check says "yes": with capacity mid the parcels arrive on time. What happens to hi?

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = 
        else:
            lo = mid + 1
    return lo

Check

Try it

Find the bug

The parcels have to arrive within 6 days. The search says 9 kg, but with 9 kg they take 7 days:

weights = [6, 9, 4, 7, 3, 8, 5, 2]
print(f"The smallest capacity: {min_capacity(weights, 6)} kg")
print(days(weights, min_capacity(weights, 6)), "days")

Output

The smallest capacity: 9 kg
7 days

Pick the line with the bug.

1def min_capacity(weights, max_days):2 lo = max(weights)3 hi = sum(weights)4 while lo < hi:5 mid = (lo + hi) // 26 if days(weights, mid) <= max_days:7 hi = mid - 18 else:9 lo = mid + 110 return lo

Check

The idea

How to spot such a task

There are three signs:

• you look for the smallest (or largest) X for which something is possible;
• for a given X the check is cheap: one pass, like days;
• the check is monotone: once X works, every larger X works too (or every smaller one).

Then you do not look for a formula for X. You binary search the range of possible X, and the check tells you which way to go.

Tasks of the same kind:

• the shortest time in which three printers with different speeds print 500 parcel labels. For a given time you count how many labels come out, and more time never gives fewer;
• the lowest speed of the warehouse conveyor at which the packages of a shift get through in 8 hours;
• the largest distance between the parcel lockers along the boulevard (the exercise below). Here you look for the largest "yes".

More precisely, if you are curious

Why the check loads "as much as fits". If the truck takes less today than it can, more is left for tomorrow. Filling it up never hurts, so the number of days that days returns is the smallest possible for that capacity.

The largest "yes". When the line is "yes… yes, no… no" and you want the last "yes", on "yes" you write lo = mid, and on "no" hi = mid - 1. Then the middle has to round up: (lo + hi + 1) // 2. Otherwise, with lo and hi next to each other, the middle is lo, lo = mid does not move and the loop never stops. The same boundary as in the binary search lesson, from the other side.

An answer with a fraction. If X is, say, a speed in meters per second, the range is made of real numbers and lo and hi never become equal. Then the loop runs a fixed number of times, for example 60: each time the range halves, and after 60 halvings it is smaller than any precision you care about.

See it

Measure: one by one against binary

Parcels from 1 to 30 kg, 5 days. The operation is one parcel loaded during a check. One by one, the number of probes grows with n, and each one loads n parcels: O(n²). Binary makes about log₂ S probes: O(n log n).

• Every capacity in turn O(n²)
• Binary search on the capacity O(n log n)

Algorithm	n = 10	n = 100	n = 1,000	n = 10,000	n = 100,000
Every capacity in turn	90	28,800	3,089,000	≈ 308,900,000	≈ 30,890,000,000
Binary search on the capacity	70	1,100	14,000	180,000	2,100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

def min_capacity(weights, max_days):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days(weights, mid) <= max_days:
            hi = mid
        else:
            lo = mid + 1
    return lo

At 1000 parcels it is 3,089,000 against 14,000. Above 1000 parcels, "one by one" is not really run: it would load hundreds of millions of parcels.

Exercise

The parcel lockers along the boulevard

Solve it in your own editor.

As far apart as possible. Along the boulevard there are seven spots for parcel lockers, at 100, 400, 900, 1200, 2000, 2400 and 3100 m from the start. The company puts up 3 lockers and wants the two closest ones to be as far apart as possible, so they cover more of the city. What is the largest possible smallest distance?

Write a check can_place(spots, lockers, gap): it puts a locker on the first spot, and every next one on the first spot at least gap meters after the previous one, and says whether there are enough for all of them. Binary search the largest gap for which the check says "yes".

Output

The largest smallest gap: 1100 m

More tasks

• The printers. Three printers print one label in 2, 3 and 7 seconds. In how few seconds do they print 500 labels?
• The couriers. Each courier works at most 8 hours and takes the orders in turn. The orders take 2, 3, 1, 4, 2, 5, 3 and 2 hours. How few couriers are needed? And if the shift is 6 hours?
• How many probes. Add a probe counter to min_capacity and compare it with the number of probes one by one for the same parcels.

Test

Check yourself

1. Why does binary search over the capacity give the right answer?

Because once capacity X is enough, every larger one is enough too: the answers are "no… no, yes… yes"Because the parcels are sorted by weightBecause capacities are whole numbers

2. The probe says "yes" at 26 kg. What happens to hi?

hi = 26: 26 may be the answer, we look for a smaller onehi = 25: 26 has already been checkedlo = 27

3. Between which values is the capacity searched?

From 0 to 1000From the heaviest parcel to the sum of all of themFrom the lightest parcel to the heaviest

4. Which task is solved with binary search on the answer?

The products sorted by priceThe shortest time in which three printers print 500 ordersThe cheapest product in a list

Check

Start the lesson over

Related lessons

• Builds on: Big-O: how the work grows · Best, average and worst case · Linear search · Binary search
• Tasks on this topic: Searching