题目描述

题目描述
给定包含n+1整数的数组num，其中每个整数介于1和n之间(包括在内)，则证明至少存在一个重复数。假设只有一个重复的号码，找到一个重复的号码。

样例

注意
不能修改数组元素，假设数组是只读的。
仅可以使用常数即O(1)O(1)的额外空间。
时间复杂度需要低于O(n2)O(n2)。
数组中仅有一个重复数字，但它可能重复超过1次。
样例
Example 1:

Input: [1,3,4,2,2]
Output: 2
Example 2:

Input: [3,1,3,4,2]
Output: 3;
注意这题是对1到n进行二分，不是对数组中的数

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l=1,r=nums.size()-1;//从1扫描到n
        while(l<r)
        {
            int ans=0;
            int mid=l+r>>1;
            for(auto i:nums) 
            if(i<=mid) ans++;
                if(ans>mid) r=mid;//小于等于mid这一侧有重复的数
                else l=mid+1;//mid左侧无重复的数，向右移动一位
        }
        return l;
    }
};