Intermediate Level
Implement the searchRangeOfTarget method that returns the first and last position of a target in a sorted array.
The input contains a sorted integer array nums, its length size, and an integer target. Your task is to return the first and last index where target appears.
If the target does not exist in the array, return [-1,-1]. For example, in [5,7,7,8,8,10], the target 8 starts at index 3 and ends at index 4.
Example 1
Input
nums (int[]) =
[5,7,7,8,8,10]size (int) =
6target (int) =
8Returns (int[])
[3,4]Example 2
Input
nums (int[]) =
[5,7,7,8,8,10]size (int) =
6target (int) =
6Returns (int[])
[-1,-1]Example 3
Input
nums (int[]) =
[2,2]size (int) =
2target (int) =
2Returns (int[])
[0,1]Use binary search twice.
The first binary search finds the leftmost occurrence of the target by continuing to search on the left side after a match. The second binary search finds the rightmost occurrence by continuing to search on the right side after a match.
Return both indexes together.
Pseudocode:
function searchRangeOfTarget(nums, size, target):
first = findBoundary(nums, size, target, true)
last = findBoundary(nums, size, target, false)
return [first, last]
function findBoundary(nums, size, target, searchFirst):
left = 0
right = size - 1
answer = -1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
answer = mid
if searchFirst:
right = mid - 1
else:
left = mid + 1
else if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run