1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findDuplicate(int[] nums) {
    int n = nums.length;
    int first = 1, last = n - 1, ans = -1;
    while (first <= last) {
        int mid = (first + last) >> 1;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= mid) {
                cnt++;
            }
        }


        if (cnt <= mid) {
            first = mid + 1;
        } else {
            last = mid - 1;
            ans = mid;
        }
    }
    return ans;
}