//抽屜原理，查找哪邊的蘋果的數量大于了抽屜的數量
class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;//對1~n的數進行二分，而不是對nums中數二分
        while (l < r) {
            int mid = (l + r) >> 1;

            int cnt = 0;
            for (auto num : nums) cnt += (num >= l && num <= mid);
            //如果小于等于左邊的抽屜數量（mid - l + 1）,說明左邊一定沒有重復的，答案在右邊
            if (cnt <= mid - l + 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};