One binary search finds an occurrence. To pin down the edges of a run of duplicates, don't stop when you find it — keep leaning toward the boundary.
Given a sorted array and a target, return the first and last index where the target appears,
or [-1,-1] if it's absent. For [5,7,7,8,8,10], target 8 →
[3,4]. The hard constraint is O(log n), which rules out a linear scan and points
straight at binary search.
The whole trick is a single tweak to standard binary search. When nums[mid] == target, save the
index but keep searching in one direction: left for the first occurrence, right for the last.
right = mid − 1 — there might be an earlier copy.left = mid + 1 — there might be a later copy.[2,2] for [2,2,2,2,2] instead of
[0,4]. And "find one, then scan outward" is O(n) in the worst case — a solid run of duplicates
defeats the log-n requirement.
Like finding a friend in a crowd and then edging left to reach the very front of their group — you don't stop at the first hello.
Rewrite the array as "is this ≥ target?" — it reads F F F T T T. Binary search just hunts the single place where false turns to true.
Left and right pointers are walls sliding inward, halving the room each step until they pin the boundary between them.
Pick First or Last, set a target, and step through. The left and right walls bracket the live range; mid is checked each step. On a match the index is saved (teal ring) and the search leans onward; the final boundary locks in solid teal.
Reframe each occurrence as a boundary in a boolean array. The first occurrence is the first
index where nums[i] ≥ target (the lower bound). One past the last occurrence is
the first index where nums[i] > target (the upper bound). So last = upperBound − 1.
Above: nums[i] ≥ target for
[5,7,7,8,8,10], target 8 → the first T is the answer's left edge. Flip the test to
> and the first T marks one-past-the-end. A neat bonus:
count = upperBound − lowerBound.
int[] searchRange(int[] nums, int target) { return new int[]{ find(nums, target, true), find(nums, target, false) }; } int find(int[] nums, int target, boolean first) { int lo = 0, hi = nums.length - 1, ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids overflow if (nums[mid] == target) { ans = mid; // candidate — keep leaning if (first) hi = mid - 1; else lo = mid + 1; } else if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return ans; }
Two O(log n) searches run back to back — still O(log n), because sequential (not nested) log-n work just adds:
2 log n = O(log n). Space is O(1). The empty array needs no special case: lo=0, hi=−1
skips the loop and returns −1.
When binary search misbehaves, a trace table exposes it fast — log each step's window and decision:
| left | mid | right | nums[mid] | Action |
|---|---|---|---|---|
| 0 | 2 | 5 | 7 | 7 < 8 → left = 3 |
| 3 | 4 | 5 | 8 | match → save 4, right = 3 |
| 3 | 3 | 3 | 8 | match → save 3, right = 2 |
Loop ends with left > right; the last saved index, 3, is the first occurrence.
The last-occurrence search is identical but leans right, landing on 4.
First occurrence must go right = mid − 1. Writing left = mid + 1 walks away from
the boundary. Memory hook: first leans left, last leans right.
Find one, then walk to both ends — looks clever, but [8,8,…,8] makes it O(n). Use binary
search for both edges.
(lo+hi)/2 can overflow. Prefer lo + (hi−lo)/2 — the standard safe form.
lo ≤ hi with inclusive bounds, or lo < hi with a half-open
[lo,hi). Don't mix pieces of different templates.
The real generalization: binary search locates the flip point in any monotonic search space — anywhere a condition goes F…F T…T. "Find a value in a sorted array" is just the simplest case. Once you see it as boundary-finding, a whole family opens up: