1. 287

[find-the-duplicate-number](https://leetcode.com/problems/find-the-duplicate-number/）

2. 算法

• O(lgn)

* 二分

* 巧妙

3. 代码

* 二分

• 区间[1,n]之间搜索，求出中点mid
• 遍历数组，统计所有小于等于mid的数的个数，
• 如果个数大于mid，则说明重复值在[mid,n]之间，反之，重复值在[1,mid-1]之间
• 搜索完成，此时low是所求

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low=1,high=nums.size()-1;
        while(low<high){
            int mid=low+(high-low)*0.5;
            int cnt=0;
            for(auto a:nums){
                if(a<=mid)  ++cnt;
            }
            if(cnt<=mid)  low=mid+1;
            else high=mid;
        }

        return low;
    }
};