1 class Solution {
 2     public int findKthPositive(int[] arr, int k) {
 3         if (arr == null || arr.length == 0) return -1;
 4         if (arr[0] != 1) {
 5             if (arr[0] - 1 >= k) return k;
 6             k = k - (arr[0] - 1); // arr[0] -1 refers to the missing numbers before arr[0]
 7         } 
 8 
 9         for (int i = 1; i < arr.length; i++) {
10             int diff = arr[i] - arr[i - 1] - 1;
11             if (diff >= k) {
12                 return arr[i - 1] + k;
13             } else {
14                 k -= diff;
15             }
16             
17         }
18         return arr[arr.length - 1] + k;
19     }

O(lgn)的解法：

https://leetcode.com/problems/kth-missing-positive-number/solutions/779999/java-c-python-o-logn/

My two cents on thought process for binary search:
Here we have three sorted sequences:
let n be len(A), then
1st sorted sequence is array values:

A[0], A[1], ... A[n-1]

2nd is indices:

0, 1, 2, ... n - 1

The nice part about this question: the indices can help us to get all the positive numbers in sorted order (i + 1 if i denotes the index)
Hence, A[i] - (i + 1) will be # of missing positives at index i, and this will be our 3rd sorted sequences
i.e.

A:            [1,3,4,6]
A[i] - (i+1): [0,1,1,2]

let's call array A[i]-(i+1) as B, which is [0, 1, 1, 2] above, then B[i] represents how many missing positives so far at index i.

So the question becomes: finding the largest index of array B so that B[j] is smaller than K.
It is the same as finding first/last occurrence 34. find-first-and-last-position-of-element-in-sorted-array

l, r = 0, len(B)
while l <= r:
    m = (r + l) / 2
    if B[m] < K:
        l = m + 1
    else:
        r = m - 1

After while loop is stopped, l - 1 is our target index because, B[l - 1] represents how many positive is missing at index l - 1 that is smaller than K, so result is A[l -1](the largest number in A that is less than result) + K - B[l - 1](offset, how far from result) = (A[l - 1]) + (k - (A[l - 1] - l)) = l + k

 1     public int findKthPositive(int[] A, int k) {
 2         int l = 0, r = A.length - 1, m;
 3         while (l <= r) {
 4             m = (l + r) / 2;
 5             if (A[m] - (1 + m) < k)
 6                 l = m + 1;
 7             else
 8                 r = m - 1;
 9         }
10         return l + k;
11     }