public int findDuplicate(int[] nums) {
int low = 1, high = nums.length  1;
while (low <= high) {
int mid = (int) (low + (high  low) * 0.5);
int cnt = 0;
for (int a : nums) {
if (a <= mid) ++cnt;
}
if (cnt <= mid) low = mid + 1;
else high = mid  1;
}
return low;
}
Java O(1)space using BinarySearch

This does not fly since you assume that the count of elements on one side of mid will be enough to tell you where the repeated element is. This is not always the case. Consider:
0 1 2 2 2 5 6 7 8 9 10. mid is 5 and the count on either side is unchanged by the repeated element. You still need to inspect both segments.

Regardless. Binary search in this way will not work since counting member on either side of the midpoint is not sufficient to determine where the repeat number is. Modified example
1 2 2 2 5 6 7 8 9 10 11
2 is repeated 2 more times. midpoint is 6. count is 5 on both sides of the midpoint. count cannot differentiate where the repeat number is.

This does not fly since you assume that the count of elements on one side of mid will be enough to tell you where the repeated element is. This is not always the case. Consider:
1 2 2 2 5 6 7 8 9 10 11. mid is 6 and the count on either side is unchanged by the repeated element. You still need to inspect both segments.


As @GodHelpMe noted this is still invalid input, not long enough. If you add another 2 it works as intended.

How could this meet the speed requirement? The worst case running time for this algorithm is O(n2). Worst case is that the dup number happens to be the median, which happens to reside in the middle of the array. Each round takes O(n), n/2 rounds are needed to locate the dup number therefore running time O(n2).
e.g. 1 2 3 4 5 5 6 7 8 9

Not sure if you are asking for an explanation of this solution or if you could not come up with the solution.
The complexity is O(logn) for the while loop times O(n) for the inner for loop => O(nlogn). In order to achieve better than O(n^2) we need to divide and conquer to get a log factor complexity. we know that the lowest num is 1 and the highest is n  1 so we choose the middle and then count the numbers in the array that are less than or equal to it. That way we can tell if the duplicate is closer to left (count > middle) or to high i.e. which side of mid it lies on and thereby we can halve the problem set each iteration.

@han38 the 'low' here means the smallest num that can possibly exist in the nums[], since according to "n + 1 integers where each integer is between 1 and n (inclusive)" , so all the numbers are in [1, n] ([1, nums.length1])