Binary search — beyond find-an-element

Most people learn binary search as 'find a number in a sorted list'. That's level one. The deeper power comes when you realise binary search applies to ANY decision space where the answer is monotonic.

Monotonic means — once a value satisfies your condition, all larger values do too (or all smaller, depending on direction). The condition flips exactly once across the range, and you binary-search that flip point.

Examples that don't look like 'sorted array search':

Find the smallest x such that f(x) is true. The classic 'first true' problem. As long as f is monotonic — false, false, false, true, true, true — binary search finds the boundary in O(log n).

Find the largest k such that we can fit k items. Capacity problems, scheduling problems. Try k; if it fits, try larger; if it doesn't, try smaller.

Find the minimum capacity that achieves target throughput. Try a capacity, simulate, check if target met. Adjust binary-style.

This is the 'binary search the answer' technique. The search space isn't the input array — it's the space of possible answers. The condition function is whatever 'is this answer feasible' looks like. The runtime is O(log(range) * cost_of_feasibility_check).

Real-world examples in ML — find the smallest learning rate that doesn't diverge. Find the largest batch size that fits in GPU memory. Find the threshold that gives target precision. All of these have monotonic feasibility.

The pattern beats brute-force linear search by orders of magnitude when the search space is large. log(10^9) is 30. Linear scan of 10^9 is forever. Same correctness, vastly faster.

Know this and you'll spot binary-search problems where most people don't.

Python's standard library has a binary-search module: bisect. Most developers either don't know it or roll their own. Don't roll your own.

bisect_left(arr, target) returns the index where target would be inserted to keep arr sorted, with target inserted BEFORE any equal entries. If target equals arr[i], it returns i.

bisect_right(arr, target) does the same but inserts AFTER any equal entries. If target equals arr[i], it returns i+1.

When to use which:

Find the index of target in a sorted array — bisect_left. If arr[bisect_left(arr, target)] == target, found. Otherwise, not present.

Insert target while keeping the array sorted — bisect.insort(arr, target). Internally uses bisect to find the position, then list.insert. O(log n) for the search, O(n) for the insert (shifting elements). Total O(n), but in tight loops the search portion saves time vs linear scan.

Count items in [low, high) range — bisect_right(arr, high) - bisect_left(arr, low). Sweet trick for range counts on a static sorted array.

Find first element ≥ target — bisect_left.
Find first element > target — bisect_right.

Don't roll your own binary search if bisect fits. It's correct, it's in C inside CPython, and millions of users have hammered on it. Hand-rolled binary searches are a notorious source of off-by-one bugs (more on this in the evening post).

The few cases where you DO need a custom search — when you're searching the answer space (yesterday's morning concept), where the 'array' is conceptual and you're calling a feasibility function. Then you write the loop yourself.

For sorted arrays — bisect.

Classic interview problem — given weights of packages and D days, find the minimum capacity that ships all packages within D days. Each day's load is a contiguous prefix of the remaining packages.

Naive — try every capacity. Slow. Capacities range from max(weights) to sum(weights), which could be enormous.

Key insight — the feasibility function is monotonic. If capacity C works, any capacity > C also works (you can always pack less per day). So we binary-search the capacity.

Look at the snippet. The feasible function takes a capacity, simulates the packing day by day, and returns whether it finishes within D days.

The outer loop is binary search. lo = max(weights) (must fit largest single package), hi = sum(weights) (always works in 1 day). We find the smallest capacity that's feasible.

Logic — if mid is feasible, the answer is at most mid; set hi = mid. If not feasible, the answer is at least mid+1; set lo = mid+1. Stop when lo == hi.

Return lo (which equals hi at termination) — that's the smallest feasible capacity.

Complexity — O(log(sum) * n) where sum is the search range and n is the number of packages. log(sum) is ~30 for typical inputs. n is the simulation cost per check. Total is barely worse than a single linear pass.

This pattern — feasibility(x) is monotonic, binary-search for the smallest feasible x — is one of the most powerful tools in DSA. Once you can spot it, you'll see it everywhere — rate limiters, capacity planners, hyperparameter tuning bounds, k-means initialisation seeds.

The code is small. The conceptual leap (binary search the ANSWER, not the array) is the unlock.

The two binary-search bugs that cause 90% of failures, and the canonical template that avoids both.

Bug one — wrong loop condition. 'while lo < hi' versus 'while lo <= hi'. Choose based on whether your range bounds are inclusive or exclusive.

Bug two — wrong update. 'lo = mid' instead of 'lo = mid + 1' creates an infinite loop when mid hits the boundary value.

Both bugs come from inconsistent invariants. The fix is to pick ONE invariant and stick to it religiously.

My template — half-open ranges. lo is inclusive (the smallest possible answer is at lo or higher). hi is exclusive (the answer is strictly less than hi). Range is [lo, hi).

Loop condition — while lo < hi. (When lo == hi, the range is empty, we stop.)

Update — either lo = mid + 1 or hi = mid. Never lo = mid (would loop forever) or hi = mid - 1 (would skip the answer).

Return — lo (which equals hi at termination).

This template handles every binary-search variant correctly:

First element ≥ target — feasible(x) means arr[x] >= target. Find smallest feasible.

First element > target — feasible(x) means arr[x] > target. Find smallest feasible.

Binary-search the answer — feasible(x) is the monotonic condition. Find smallest feasible.

Memorise the four lines:

lo, hi = ..., ... + 1
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid
    else: lo = mid + 1

Use this template every time. Stop debugging off-by-one. Most binary-search bugs are just inconsistency between the loop condition, the range semantics, and the update rule. Pick one set; stay consistent.

End of Day 23. Binary search done.

What we covered.

Morning, the realisation that binary search isn't just for sorted arrays — it's for any decision space where the answer is monotonic. Find the smallest capacity, find the largest k, find the threshold. Same pattern; the 'array' is conceptual.

Midday, Python's bisect module. Standard library, in C, used everywhere. bisect_left, bisect_right, insort. The patterns for find-target, sorted-insert, range-count.

Afternoon, the 'binary search the answer' technique on the ship-within-days problem. Feasibility is monotonic; binary-search the capacity; O(log(range) * n).

Evening, the canonical binary-search template. Half-open [lo, hi), while lo < hi, lo = mid+1 or hi = mid. Memorise this and stop fighting off-by-one bugs. Almost every binary-search bug is inconsistency in the invariants.

A broader theme. The 'binary search the answer' pattern is one of the most powerful pieces in the DSA toolkit. It comes up constantly in real ML/data work — sweep a learning rate, tune a threshold, pick a batch size. Recognising the pattern (monotonic feasibility) and reaching for it is the skill.

Tomorrow, Day 24, sorting. Why Python's default is timsort. When to use heapq instead of sorting. Stable vs unstable sorts and why stability matters. Plus the 'don't sort to compute one stat' tip that saves real time.

See you in the morning.