Array Sorting Binary Search
Intermediate Level

Implement the kthMissingPositiveNumber method that returns the kth missing positive integer from a sorted array.

You are given a strictly increasing sorted array of positive integers and a value k. Return the kth positive integer that is missing from the array.

For example, in [2,3,4,7,11], the missing positive integers start as 1,5,6,8,9,....

Example 1
Input:
nums (int[]) = [2,3,4,7,11]
size (int) = 5
k (int) = 5
Return:
(int) 9
Example 2
Input:
nums (int[]) = [1,2,3,4]
size (int) = 4
k (int) = 2
Return:
(int) 6
Example 3
Input:
nums (int[]) = [5,6]
size (int) = 2
k (int) = 1
Return:
(int) 1

Use binary search on how many numbers are missing before each index.

At index i, the number of missing positive integers before nums[i] is nums[i] - (i + 1). Find the first index where the missing count is at least k. The answer can then be calculated from the search boundary.

This avoids scanning every missing number one by one.

Pseudocode:

function kthMissingPositiveNumber(nums, size, k):
    left = 0
    right = size
    while left < right:
        mid = (left + right) / 2
        missing = nums[mid] - (mid + 1)
        if missing < k:
            left = mid + 1
        else:
            right = mid
    return left + k
Run your code to see the result.