AlgoMaster Logo

Find First and Last Position of Element in Sorted Array

medium5 min readUpdated June 23, 2026

Understanding the Problem

We have a sorted array that may contain duplicates, and we need to find where a target value first appears and where it last appears. If it doesn't exist at all, we return [-1, -1].

The difficulty is not finding the target, but finding its exact boundaries. A standard binary search confirms the target is present but stops at an arbitrary matching index. Consider [5, 7, 7, 8, 8, 10] with target 8. A regular binary search could return either index 3 or 4, while we need both.

This calls for two separate searches: one to find the leftmost (first) occurrence, and one to find the rightmost (last) occurrence. Both are variations on binary search. The leftmost occurrence is the "lower bound", the first index where nums[i] >= target. The rightmost occurrence is one position before the "upper bound", the first index where nums[i] > target.

Key Constraints:

  • 0 <= nums.length <= 10^5 → The array can be empty (n = 0), which is an edge case. With up to 100,000 elements, O(n) would pass but the problem explicitly requires O(log n).
  • nums is a non-decreasing array → "Non-decreasing" means duplicates are allowed. This is the whole point of the problem: there can be many copies of the target.
  • -10^9 <= nums[i] <= 10^9 → Values fit in a 32-bit integer. The midpoint is computed as left + (right - left) / 2 rather than (left + right) / 2 to avoid integer overflow when the indices are large.

Approach 1: Linear Scan

Intuition

Scan the array from left to right to find the first occurrence, then scan from right to left to find the last occurrence. The first match in each direction is a boundary.

This does not meet the O(log n) requirement, but it establishes what the binary search version needs to produce: the leftmost and rightmost matching indices.

Algorithm

  1. Initialize first = -1 and last = -1.
  2. Scan left to right: when you find nums[i] == target, set first = i and break.
  3. Scan right to left: when you find nums[j] == target, set last = j and break.
  4. Return [first, last].

Example Walkthrough

1Start left-to-right scan: looking for first occurrence of 8
0
5
i
1
7
2
7
3
8
4
8
5
10
1/4

Code

The linear scan is O(n), which violates the required O(log n). Because the array is sorted, binary search can locate both boundaries without examining every element.

Approach 2: Two Binary Searches

Intuition

A standard binary search returns an arbitrary occurrence of the target. To get both ends, run two boundary searches:

  1. Find the first occurrence (lower bound): the smallest index where nums[i] >= target. If the value there equals the target, that index is the first position.
  1. Find the last occurrence (upper bound - 1): the upper bound is the smallest index where nums[i] > target, so the last occurrence is one position before it.

Both searches share the same skeleton and differ only in the comparison. For the lower bound, move right = mid when nums[mid] >= target, since mid itself could be the first occurrence. For the upper bound, move left = mid + 1 when nums[mid] <= target, since mid could still equal the target and the boundary lies farther right.

Algorithm

  1. Run a lower bound binary search to find first: the smallest index where nums[i] >= target.
  2. If first is out of bounds or nums[first] != target, the target doesn't exist. Return [-1, -1].
  3. Run an upper bound binary search to find the smallest index where nums[i] > target. Subtract 1 to get last.
  4. Return [first, last].

Example Walkthrough

1Lower Bound Search: left=0, right=6, find first index >= 8
0
5
left
1
7
2
7
3
8
4
8
5
10
search range
1/7

Code