Find First and Last Position
Module 13 · Binary Search
Problem
Given a sorted array (duplicates allowed) and a target, return
[first index, last index] of target's occurrences, or [-1, -1] if
absent — in O(log n).
Examples
Example 1
Input
nums = [5,7,7,8,8,10], target = 8Output[3, 4]Example 2
Input
nums = [5,7,7,8,8,10], target = 6Output[-1, -1]Example 3
Input
nums = [], target = 0Output[-1, -1]Constraints
0 ≤ n ≤ 10⁵.
Attempt it first
The two-sided version of the boundary-search lesson: find where target STARTS and where it ENDS, each its own binary search. The tempting shortcut — find target once, then scan outward — breaks the O(log n) requirement (a run of equal values can be O(n) long). Two independent boundary searches are the only way to keep the guarantee.