Find the Duplicate Number — Binary Search on Count

# Python
def findDuplicate(nums):
    lo, hi = 1, len(nums)-1
    while lo < hi:
        mid = (lo+hi)//2
        count = sum(1 for x in nums if x <= mid)
        if count > mid: hi = mid   # duplicate in [lo, mid]
        else: lo = mid+1
    return lo

// Java
public int findDuplicate(int[] nums) {
    int lo=1, hi=nums.length-1;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2, cnt=0;
        for (int x:nums) if(x<=mid) cnt++;
        if (cnt>mid) hi=mid; else lo=mid+1;
    }
    return lo;
}