Intermediate Level
Implement the firstAndLastPositionBinary method that returns the first and last target positions using binary search.
The input contains a sorted integer array nums, its length size, and a target value.
Your task is to return an array containing the first and last index where target appears. If the target is not present, return [-1,-1].
For example, in [5,7,7,8,8,10], the value 8 first appears at index 3 and last appears 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[]) =
[1]size (int) =
1target (int) =
1Returns (int[])
[0,0]Use binary search two times.
The first binary search looks for the leftmost occurrence of the target. When the target is found, store the index and continue searching on the left side.
The second binary search looks for the rightmost occurrence. When the target is found, store the index and continue searching on the right side.
Pseudocode:
function findBoundary(nums, size, target, findFirst):
left = 0
right = size - 1
answer = -1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] == target:
answer = mid
if findFirst:
right = mid - 1
else:
left = mid + 1
else if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return answer
function firstAndLastPositionBinary(nums, size, target):
first = findBoundary(nums, size, target, true)
last = findBoundary(nums, size, target, false)
return [first, last]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run