Binary Search

When I was building the task scheduler for my Python orchestration framework, I ran into a capacity planning problem that stopped me cold. The scheduler distributed batches of work across worker processes. Each batch had a size — the number of subtasks it contained — and the system had a hard deadline: all batches had to complete within a fixed time window. I needed to find the minimum processing rate (tasks per second) that would let every batch finish on time.

My first implementation was the obvious one: loop from rate=1 upward, check whether that rate could drain every batch, and return the first rate that worked. It was correct. It was also unacceptably slow when I fed it a realistic workload — the answer could be anywhere up to the maximum batch size, which in practice meant scanning tens of thousands of candidate rates.

The fix took about five minutes once I recognized the structure of the problem: the feasibility function was monotone. If rate=10 could drain every batch in time, then so could rate=11, rate=12, and every rate above. If rate=5 was too slow, so was rate=4. That monotone structure meant I did not need to scan from 1 upward — I could binary search on the answer space and find the minimum feasible rate in O(log n) instead of O(n).

That is the move this module teaches. Binary search is not just for finding a value in a sorted array. It is for finding the boundary in any monotone sequence, whether that sequence is an actual sorted list or just a space of possible answers. Once you see it, you recognize it everywhere — rate limits, capacity thresholds, feasibility checks, minimum window sizes.

Before the answer-space variant, let's build a template that doesn't have bugs in it — off-by-one errors in binary search are famously easy to introduce and hard to spot once the code is running. I'll show you exactly where they live.

Think of binary search like looking up a name in a phone book. You do not start at the front and scan every page. You open to the middle, ask "is the name I want before or after this page?", and discard half the book. Repeat until you have one page left. The phone book might have a million entries, but you never look at more than about twenty pages.

Here is the exact-match template I reach for first:

Two things here are worth burning into memory. First, the termination condition is lo <= hi — not lo < hi. When lo == hi you still have one candidate to check; lo < hi would skip it and miss the answer. Second, mid = lo + (hi - lo) // 2 is equivalent to (lo + hi) // 2 in Python (which has arbitrary-precision integers), but the lo + (hi - lo) form is safe in languages where integer overflow is possible. I write it this way as a habit that costs nothing.

Here is what the halving looks like on a concrete array when searching for 9:

graph TD
    A["arr=[1,3,5,7,9,11,13], target=9\nlo=0, hi=6"] --> B["mid=3, arr[3]=7 < 9\nlo = mid+1 = 4"]
    B --> C["lo=4, hi=6\nmid=5, arr[5]=11 > 9\nhi = mid-1 = 4"]
    C --> D["lo=4, hi=4\nmid=4, arr[4]=9 = 9\nreturn 4"]
    style D fill:#22c55e,color:#fff

Seven elements, three comparisons. At each step the live search space is cut in half — that is where O(log n) comes from.

The exact-match template answers "is the target here?" But many real problems need a different question: "where does the target first appear?" or "where does it last appear?" For sorted data with duplicates, those are different questions with different answers.

Python's bisect module answers both. bisect.bisect_left(arr, x) returns the leftmost index where x could be inserted and keep the array sorted — equivalently, the index of the first element >= x. bisect.bisect_right(arr, x) returns the rightmost insertion point — the index of the first element > x.

When you need the left-boundary variant but cannot use bisect — for instance, when searching a custom comparator or a non-list structure — implement it yourself:

The only change from exact-match: when arr[mid] == target, record the answer and continue searching the left half (hi = mid - 1) instead of returning immediately. The right-boundary variant mirrors this — record and continue searching right (lo = mid + 1).

Here is the insight that took me too long to internalize: binary search is not a function for finding values in sorted arrays. It is a method for finding the boundary in any monotone boolean function. The sorted array is the most common context, but it is not the only one.

A feasibility function f(x) is monotone if it is "False, False, ..., True, True, True" over its domain. If you can evaluate f(x) efficiently, you can binary search for the boundary in O(log(domain size)) evaluations instead of scanning the entire domain.

Back to the orchestration problem: I had batch sizes and a time limit h. The feasibility check was:

can_finish is False for small rates and True for large ones. The answer is the leftmost True. That is a left-boundary binary search on the answer space [1, max(piles)].

The structure of the answer space looks like this — we are binary searching for the leftmost feasible rate:

graph LR
    A["rate=1\ninfeasible"] --> B["rate=2\ninfeasible"]
    B --> C["...\ninfeasible"]
    C --> D["rate=k*\nfirst feasible"]
    D --> E["rate=k*+1\nfeasible"]
    E --> F["...\nfeasible"]
    F --> G["rate=max\nfeasible"]
    style D fill:#22c55e,color:#fff

The pattern generalizes: whenever a problem asks for the minimum or maximum value satisfying some constraint, and the feasibility check is monotone, binary search on the answer space applies. "Minimum days to complete work", "minimum capacity to ship all packages", "minimum number of workers" — a large family of optimization problems that look unrelated until you notice the monotone structure.

Pause and answer these from memory before continuing. Do not scroll back up.

From memory:

1. Write the termination condition for exact-match binary search. Why <= and not <?
2. What does bisect.bisect_left([1,2,2,3], 2) return? What does bisect_right return for the same call?
3. What property must a function have for binary search on its domain to be valid?
4. In min_rate above, why is hi = max(piles) the correct upper bound?

Reflective prompt: min_rate runs O(log(max_pile)) binary search iterations, each calling can_finish in O(n). Total: O(n log m). The brute-force scan is O(n * m). When — if ever — would you prefer the brute-force? Think about the case where max(piles) is always very small (say, 5 or fewer). What does that do to the comparison?

You have piles of bananas. A guard leaves and returns in h hours. You can eat at most k bananas per hour; if a pile has fewer than k bananas left, you finish it and wait (you do not start another pile that hour). Find the minimum integer k such that you can eat all the bananas before the guard returns.

This is the same shape as min_rate — implement it from scratch.

Complexity: O(n log m) where n is the number of piles and m is max(piles). Each binary search iteration is O(n); there are O(log m) iterations.