二分法查找之应用

待定

1.二分法查找的前提：有序

1.二分法查找元素

  例题1--287. 寻找重复数，给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

    int findDuplicate(vector<int>& nums) {
        int n=nums.size();
        int left=0,right=n-1;
        int cnt=0;
        while(left<right){
            int mid=(right-left)/2+left;
            cnt=0;
            for(auto it:nums){
                if(it<=mid){
                    cnt++;
                }
            }
            if(cnt>mid){
                right=mid;
            }
            else{
                left=mid+1;
            }

        }
        return left;
    }

例题2--剑指 Offer 53 - II. 0～n-1中缺失的数字