Find the starting and ending index of a target value in a sorted array.
Given a sorted integer array, find the first and last positions where a target value appears. If the target does not exist in the array, return [-1, -1].
Your solution should be efficient and better than a linear scan when possible.
Input Format
- An integer array
numssorted in non-decreasing order. - An integer
target.
Treat the array as zero-indexed.
Output Format
Return two integers [firstIndex, lastIndex] representing the leftmost and rightmost positions of target in nums. If target is absent, return [-1, -1].
Constraints
0 <= nums.lengthnumsis sorted in non-decreasing order- Values may repeat
- If no occurrence exists, return
[-1, -1]
Example 1
Input
nums = [5,7,7,8,8,10], target = 8
Output
[3,4]
Explanation
The value 8 appears first at index 3 and last at index 4.
Example 2
Input
nums = [5,7,7,8,8,10], target = 6
Output
[-1,-1]
Explanation
The target 6 does not appear in the array.
Show 1 more example
Example 3
Input
nums = [], target = 1
Output
[-1,-1]
Explanation
An empty array cannot contain the target.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.