Binary Search Variants
01 / The one-sentence essence
On a sorted sequence, halve the range on every step — the predicate you check at mid decides which boundary you find: any match, the first, or the last.
Problemfind target in a sorted arrayInput[1, 3, 3, 5, 7, 7, 7, 9, 11]target11modeexact
10
31
32
53
74
75
76
97
118
Sorted input, target 11. Place lo at 0 and hi at n−1 — closed interval [lo, hi].
step
0 / 8
lo · mid · hi
—
range size
—
result
—
0 / 8
02 / The pattern signature
# exact match — closed interval [lo, hi]lo ← 0; hi ← n − 1while lo ≤ hi:mid ← lo + (hi − lo) / 2 // avoid overflowif arr[mid] = target: return midif arr[mid] < target: lo ← mid + 1else: hi ← mid − 1# leftmost — half-open [lo, hi); replace strict-less with non-strict-less# rightmost — half-open [lo, hi); use arr[mid] ≤ target, return lo − 1
03 / When to recognize this pattern
"sorted"
The input is sorted or can be transformed to behave that way. Sortedness is what makes the discard-half step valid.
"O(log n)"
The expected complexity hints at halving — most other tools won't hit log time.
"first / last occurrence"
You need to find a boundary, not just any match — reach for leftmost / rightmost (lower_bound / upper_bound).
"on the answer"
The answer is a number, and you can check "does some predicate hold for this value?" The set of valid answers is monotonic in the value — binary-search the value, not an index.
04 / Common pitfalls
i.
Integer overflow on
(lo + hi) / 2.For large arrays in languages with fixed-width ints,
lo + hi can overflow. Use lo + (hi − lo) / 2 instead — same midpoint, no overflow.ii.
Mixing closed
[lo, hi] with half-open [lo, hi).Pick one convention per problem and stick to it. The loop condition (
≤ vs <) and the boundary updates (mid − 1 vs mid) must agree, or you get off-by-ones or infinite loops.iii.
Infinite loop on a range that won't shrink.
If your boundary update can leave
lo and hi unchanged on some branch, the loop spins forever. Each branch must strictly shrink the range — verify on paper for the edge case where lo = hi.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. The first two are vanilla binary search; the third is the leftmost/rightmost variant; the fourth lifts you to "binary-search-on-answer" thinking.