Binary Search
Halving the search space — for exact matches, for boundaries, and for answers with no array at all
Binary search is the payoff for having sorted data. Each comparison discards half of what remains, so a billion candidates collapse to about 30 questions.
The idea is easy. Getting the boundaries right is not — which is why it deserves its own section.
Watch It Work
Three variables do everything. lo and hi mark the range that could still contain the answer; mid is the guess in the middle.
Why halving is so powerful
Each step cuts the problem in half, so the cost is how many times can you halve n before reaching 1 — that is log₂ n.
| Items | Steps needed |
|---|---|
| 10 | 4 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
A thousand-fold increase in data costs ten more steps. Almost nothing else in computing scales this well, which is why so much effort goes into keeping data sorted in the first place.
The prerequisite that is easy to forget
The array must be sorted by the thing you are comparing. Binary search on unsorted data does not crash and does not warn you — it confidently returns a wrong answer, because the assumption it relies on ("everything left of mid is smaller") is simply false.
If sorting first costs O(n log n) and you only search once, sorting was not worth it — a plain O(n) scan is cheaper. Sorting pays off when you will search many times.
Two Templates
Nearly every binary search you write is one of these, and mixing lines between them is the source of almost every bug.
Template 1 — exact match (inclusive bounds)
lo = 0, hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target: return mid
if a[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1Use it when you want to find a specific value. See Binary Search.
Template 2 — boundary / lower bound (exclusive upper bound)
lo = 0, hi = n ← note: n, not n - 1
while lo < hi: ← note: <, not <=
mid = lo + (hi - lo) // 2
if predicate(mid): hi = mid ← KEEP mid, it may be the answer
else: lo = mid + 1
return loUse it when you want the first position where something becomes true. See Search Insert Position and First Bad Version.
The asymmetry in template 2 is deliberate
hi = mid but lo = mid + 1.
A candidate that satisfies the predicate might be the first one, so it stays. A candidate that fails definitely is not the answer, so it goes. Making both symmetric either discards the answer or loops forever.
The Real Insight: Binary Search Without an Array
Template 2 does not need an array. It needs a monotonic predicate — one that is false, false, …, false, true, true, …, true over a range.
First Bad Version is the clearest example: there is no array, only version numbers and an API. The predicate "is this version bad?" is monotonic because every version after a bad one is also bad, and that is all binary search requires.
This unlocks a whole family of "binary search on the answer" problems: minimum capacity to ship packages in d days, smallest divisor under a threshold, minimum eating speed. In each, you binary-search the answer space and use a feasibility check as the predicate.
The Three Classic Bugs
All Problems
| Problem | Difficulty | Template |
|---|---|---|
| Binary Search | Easy | Exact match |
| Search Insert Position | Easy | Boundary |
| First Bad Version | Easy | Boundary, no array |
Related Elsewhere
- H-Index — the pre-sorted variant is a binary search
- Is Subsequence — binary search over position lists in the follow-up
- Merge Sorted Array — another algorithm that exists only because the input is sorted