Array Binary Search
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) = 4
target (int) = 5
Return:
(int) 2
Example 2
Input:
nums (int[]) = [1,3,5,6]
size (int) = 4
target (int) = 2
Return:
(int) 1
Example 3
Input:
nums (int[]) = [1,3,5,6]
size (int) = 4
target (int) = 7
Return:
(int) 4

Use 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 left
Run your code to see the result.