给定一个包含 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) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

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

二分查找

思路及算法

看了标签有「二分查找」，我就一直琢磨这个用「二分查找」怎么完成这道题

排序

二分查找需要有序数组，所以在查找前必须排序。

题目要求「不能更改原数组（假设数组是只读的）」，但是我们可以将排序好的结果放入新的数组中，满足要求「只能使用额外的 O(1) 的空间」

求中位数

既然求mid，那么我们需要知道大小范围才能求吧。

仔细审题「n + 1 个整数的数组 nums」，「数字都在 1 到 n 之间」

length = len(nums) # 求出数组长度 n+1
n = length - 1     # 数字都在1到n之间

所以，范围是 [0, len(nums)-1]

length = len(nums) # 求出数组长度 n+1
n = length - 1     # 数字都在1到n之间
left = 0
right = n
...
mid = (left + right) >> 1

与谁比较，怎么比较？

「二分查找」的特性就是，按中位数将有序数组一分为二，每次选择满足条件的一半，继续二分

那么，现在的问题就是「如何知道重复元素在哪一半？」

重要信息：

只有一个重复元素 数字范围是[0, len(nums)-1]

举例来说明，当前有一个有序数组 [1,2,3,4,4]，这个数组长度为5，而数字取值范围是[1, 4]，就算一字排开[1,2,3,4] 也只有4个元素，所以剩下一个元素，必定重复。绕了个弯子，那么如何找重复元素呢？

可以把每个不同的数字，看做是不同种类的萝卜，一个坑位对应一种类型的萝卜

在此例中，第一次mid是2，对应的元素值是3，用rihgt-mid我们得知mid之后还有两个位置

然而用nums[right]-nums[mid]，差值为1，小于剩余位置的个数，这就可以说明重复元素在mid的右边部分。这就好像，坑有两个，但是只有一个品种的萝卜

换个例子[1,2,2,3,4],在这个例子中的第一次计算mid之后，nums[right]-nums[mid] 等于 right-mid，mid右边部分就符合 一个坑位对应一个品种

形象一点：

rihgt-mid：计算坑位

nums[right]-nums[mid]：计算萝卜品种数

经过上面的分析，得出结果：

如果right - mid > nums[right] - nums[mid]

表示重复元素在右边，即向右收缩，left = mid，因为mid可能刚好是重复元素，所以不是 left = mid + 1

否则表示重复元素在左边，即向左收缩，right = mid
循环何时退出？

通过上面的分析，左右收缩的时候都是 =mid，观望大佬们总结的模板，此等情况循环的结束条件为 left + 1 = right

动图演示

完整代码

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        length = len(nums)
        n = length - 1
        left, right = 0, n
        nums = sorted(nums)
        while left + 1 < right:
            mid = (left + right) >> 1
            if nums[right] - nums[mid] < right - mid:
                left = mid
            else:
                right = mid
        return nums[left]