Find First and Last Position of Element in Sorted Array

Medium· binary search· lower bound

Problem

Given a non-decreasing array that may contain duplicates and a target, return the first and last index where the target appears. If the target is absent return [-1, -1]. The expected running time is O(log n).

Examples

Input: nums = [1,2,2,2,5,8], target = 2

Output: [1,3]

The run of 2s spans indices 1 through 3.

Input: nums = [1,2,2,2,5,8], target = 4

Output: [-1,-1]

Constraints

• 0 <= nums.length <= 10^5
• nums is sorted in non-decreasing order

Hints & approach

Hint 1

A single binary search that stops on any match cannot tell you where the run begins.

Hint 2

Run two searches: one for the first index >= target, one for the first index > target.

Hint 3

The last occurrence is one less than the second result.

Approachtry the hints first

Write one lower-bound helper that returns the first index whose value is >= x. The first occurrence is lowerBound(target); if that index is out of range or holds a different value, the target is missing. The last occurrence is lowerBound(target + 1) - 1, i.e. just before the first value strictly greater than the target. Two logarithmic searches keep the whole thing O(log n) even when the run of duplicates is huge.

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

← PreviousFirst Bad Version Next →Search in Rotated Sorted Array