LC 1539. Kth Missing Positive Number (二分)

link

随着i增加，缺失的个数非减，在i处缺失的个数为arr[i]-(i+1).二分找到第一个缺失个数大于等于k的位置left, 则left-1处缺失的个数<k。left-1处缺失的个数为arr[left-1]-left, 还差k-arr[left-1]+left个，则答案是k+left.

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n=arr.size();
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(arr[mid]-(mid+1)>=k) right=mid-1;
            else left=mid+1;
        }
        
        return left+k;
            
    }
};