class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        //思路，利用抽屉原理，分两半区间，由于有n+1个数，故而分的两半区间中必定有一半数的个数大于
        //区间的长度，如果为左半边，则对左半边进行继续划分，如果为右半边，对右半边划分直至区间大小为
        //1此时直接返回，时间复杂度，区间划分为log(n) 区间中遍历为n 故而 nlogn 空间为1
        int l = 1,r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            int s = 0;
            for(auto x: nums) s += x >= l && x <= mid;  //等价于if(x >= l && x <= mid)  s++;
            if(s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};