Previous post: Binary search done right: longest increasing subsequence in O(n log n)

<aside> 💡 Problem statement: you are given a sorted array of positive integers, you have to identify k-th non-present positive integer element.

</aside>

Example:

array = [1, 2, 3, 5, 7, 8, 15]
                 ^ missing 4
                    ^ missing 6
                          ^ missing 9, 10, 11, 12, 13, 14

Note that by taking k-th element and subtracting its index, we get the number of skipped elements up to this point (plus one):

array[0] - 0 = 1  # 0 elements skipped + 1
array[1] - 1 = 1  # the same
array[3] - 3 = 5 - 3 = 2 # element `4` is skipped + 1
array[6] - 6 = 15 - 6 = 9 # 8 elements skipped + 1

Therefore, the sequence $(\mathtt{array}[i] - i + 1)_{i=0}^{n-1}$ is non-decreasing. By using binary search, we can identify the left and right boundaries for the property “the number of skipped elements is less than or equal to k”.

def find_kth_nonpresent(array: list[int], k: int) -> int:
    left = -1
    right = len(array)
    while right - left > 1:
        mid = (left + right) // 2
        if array[mid] - mid - 1 < k:
            left = mid
        else:
            right = mid
    # discussion continues

In the above code, we make sure that

• the left boundary satisfies the search condition. If we mathematically suppose that minus first element is $0$, then we have no skipped elements, which is less than k.
• the right boundary does not satisfy the search condition. Indeed, appending a positive infinity to the array, we have an infinite amount of skipped elements.

At the end of this piece, we have the left and right positions so that at left, there are less than k numbers skipped, and at right there are at least k numbers skipped.