I have following concerns when solving this problem using binary search:

(1) what is the condition of ending the while loop, i.e., start + 1 < end or start < end (2) how to update bounds, i.e., start = mid or start = mid + 1 (3) which bound is the final result.

My way of avoiding pitfall is using start + 1 < end as the condition where the while loop ends. Then I can update both bounds with start = mid or end = mid. To guarantee my result is correct, I do a final check. Any suggestion? Thank you in advance!

```
int findDuplicate(vector<int>& nums) {
int start = 0;
int end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
int cnt = 0;
for (auto num : nums) {
if (num <= mid) cnt++;
}
if (cnt > mid)
end = mid;
else
start = mid;
}
int cnt = 0;
for (auto num : nums) {
if (num == start) {
cnt++;
if (cnt > 1)
return start;
}
}
return end;
}
```