Learner Level
Implement the findInsertPosition method that returns the index where the target should be inserted in sorted order.
The input contains a sorted integer array nums, its length size, and an integer target. Your task is to return the index where target is found or where it should be inserted to keep the array sorted.
For example, in [1,3,5,6], target 5 is already at index 2. Target 2 should be inserted at index 1, and target 7 should be inserted at index 4.
Example 1
Input
nums (int[]) =
[1,3,5,6]size (int) =
4target (int) =
5Returns (int)
2Example 2
Input
nums (int[]) =
[1,3,5,6]size (int) =
4target (int) =
2Returns (int)
1Example 3
Input
nums (int[]) =
[1,3,5,6]size (int) =
4target (int) =
7Returns (int)
4Use binary search to find the first position where the current value is greater than or equal to the target.
If the target exists, that position is its index. If it does not exist, the same position is where the target should be inserted. When the search finishes, left holds the correct insertion index.
Pseudocode:
function findInsertPosition(nums, size, target):
left = 0
right = size - 1
while left <= right:
mid = left + (right - left) / 2
if nums[mid] == target:
return mid
else if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return leftReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run