23.02.26 学习

这个题用分治的二分思想去做，根据抽屉原理
看题解：https://www.acwing.com/solution/content/2814/

区间的划分是数值，而不是下标，所以l=1,r=nums.size()-1

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1; // 划分的区间：[l, mid], [mid + 1, r]
            int s = 0;
            for (auto x : nums)   // 统计在[l, mid]区间之间的数字个数
                if (x >= l && x <= mid) 
                    s ++ ;
            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;


    }
};