Find First and Last Position

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 1

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

Explanation: 8 first appears at index 3, last at index 4.

Example 2

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

Explanation: 6 not found in array.

Example 3

Input: nums = [1], target = 1

Output: [0,0]

Explanation: Single element array; first and last are both index 0.

Constraints: 0 ≤ nums.length ≤ 10⁵ | −10⁹ ≤ nums[i], target ≤ 10⁹ | nums sorted in non-decreasing order

Array

Initializing

Variables

Phase

—

mid

—

nums[mid]

—

bound

—

Step Logic

Press ▶ Play or Next Step to begin the animation.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Run Search #1 (left bound): binary search, on match record bound=mid then continue left hi=mid−1

During left search: nums[mid] < target → lo=mid+1 | nums[mid] > target → hi=mid−1

Run Search #2 (right bound): on match record bound=mid then continue right lo=mid+1

Return [first, last]. Both are -1 if target not found.

Time

O(log n)

Space

O(1)

Why Two Searches?

A single binary search stops as soon as it finds the target — but there may be duplicates. By not stopping on the first match and instead recording the index and shrinking the search window toward the boundary, each search converges on the extreme position. Two passes of O(log n) remain O(log n) overall.