```
class Solution {
public:
int findDuplicate(vector<int>& nums) {
const int n = static_cast<int>(nums.size()) - 1;
int left = 1;
int right = n + 1;
while (left < right - 1) {
int mid = (left + right) >> 1;
int count[2] = {0};
for (size_t i = 0; i < nums.size(); ++i) {
if (nums[i] >= left && nums[i] < mid) {
++count[0];
} else if (nums[i] >= mid && nums[i] < right) {
++count[1];
}
}
if (count[0] > mid - left) {
right = mid;
} else {
left = mid;
}
}
return left;
}
};
```