Find First and Last Position

Difficulty: Medium

Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

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.

Brute-force approach

Scan the array from left to right to find the first occurrence, then scan from right to left (or continue forward) to find the last occurrence.

Steps

  1. Scan left to right to find the first index where nums[i] == target
  2. Scan right to left to find the last index where nums[i] == target
  3. If not found in either scan, return [-1, -1]

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Scans the entire array in the worst case — O(n)
  • Doesn't use the sorted property at all
  • Two full passes through the array

Optimal approach

Key insight: Standard binary search stops when it finds the target. To find the FIRST occurrence, keep searching LEFT even after finding it. To find the LAST, keep searching RIGHT.

Run two binary searches: one modified to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence of the target.

Steps

  1. findLeft: Binary search where matches push search LEFT
  2. findRight: Binary search where matches push search RIGHT
  3. Return [findLeft, findRight]

Time complexity: O(log n) · Space complexity: O(1)