```
class Solution {
public:
int findDuplicate(vector<int>& v) {
if(v.size()<1) return 0;
if(v.size()<3) return v[0];
int big=v.size()-1, small=1;
while(big!=small){
int mid=(big+small+1)/2;
int nums=0, numb=0, numm=0;//count less than,bigger than, and equal to middle
for (int i=0; i<v.size(); i++){
if(v[i]>mid&&v[i]<=big){
numb++;
} else if(v[i]>=small&&v[i]<mid){
nums++;
} else if(v[i]==mid){
numm++;
}
}
if(numm>1)
return mid;
if(nums>numb)
big=mid-1;
else
small=mid+1;
}
return small;
}
};
```