Description
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, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.
Examples
nums = [5,7,7,8,8,10], target = 8[3,4]In the sorted array [5,7,7,8,8,10], target 8 appears twice. Binary search for leftmost 8: check mid=2 (value 7), go right. Check mid=4 (value 8), go left to find first. First 8 at index 3. Binary search for rightmost 8: check mid=2, go right. Check mid=4, go right to find last. Last 8 at index 4. Result: [3,4].
nums = [], target = 0[-1,-1]An empty array has no elements to search. Since target 0 cannot exist in [], the algorithm immediately returns [-1,-1] without any binary search operations.
nums = [2,2,2,2,2], target = 2[0,4]When all elements in the array are the same and match the target, the first position is 0 and the last position is the length-1 (4 in this case).
Constraints
- •
0 ≤ nums.length ≤ 10⁵ - •
-10⁹ ≤ nums[i] ≤ 10⁹ - •
nums is sorted.