Find First and Last Position of Element in Sorted Array
Find First and Last Position of Element in Sorted Array: return the starting and ending indices of a target value in a sorted array, or [-1, -1] if it is absent, in O(log n) time.
- 0 <= nums.length <= 10⁵
- -10⁹ <= nums[i] <= 10⁹
- nums is a non-decreasing array
- -10⁹ <= target <= 10⁹
Intuition
A plain binary search finds some occurrence, but which one it lands on is arbitrary, and expanding outward from it costs O(n) when the whole array is the target. The fix is to run two boundary searches instead: one that finds the leftmost position where the target could sit, and one that finds the position just past its last occurrence. Two O(log n) passes give both ends without ever scanning the run.
When a sorted array holds duplicates and a question asks about the extent of a value — its first index, last index, or count — the answer is two boundary searches. Counting occurrences is the same pair subtracted, which is the whole of Count of Occurrences.
Approach
Before reading on: work out why expanding outward from a found index breaks the time bound, and construct the input where it is worst. Then express the last occurrence in terms of a lower-bound search rather than a separate upper-bound one.
Why the naive find-then-expand fails the bound
After locating any occurrence, walking left and right to the edges of the run is correct but linear in the run's length. On an array of ten thousand identical values the expansion touches every element, so the total is O(n) and the required logarithmic bound is missed. The run's length is exactly what must not be traversed, which forces the boundaries themselves to be searched rather than discovered by scanning.
Two boundaries from one helper
Define lower_bound(x) as the first index whose value is at least x. Then the first occurrence of the target is lower_bound(target), and the index one past its last occurrence is lower_bound(target + 1) — because the first element exceeding the target begins immediately after the run ends. So the answer is [lo, hi - 1] where lo = lower_bound(target) and hi = lower_bound(target + 1). Writing one helper twice is far less error-prone than writing two subtly different searches, which is where most attempts introduce bugs.
Detecting absence, and the half-open interval
The target is missing precisely when lo == hi, meaning no element lies in [target, target + 1) — an empty run. That single test covers every absent case, including a target smaller than everything, larger than everything, or falling in a gap, so no separate bounds checks are needed. The helper itself uses lo = 0, hi = len(nums) with while lo < hi and hi = mid, keeping the interval half-open so that an answer of len(nums) remains representable. Two searches give O(log n) total with O(1) space.
Solution & live demo
Common pitfalls
Expanding outward after finding a match
while nums[i - 1] == target:
i -= 1start = lower_bound(target)
The expansion is linear in the run's length, so an array of identical values makes it O(n) and the required O(log n) is missed on exactly the input the problem is testing for.
Using hi = mid - 1 in the lower-bound helper
else:
hi = mid - 1else:
hi = midWhen nums[mid] equals the target, mid may itself be the first occurrence. Excluding it discards the answer and the search settles one position too far left.
Reporting absence with a bounds check on lo
if lo >= len(nums) or nums[lo] != target:
return [-1, -1]if start == end:
return [-1, -1]The bounds version works but duplicates logic the second search already computed. Comparing the two boundaries covers absence, an empty array, and out-of-range targets with one test and no indexing.
Edge cases
lo equals hi, so [-1, -1] is returned.
Both searches return 0, they are equal, and [-1, -1] follows.
lo is 0 and hi is n, giving [0, n - 1] without scanning the run.
hi is exactly lo + 1, so the range collapses to one index.
Both bounds land at len(nums) and are equal, so absence is reported.