Find First and Last Position of Element in Sorted Array: Binary Search That Refuses to Stop

Classic binary search answers one question: is the target here, and at what index? This problem — LeetCode 34 — breaks that habit on purpose. The array is sorted but full of duplicates, and you need the entire range the target occupies: its first index and its last. And you must do it in O(log n).

The trap is that vanilla binary search returns the first match it happens to land on, which could be anywhere inside a run of duplicates. Search for 8 in [5, 7, 7, 8, 8, 10] and mid might land on index 3 or index 4 — you have no control over which. Returning that index answers "is 8 present?" but not "where does the block of 8s start and end?"

The fix is one deliberate change to the algorithm: when you find the target, don't return — record the index and keep searching toward the boundary you want. Run that modified search twice, once leaning left and once leaning right, and you get both edges in two logarithmic passes.

The problem#

Given an integer array nums sorted in non-decreasing order and an integer target, return the starting and ending position of target. If target is not in the array, return [-1, -1]. Required runtime: O(log n).

Two constraints shape everything:

• Duplicates are the whole point. If every value were unique, first and last would be the same index and one ordinary binary search would finish the job.
• O(log n) is mandatory. Any solution that walks along the duplicate run element by element can be forced into linear time, and interviewers will force it.

The brute force baseline#

Scan once, note the first time you see the target and the last time.

This is correct and O(n) — and it completely ignores the fact that the array is sorted. On a 10⁶-element array you touch a million entries to locate a block you could have pinned down in about 20 comparisons. Sorted input is a gift; a linear scan throws it away.

A tempting "improvement" is to binary search for any occurrence, then expand outward with two while-loops until the values change. That looks logarithmic but isn't: if the array is [8, 8, 8, ..., 8] and the target is 8, the expansion walks the entire array. Worst case O(n) — the duplicates that make the problem interesting are exactly what break this shortcut.

The key insight: search for a boundary, not a match#

This is the boundary binary search pattern. Reframe the goal: you're not looking for the target, you're looking for the edge of the target's block.

Ordinary binary search has three outcomes at each mid: too small (go right), too big (go left), found (stop). Boundary search changes only the third case. Finding the target tells you a boundary exists at mid or beyond it in one direction — so record mid as your best answer so far, then keep halving in that direction:

• Hunting the first position? A match at mid means the leftmost occurrence is at mid or somewhere left of it. Save mid, then set right = mid - 1 and keep looking left.
• Hunting the last position? Save mid, then set left = mid + 1 and keep looking right.

The loop still discards half the range every iteration — the O(log n) guarantee is untouched. The saved index simply tracks the best boundary candidate seen so far; when the window empties, that candidate is the boundary. One search leaning left plus one leaning right gives both edges: 2 × O(log n) = O(log n).

The optimal solution#

One helper, parameterized by direction. searchLeft = true biases every match toward the left edge; false biases toward the right.

Three details carry the correctness:

• boundary starts at -1, so a target that never appears returns [-1, -1] with zero special-casing.
• On a match, the found index is excluded from the next window (mid - 1 / mid + 1). That's safe because boundary already remembers it — and it's what guarantees the loop shrinks and terminates.
• The two non-match branches are untouched classic binary search. The entire pattern is one extra line in the equality case.

You can step through it interactively and watch the left-boundary pass drag right down while the right-boundary pass drags left up.

Walkthrough: nums = [5, 7, 7, 8, 8, 10], target = 8#

Pass 1 — left boundary (searchLeft = true):

Pass 2 — right boundary (searchLeft = false):

Result: [3, 4]. Step 2 of pass 1 is the moment that defines the pattern: the search finds an 8 at index 4 and a classic binary search would return right there — one index into the block, boundary unknown. Instead it banks the index and keeps pressing left, and one step later finds the true first position at 3.

Complexity#

Both passes together cost about 2 log₂ n comparisons — roughly 40 for a million elements — and only three integer variables per pass.

Common mistakes#

• Returning on the first match. nums[mid] === target means the target exists, not that mid is an edge. The one-line fix — save and continue — is the entire pattern.
• Expanding linearly from a found index. Feels clever, silently O(n). Any input that is mostly the target defeats it. If the follow-up says O(log n), expansion is an automatic fail.
• Shrinking the wrong side after a match. Writing left = mid + 1 in the left-boundary pass hunts the last occurrence instead of the first. Anchor the rule: chasing the first position → move right down; chasing the last → move left up.
• Mixing loop templates. This solution uses inclusive bounds: right = nums.length - 1 with while (left <= right) and mid ± 1 updates. Borrowing right = mid from the half-open template (while (left < right), right = nums.length) creates infinite loops. Pick one template per function and commit.
• Hand-rolling the absent-target case. No occurrence means the equality branch never fires, so boundary stays -1 and [-1, -1] falls out naturally. Extra existence checks are places to plant bugs.

Where this pattern shows up next#

Boundary search is the second binary-search skill you need after the plain lookup — and the Binary Search track builds toward and past it:

• Binary Search — the classic exact-match template this problem deliberately modifies; be fluent there first.
• Guess Number Higher or Lower — the same halving loop driven by an API's feedback instead of direct array reads.
• Sqrt(x) — another "track the best candidate so far" search, this time over the answer space of integers rather than array indices.
• Search in Rotated Sorted Array — binary search surviving a structural twist: the array is sorted, but in two rotated pieces.

Master the save-and-keep-searching move here and lower-bound/upper-bound style problems — insert positions, counting occurrences, first-true-in-a-monotonic-predicate — all collapse into the same template.

FAQ#

Why can't I binary search once and expand outward to find the range?#

Because the expansion step is linear in the size of the duplicate run. If nums = [8, 8, 8, 8, 8] and target = 8, the two expanding while-loops visit every element, making the whole algorithm O(n) — no better than a scan. The problem's O(log n) requirement exists precisely to rule this out. Two boundary binary searches keep every iteration halving the window, duplicates or not.

What is the time complexity of the two-binary-search solution?#

O(log n) time and O(1) space. Each of the two passes is a standard binary search that discards half its window per iteration — the only change is that a match records the index instead of returning, and the window still shrinks by at least one. Two passes of log₂ n comparisons is still O(log n); the constant factor is 2.

What does searchRange return when the target is not in the array?#

[-1, -1], and it happens without any explicit check. Each pass initializes boundary = -1 and only overwrites it inside the nums[mid] === target branch. If the target never appears, that branch never runs, both passes return -1, and the result is [-1, -1] — including for an empty array, since the loop condition left <= right fails immediately.

How is this different from lower_bound and upper_bound?#

Same idea, different packaging. lower_bound(target) (Python's bisect_left) returns the first index with nums[i] >= target, and lower_bound(target + 1) - 1 gives the last occurrence — so the problem can be solved with two lower-bound calls and one existence check. The findBoundary(searchLeft) helper in this article computes first/last occurrence directly and returns -1 when absent, trading the generic library shape for a self-contained version that needs no post-check.

Why does the loop keep running after finding the target?#

Because finding the target only proves an occurrence exists at mid — it says nothing about whether mid is the edge of the block. The leftmost occurrence could sit anywhere left of mid, so the search saves mid as its best candidate and continues on that side. When the window empties, no better candidate exists, so the saved index is provably the boundary. Stopping early is the difference between answering "does it exist?" and "where does the block start?"