Binary search on the answer: monotonicity, bounds and the loop invariant

← Back to the section

Binary search is familiar as a way to find a number in a sorted array: halve the range, throw away one half, repeat. It turns out the same trick works where there is no array at all — one of the least obvious uses of the halving idea.

A task where the answer cannot be computed

A warehouse holds piles of goods. A picker works for h hours, takes one pile per hour and picks at most speed items out of it; if fewer items are left in the pile, the whole hour is still spent. What is the smallest speed that gets everything done within h hours?

There is no formula for the answer — the speed enters the task through rounding up, and it cannot be derived directly. Yet checking a given speed is easy: count how many hours it takes and compare with h. That is O(N) per check.

Trying every speed in turn is possible, but there can be a billion of them. This is where the key observation helps.

Monotonicity — the condition for applying it

If speed 10 gets the job done, then 11 certainly does. If 5 does not, then neither does 4. In other words, as the speed grows, the answer to "do we make it?" flips exactly once: a run of "no", then a run of "yes".

That is monotonicity. In effect we have a sorted array of "no" and "yes" — it simply is not stored in memory but computed on demand. And in a sorted array the border between "no" and "yes" is found by binary search.

Monotonicity has to be verified every time. If the condition can flip back and forth — yes, no, yes — the trick returns an arbitrary suitable answer rather than the smallest one.

The solution

We search the range of possible answers: from the smallest conceivable speed to one that is obviously enough.

live example

import java.util.ArrayList;
import java.util.List;

public class MinSpeed {
    public static void main(String[] args) {
        int[] piles = {30, 11, 23, 4, 20};
        int h = 6;
        int top = 0;
        for (int p : piles) top = Math.max(top, p);
        int low = 1;
        int high = top;
        List<String> steps = new ArrayList<>();
        while (low < high) {
            int mid = low + (high - low) / 2;
            long hours = 0;
            for (int p : piles) hours += (p + mid - 1) / mid;
            steps.add(mid + (hours <= h ? " fits" : " too slow"));
            if (hours <= h) high = mid;
            else low = mid + 1;
        }
        System.out.println("speeds checked: " + String.join(", ", steps));
        System.out.println("answer: " + low + " (" + steps.size() + " checks out of " + top + ")");
    }
}

The cost is O(N · log(width of the range)): thirty candidate speeds are settled in five checks, and a billion would take about thirty.

Three places where people usually slip

The bounds. The lower one must be obviously possible, the upper one obviously sufficient. Here the upper bound is the largest pile: at that speed any pile is picked within a single hour, and faster is pointless. Set the upper bound too low and the answer is simply not inside the range.

Not converging. The loop invariant is this: high always points at a value that works, low at the first one not yet rejected. So on success we write high = mid (that very mid works, discarding it is wrong), and on failure low = mid + 1 (mid definitely does not work). Write low = mid by accident and the loop can get stuck: when high - low == 1 the midpoint equals low, and the bounds stop closing in.

Overflow and rounding. low + (high - low) / 2 is not decoration: (low + high) / 2 steps outside int on large bounds. And (p + mid - 1) / mid is division rounded up; plain division here would report fewer hours than the work really takes.

How to recognise the trick in a task

The reliable signs:

• the wording contains "the smallest such that" or "the largest such that";
• the answer is a number from a range, not an element of the data;
• the answer cannot be computed directly, but checking a given answer is easy;
• if an answer works, then any larger one (or any smaller one) works too.

Typical tasks of this shape: the smallest truck capacity that delivers everything in k trips; the greatest length the ropes can be cut into to get k pieces; the earliest day by which all the jobs are finished.

How this is done in Java

The search on the answer itself is not in the standard library, and that is expected: there is no "array" in such a task, only a check that you write for the condition at hand — the halving loop is always your own. Searching for a border among data you already store, however, was implemented long ago, and there is no point in rewriting it by hand.

For a sorted array that is Arrays.binarySearch, for a list Collections.binarySearch: inside is the same halving loop, except the midpoint there is computed with an unsigned shift ((low + high) >>> 1) — the same family of overflow tricks as low + (high - low) / 2 above. And they answer more than "present or not": when there is no exact match, the return value is -(insertion point) - 1, which is exactly the "first one that fits" border people usually write their own search for; the details and the main trap are covered in the article on arrays.

Closer to our wording are TreeSet and TreeMap. Inside them is a red-black tree: a binary search tree that adjusts its own shape on insertion, so the depth stays on the order of log N and does not degrade into a list even on data arriving in ascending order. Hence the cost: add, contains, get, remove are O(log N), and firstKey with lastKey are O(log N) for the walk down to the edge. And that is where the methods answering exactly the "first one that fits" question live: ceiling(x) returns the smallest element not below x, floor(x) the largest not above, higher and lower do the same strictly, while headMap, tailMap and subMap return a whole range of keys. The same border between "does not fit" and "fits", only searched among stored keys instead of computed by a check:

live example

import java.util.List;
import java.util.TreeSet;

public class Boundary {
    public static void main(String[] args) {
        TreeSet<Integer> speeds = new TreeSet<>(List.of(4, 7, 11, 18, 25));
        System.out.println("first not below 12: " + speeds.ceiling(12));
        System.out.println("last not above 12: " + speeds.floor(12));
        System.out.println("whole tail from 12: " + speeds.tailSet(12));
    }
}

Trees have a trap of their own, and it is a quiet one: for them the ordering is the definition of equality. TreeSet treats two elements as the same when the comparison returns zero, and does not look at equals at all. If the comparator is written, say, on price only, the second product with that same price simply never enters the set — no exception, no warning, add returns false and nobody checked it. The comparison inside a tree must distinguish exactly what equals distinguishes; otherwise the structure loses data silently.

In short

• Binary search on the answer searches the range of possible answers, not the data; the data is only used to check a candidate.
• The condition for applying it is monotonicity: the answer to "does it fit?" flips exactly once across the range.
• The cost is O(check · log(width of the range)); a billion candidates come down to about thirty checks.
• The bounds: the lower one obviously possible, the upper one obviously sufficient.
• On success high = mid, on failure low = mid + 1 — otherwise the loop may never converge.
• low + (high - low) / 2 instead of (low + high) / 2 saves you from overflow; rounding up is written as (a + b - 1) / b.
• In Java a ready-made border among stored keys comes from Arrays.binarySearch and from ceiling/floor on TreeSet and TreeMap.

What to read next

• Arrays, binary search and big O — where halving comes from and what Arrays.binarySearch returns.
• Red-black trees — what spins inside TreeSet and TreeMap.
• Two pointers and the sliding window — the neighbouring trick, for when the answer is in the data itself.
• Choosing a data structure — when an array is enough and when a tree is needed.