// binary search
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size();
int m = 0, c = 0;
while (l <= r) {
m = (l + r) / 2;
c = 0; // number less or equal to m
for (int x : nums) {
if (x <= m) ++c;
}
if (c > m) r = m  1; // duplicate number must located in [0, m1]
else l = m + 1; // duplicate number must located in [m+1, r]
}
return l;
}
There are bugs in the test system


@StefanPochmann, I have updated the code (which is not right), and it pass the judge system！

I believe it's actually correct now. Do you have an input that it fails?
With the invariant being that the correct answer lies in [l,r+1], the invariant is true at start (although r is two higher than necessary) and after each iteration and thus at the end. And you stop with l=r+1 and thus have exactly one number in [l,r+1] and it's the correct answer. No?