Find First and Last Position of Element in Sorted Array Solution

Problem

Given a sorted array of integers that may contain duplicates, return the first and last index where a target value appears. All copies of the target form a contiguous block because the array is non-decreasing.

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]
Explanation: 8 first appears at index 3 and last appears at index 4.

Counter-example: if target = 6, return [-1, -1] — 6 is not in the array.

Intuition

Because the array is sorted, all occurrences of the target sit side-by-side. A linear scan can locate both boundaries in O(n), but the sorted property lets us do much better: we can run two binary searches independently — one biased to keep searching left when a match is found (to reach the leftmost copy) and one biased right (to reach the rightmost copy).

Approach 1 — Linear Scan

Walk the array once from left to right. Record the index of the first match and keep overwriting with each subsequent match so the last update holds the rightmost position.

Steps:

Initialize first_pos = -1 and last_pos = -1.
Iterate over every index i.
When nums[i] == target, set first_pos = i only if it is still -1 (captures the first occurrence).
Set last_pos = i on every match — the final overwrite lands on the rightmost occurrence.
Return [first_pos, last_pos].

1def searchRange(nums: list[int], target: int) -> list[int]:
2    first_pos = -1
3    last_pos = -1
4    for i in range(len(nums)):
5        if nums[i] == target:
6            if first_pos == -1:
7                first_pos = i  # freeze on the very first match
8            last_pos = i       # keep updating so final value is rightmost
9    return [first_pos, last_pos]

Time: O(n) — every element is visited once regardless of where the target appears.
Space: O(1) — only two integer variables.

Approach 2 — Two Binary Searches

Run two independent binary searches: one that continues searching left whenever it finds a match (to pin the leftmost index), and a mirror that continues right (to pin the rightmost index).

Steps:

In find_leftmost: perform standard binary search; when nums[mid] == target, record mid as the current best answer and set high = mid - 1 to continue left.
In find_rightmost: mirror — when nums[mid] == target, record mid and set low = mid + 1 to continue right.
Each helper returns -1 if the target is never found.
Return [find_leftmost(), find_rightmost()].

1def searchRange(nums: list[int], target: int) -> list[int]:
2    def find_leftmost() -> int:
3        low, high, leftmost = 0, len(nums) - 1, -1
4        while low <= high:
5            mid = (low + high) // 2
6            if nums[mid] == target:
7                leftmost = mid      # record and keep narrowing left
8                high = mid - 1
9            elif nums[mid] < target:
10                low = mid + 1
11            else:
12                high = mid - 1
13        return leftmost
14
15    def find_rightmost() -> int:
16        low, high, rightmost = 0, len(nums) - 1, -1
17        while low <= high:
18            mid = (low + high) // 2
19            if nums[mid] == target:
20                rightmost = mid     # record and keep narrowing right
21                low = mid + 1
22            elif nums[mid] < target:
23                low = mid + 1
24            else:
25                high = mid - 1
26        return rightmost
27
28    return [find_leftmost(), find_rightmost()]

Time: O(log n) — two independent binary searches, each halving the search space each step.
Space: O(1) — no extra data structures beyond a few integer variables.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Small arrays or when the array may not be sorted
Two Binary Searches	O(log n)	O(1)	Standard choice — exploits the sorted guarantee the problem guarantees

Common Mistakes

Stopping at the first match in binary search: A standard binary search returns some occurrence but not necessarily the leftmost or rightmost. You must continue narrowing the range after a match — that's the entire trick.
Updating the bound without first saving the current index: In the leftmost search, setting high = mid - 1 before storing leftmost = mid discards the answer when the loop ends on that iteration.
Thinking one binary search can find both bounds: A single pass cannot simultaneously bias left and right; the two-search structure is deliberate, not redundant.
Integer overflow in mid calculation: (low + high) / 2 overflows when both values are near INT_MAX in Java and C++; low + (high - low) / 2 is the safe equivalent.
Not initializing the result to -1: If the target is absent, the helper must return -1. Defaulting to 0 would falsely report index 0 as a valid occurrence.

Find First and Last Position of Element in Sorted Array — Solution