287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

本道题如果没有说明会是是一道很简单的题目，有多种解法，例如循环检测，例如创建一个哈希表，遍历一个数字就放进去，当出现重复就直接返回，例如可以排序之后用二分或者遍历，都是很方便很简单的方法，但是由于不满足说明，那就被一一否决了。

但是即使这样，本题依然有两种解法。
一种解法是用快慢指针，用了抽屉原理，是比较取巧的方法，没有通用性，我们这边就不做说明了。
另外一种解法其实就是在剑指offer上出现过的二分查找。

本题抓住数组的关键性质，数组大小是n+1，其数组都在乎1-n之间，包括1和n。

普通的二分查找是一个有序数组，而这个数组显然不是有序数组，那该如何解决呢，我们的答案是把中位数当做mid。
那应该如何求解呢？我们先设low = 0 ， high = n。然后我们去mid = (n-0)/2。这个时候我们开始遍历数组，当该数字小于等于mid 就加一，那我们就能得出该数组中，小于等于mid的值，如果不出现重复，那这个值显然应该是小于等于mid的。为什么会小于？这边不出现重复，说明会缺少数字，使得另外半边出现重复。
那我们就可以直接缩减范围了。二分查找也就成立了。

这就是解决本道题的关键，二分查找法不但可以运用在排序数组，如果这个数组限定了范围，从某种程度上仍然可以用二分查找。

代码如下：

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int low = 0;
        int high = n - 1;

        while (low < high){
            
            int mid = (high - low) / 2 + low;
            int count = 0;

            for (int num : nums){
                if (num <= mid){
                    count++;
                }
            }
            
            if (count > mid){
                high = mid;
            }
            else{
                low = mid + 1;
            }

        }
        return low;

    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。