Binary Search & Search on the Answer

Binary search finds an item among a billion in about 30 steps. Its bigger idea, searching over the answer itself, solves optimisation problems that look nothing like searching.

intermediate⏱ 14 min read

←Builds on

2Comparators & StabilityBinary search needs sorted data, and lower_bound takes the same comparator as std::sort.0Big-O & Growth RatesHalving the range every step is exactly where O(log n) comes from.

Leads to→

5Binary Search TreeSearching a BST is binary search frozen into the shape of a tree.5Fenwick Tree (Binary Indexed Tree)Like binary search, every step works with powers of two, so update and query take O(log n).

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Halve the search space

In a sorted array, look at the middle element. If it is the target, done. If it is smaller than the target, the target can only be to the right; if larger, only to the left. Either way, one comparison throws away half of the remaining elements.

Keep an interval [lo, hi] with the invariant "if the target exists, it is inside [lo, hi]". Each step: mid = lo + (hi − lo) / 2, compare, and move lo to mid + 1 or hi to mid − 1. When lo > hi, the interval is empty and the target is not there.

16 → 8 → 4 → 2 → 1: n elements need about log₂ n steps. For 10⁹ elements that is 30.

02Think in predicates: lower_bound

The most useful form of binary search is not "find x" but "find the first position where a condition becomes true".

On a sorted array, the condition a[i] ≥ x is false, false, …, false, true, true, …, true. Binary search finds the boundary: that is lower_bound(x). Similarly upper_bound(x) is the first a[i] > x, so the number of copies of x is upper_bound − lower_bound.

Writing it this way avoids most bugs:

lo = 0, hi = n; while lo < hi: mid = (lo + hi) / 2; if cond(mid) then hi = mid else lo = mid + 1. At the end lo is the first true (or n if none).

Classic pitfalls: an infinite loop when lo never moves, off-by-one on hi, and (lo + hi) overflowing int on huge ranges.

03Binary search on the answer

Sometimes there is no array at all. Instead you are asked for the smallest value that works: the least time, the minimum capacity, the slowest speed that still finishes.

If you can write can(t), "is t enough?", and it is monotone (once t works, every larger t works too), then the answers form F F F … T T T. Binary search over t finds the first T.

Example: machines need 3, 2 and 5 seconds per product. In time t they make ⌊t/3⌋ + ⌊t/2⌋ + ⌊t/5⌋ products. Is t enough for 7? t = 7 gives 6 (no), t = 8 gives 7 (yes): the answer is 8.

Each check here is O(number of machines), and the search needs log₂(range) checks, about 60 even for answers up to 10¹⁸.

04Recognising the pattern

Reach for binary search when:

the data is sorted (or you can sort it once and then answer many queries)
the problem says "minimum maximum", "maximum minimum", "least time such that", "smallest k such that"
checking a candidate answer is easy, but constructing the best answer directly is hard

The checklist for search on the answer: define can(x), prove it is monotone, pick lo (surely bad or smallest possible) and hi (surely good), then search. Use 64-bit integers for the range.

When the sorted data changes (inserts, deletes), keep it in an ordered set or map instead, which offers the same lower_bound in O(log n). And if you only need membership with no order, a hash set is O(1).

Cost at a glance

Search in a sorted arrayO(log n)

lower_bound / upper_boundO(log n)

Search on the answerO(log(range) · check)

Sort once, then q queriesO((n + q) log n)

Remember

Each comparison discards half of [lo, hi], so a sorted array of n elements needs about log₂ n steps.
Frame it as "first index where a monotone condition is true" to get lower_bound right every time.
If can(x) is monotone, binary search over x finds the optimal answer without constructing it.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the live interval [lo, hi] shrink by half on every probe. Try a target that is missing to see lo cross hi.

Interactive visualizerfocus here, then space ← →

Sorted array: searching for 31

Search for 31 in a SORTED array of 10 elements. The invariant: if 31 exists, it lies inside [lo, hi].

Pseudocode

 1 lo = 0; hi = n-1 2 while lo <= hi: 3   mid = (lo + hi) / 2 4   if a[mid] == x: return mid 5   if a[mid] <  x: lo = mid + 1 6   else:           hi = mid - 1 7 return -1  // not present

1 / 1

Check

Three questions. Pick an answer to see why.

a = [2, 4, 4, 4, 7, 9]. What does lower_bound(4) return (0-based)?

About how many probes does binary search need on a sorted array of 1 000 000 elements in the worst case?

Find the smallest daily capacity to ship packages within D days. Why does binary search on the capacity work?

Practice

Real problems to lock it in, easiest first.

LeetCodeBinary Search beginner↗LeetCodeFind First and Last Position of Element in Sorted Array intermediate↗LeetCodeKoko Eating Bananas intermediate↗CSESFactory Machines intermediate↗CSESArray Division advanced↗