287. Find the Duplicate Number

做题历程：

1. 9月6日，第一遍，没有解出。。。。

本题个人认为还是有一些难度的，但是难点不是在复杂上，而是一种思维上的转变。本题用的方法是binary search，算法的时间复杂度是O(nlogn)，不是最简单的，但是个人认为这种算法比较好理解。 大概说下思路：

1. 最外层是binary search，这里有一个思维盲点，原来的二分搜索的low和high都是index，在本题中是数本身
2. 内层循环数比mid小的count，跟据count值，来决定搜索左边还是右边，举一个例子吧： 假设中点为5，而count比5小的数有5个，这就证明duplicate number一定是在1 ~ 5这个范围内
3. 当然，具体的大于小于等于，需要仔细思考！！！！

代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1;
        int high = nums.size() - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid) {
                    ++count;
                }
            }
            if (count > mid) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
};