34. Find First and Last Position of Element in Sorted Array
You are given an integer array nums sorted in non-decreasing order (it may be empty) and an integer target. Because values can repeat, target may occupy a whole block of consecutive positions.
Return the pair (first, last) — the 0-based indices of the first and the last occurrence of target in nums. If target never appears, return (-1, -1).
Since the array is sorted, aim for O(log n) time rather than a linear sweep.
Example 1:
Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]
Explanation: The 8s form the block at indices 3 and 4, so the boundaries are (3, 4).
Example 2:
Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]
Explanation: 6 never appears, so both boundaries are -1.
Constraints:
- 0 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
- nums is sorted in non-decreasing order
- -10⁹ ≤ target ≤ 10⁹
Hints:
Equal values sit in one contiguous block in a sorted array, so you only need the block's two edges — not every occurrence.
Write one helper: the smallest index whose value is >= x (a lower bound). Run it for target to get the left edge.
The right edge falls out of the same helper for free: it is lowerBound(target + 1) - 1. Two binary searches total.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Expected output: [3, 4]