// 1. 二分抽屉个数， 因为0~mid个抽屉， 如果cnt个球，cnt > mid, 则必然在0~mid，反之亦如此
class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0 , r = nums.length - 1;

        while (l < r){
            int mid = (l+r) >> 1;
            int cnt = 0;
            for (int i = 0 ; i < nums.length ; i++) cnt +=  nums[i] <= mid ? 1: 0;

            if (cnt > mid ) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}