Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
Return an array [first, last] where:
firstis the index of the first occurrence oftargetinnums.lastis the index of the last occurrence oftargetinnums.
If target is not found in nums, return [-1, -1].
Your algorithm must run in O(log n) time.
Example 1
Input
nums = [5,7,7,8,8,10], target = 8Output
[3,4]The target value 8 appears first at index 3 and last at index 4.
Example 2
Input
nums = [5,7,7,8,8,10], target = 6Output
[-1,-1]The target value 6 does not appear in the array, so both positions are -1.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is a non-decreasing array
- -10^9 <= target <= 10^9