1Understand
The idea
On sorted data, compare with the middle element and discard the half that cannot contain the answer, so n elements need about log₂ n steps. Most bugs come from the boundaries: decide whether you are looking for a value, the first position where a condition becomes true, or the last, and keep the loop invariant consistent with that choice.
Intuition
On sorted data, compare with the middle element and discard the half that cannot contain the answer. Roughly log₂ n steps beat a linear scan.
Most bugs come from boundaries: are you finding an exact value, the first position where a condition becomes true, or the last? Pick a loop invariant and stick to it; usually lo is inclusive, hi exclusive, or both inclusive with clear mid bias.
When duplicates exist, decide whether you want any hit or the leftmost/rightmost.
What you will be able to do
- Pick consistent bounds ([lo, hi) or [lo, hi])
- Find boundaries, not just equality
When to use it
- Sorted array and a target
- O(log n) required
- First or last occurrence, insertion point
- Rotated sorted array
2See it
Walkthrough
Find a value in sorted data
nums = [1, 3, 5, 7, 9, 11], target = 7, discard half each step.
1 / 6
Sorted nums, target 7. Invariant: answer lies in [left, right] if it exists.
Live template
Line 1 active
Complexity: time O(log n), space O(1)
O(log n) time, O(1) space. Linear scan is O(n), fine for tiny n, wrong for n ~ 10⁵ on a hot path. If the array is unsorted, binary search on indices does not apply (use binary search on the answer instead, or sort first).
Read the walkthrough as text
Lower bound. Sorted a = [1, 2, 2, 2, 4], find first index with a[i] >= 2.
- Invariant: answer is in
[lo, hi), startlo=0,hi=5. mid=2,a[2]=2is already≥ 2→ discard right half including? Keep mid as candidate:hi = mid.- Narrow until
lo == hi. Result index1.
In code:
lo, hi = 0, len(a)while lo < hi:mid = (lo + hi) // 2if a[mid] >= target:hi = midelse:lo = mid + 1return lo
3Recognise it
Kinds of problems (9)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Exact match
Example. Find target in a sorted array, or return −1.
How. Compare mid; discard the half that cannot contain target.
First / last position (lower and upper bound)
Example. First and last index of target in a sorted array with duplicates.
How. Lower bound: first index ≥ target. Upper bound: first > target. Same loop, different branch.
Insertion point
Example. Index where target would be inserted to keep order.
How. Same as lower bound: return lo when the loop ends.
Rotated sorted array
Example. Sorted array rotated at an unknown pivot; find target.
How. From mid, decide which half is sorted, then see which half can hold target.
Search a sorted 2-D matrix
Example. Matrix rows are sorted and stitch into one increasing sequence.
How. Binary search on the flattened index; map mid → (row, col).
Peak element
Example. Find an index whose value is greater than its neighbours.
How. Move toward the larger neighbour; a peak must exist in that direction.
Search on index parity (single element)
Example. Every element appears twice except one; find the single (sorted pairs).
How. Pairs sit on even-odd indices until the single breaks parity; binary search on that pattern.
Search for the start of a window (k closest)
Example. k closest values to x in a sorted array.
How. Binary search the leftmost start of a window of length k whose endpoints are closest to x.
Weighted random pick (prefix sums + search)
Example. Pick an index with probability proportional to its weight.
How. Build prefix sums of weights; draw r in [1, total] and lower-bound into the prefix.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Infinite loop
Why it happens. When lo and hi stay adjacent, `lo = mid` or `hi = mid` can freeze the window.
How it fails. lo = 0, hi = 1, mid = 0; setting lo = mid leaves lo == 0 forever.
Fix. With while lo < hi, use lo = mid + 1 on the “too small” branch (or hi = mid, 1 on inclusive schemes). Bounds must shrink every step.
Inconsistent bounds
Why it happens. Mixing [lo, hi] and [lo, hi) mid updates breaks the invariant.
How it fails. hi = len(a)−1 but you still do hi = mid on “too big”, skipping the last index forever.
Fix. Pick one convention and stick to it: either half-open [lo, hi) with hi = mid, or closed [lo, hi] with hi = mid, 1.
Wrong sorted half
Why it happens. In a rotated array only one side of mid is sorted; searching the other side blindly misses the target.
How it fails. a = [4,5,6,7,0,1,2], target = 0; discarding the right half because mid = 7 > 0 loses the only copy.
Fix. Check which half is sorted (compare a[lo] and a[mid]), then ask whether target lies in that sorted range.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.