可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足

在这里，对于一个区间$[l, r]$，如果给定数组中所有数在这个区间内的数量大于区间长度，那么答案必然在区间内，否则不在这个区间内，通过不断缩小范围，最终可以确定答案。

这里的区间指的是数值范围，而非下标。

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            int s = 0;
            for (auto &x : nums) s += (x >= l && x <= mid);
            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};