leetcode 二分查找·系统掌握 第k个缺失的正整数

题目：

题解：

一种可行的办法是从1开始枚举num并不断在arr中二分查找该值，返回没有找到的第k个元素对应的num即可。

int findKthPositive(vector<int>& arr, int k) {
        int cnt=0;
        int num=0;
        int l=0,r=arr.size()-1,mid;
        while(cnt!=k){
            num++;
            l=l,r=arr.size()-1;
            while(l<=r){
                mid=(l+r)>>1;
                if(arr[mid]==num)break;
                else if(arr[mid]>num)r=mid-1;
                else l=mid+1;
            }
            //只有在普通二分查找失败时才执行
            if(arr[mid]!=num)cnt++;
        }
        return num;
    }

题后反思：

和泛型二分查找一样，普通二分查找也有需要查找失败的情况。但是和泛型二分查找不同，查找结果在mid中而泛型二分查找结果在 l 和 r 中。只需要增大普通二分查找的 r l mid 的作用域即可。