Find First and Last Position of Element in Sorted Array

Problem

You are given an array of integers nums sorted in non-decreasing order and a value target. Return a two-element list [first, last] giving the smallest and largest indices at which target appears. If target is not present, return [-1, -1]. The running time should stay logarithmic even when every element equals target.

• nums may be empty and has at most 200,000 elements.
• Values and target are integers between -2,000,000,000 and 2,000,000,000.

Examples

• nums = [3, 6, 6, 6, 9, 14], target = 6 → [1, 3].
• nums = [3, 6, 6, 6, 9, 14], target = 10 → [-1, -1]; 10 is absent.
• nums = [4, 4, 4, 4, 4], target = 4 → [0, 4]. When the whole array is the target, a naive "find it then expand outward" approach degrades to O(n).

Hints

1. A standard binary search stops at any occurrence. Why is expanding from there to find the ends not O(log n)?
2. Rather than searching for the value, search for a boundary: the first index whose element is >= target.
3. Two lower-bound searches: one for target and one for target + 1. The second minus one is the last position.