Intermediate Level
Implement the findFirstGreaterThanTarget method that returns the first value greater than the 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 value in the array that is greater than target.
If no value is greater than the target, return -1. For example, in [1,3,5,7] with target 4, the first greater value is 5.
Example 1
Input
nums (int[]) =
[1,3,5,7]size (int) =
4target (int) =
4Returns (int)
5Example 2
Input
nums (int[]) =
[2,4,6]size (int) =
3target (int) =
6Returns (int)
-1Example 3
Input
nums (int[]) =
[5,8,9]size (int) =
3target (int) =
1Returns (int)
5Because the array is sorted, binary search can find the first value greater than the target efficiently.
When the middle value is greater than the target, store it as a possible answer and continue searching on the left side to find an earlier greater value. When the middle value is less than or equal to the target, search on the right side.
At the end, return the stored answer, or -1 if no greater value was found.
Pseudocode:
function findFirstGreaterThanTarget(nums, size, target):
left = 0
right = size - 1
answer = -1
while left <= right:
mid = (left + right) / 2
if nums[mid] > target:
answer = nums[mid]
right = mid - 1
else:
left = mid + 1
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run