AlgoMaster Logo

Find First and Last Position of Element in Sorted Array

Last Updated: March 29, 2026

medium
3 min read

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 tricky part is not just finding the target, but finding its exact boundaries. A standard binary search tells you "yes, the target is here" but doesn't tell you where the range of that target starts and ends. Consider [5, 7, 7, 8, 8, 10] with target 8. A regular binary search might land on either index 3 or 4, but we need both.

The key observation is that we need two separate searches: one to find the leftmost (first) occurrence, and one to find the rightmost (last) occurrence. Both can be done with modified binary search. The leftmost occurrence is the "lower bound" (first index where nums[i] >= target), and the rightmost occurrence is related to the "upper bound" (first index where nums[i] > target, then subtract 1).

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 → Full integer range. No special handling needed, but be careful with overflow in mid calculation.

Approach 1: Linear Scan

Intuition

The simplest approach: scan the array from left to right to find the first occurrence, then scan from right to left to find the last occurrence. No tricks, no binary search, just straightforward iteration.

This doesn't meet the O(log n) requirement, but it's the natural starting point and it helps us understand what the binary search needs to accomplish.

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 works but doesn't meet the O(log n) requirement. Since the array is sorted, we can use binary search to find both boundaries without scanning every element.

Approach 2: Two Binary Searches

Intuition

The array is sorted, so binary search is the natural tool. But a standard binary search just finds "some" occurrence of the target. We need the first and last. The insight is to run two modified binary searches:

  1. Find the first occurrence (lower bound): We're looking for the smallest index where nums[i] >= target. If nums[i] at that index equals the target, that's our first position.
  1. Find the last occurrence (upper bound - 1): The upper bound is the smallest index where nums[i] > target. The last occurrence of the target is one position before that.

Both searches use the same binary search skeleton with a small twist in the comparison. For the lower bound, we move right = mid when nums[mid] >= target (because mid could be the first occurrence). For the upper bound, we move left = mid + 1 when nums[mid] <= target (because mid could still be the target, so the boundary is 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