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

示例 1:

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

示例 2:

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

一定注意以下几点要求：

1 不能更改原数组（假设数组是只读的）。

2 只能使用额外的 O(1) 的空间。

3 时间复杂度小于 O(n2) 。

4 数组中只有一个重复的数字，但它可能不止重复出现一次。

通常来说，二分查找是对值的二分。

就本题，在已知的条件下，却非常适合对索引二分。

因为题目假定元素取值范围：[1,n]，而数组长度为n+1，所以nums[i], i最大为 n，都不会越界。

那么如何利用好这个条件，是本题求解的关键。

我们思考如下问题：

如果所有元素都不重复，那么不大于i的个数一定为i个，考虑如下序列：

[1,4,2,3]
不大于2的个数为2，不大于3的个数为3.

如果出现不大于i的个数大于i，则意味着一定有重复元素，且重复元素值不大于i. 考虑如下序列：

[1,4,2,4,4]
不大于4的元素个数为5个，则表明重复元素一定位于[1,4]区间，而不可能出现在(4,5]区间。

因此，归纳出根据索引的二分条件找到重复元素的方法：

找到中间索引，即 mid = 0 + len(nums)-1
若nums中不大于mid的元素个数小于或等于mid，则表明重复值位于[mid+1,len(nums)-1]若大于mid，则一定位于区间[0,mid-1] 中

二分法

class Solution():
def findDuplicate(self, nums):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) //2
count = sum([1 for i in nums if i <=mid])
if count <= mid:
left = mid + 1
else:
right = mid -1
return left

def test_findDuplicate():
s = Solution()
nums = [1,3,4,2,2]
assert s.findDuplicate(nums ) == 2
nums = [3,1,3,4,2]
assert s.findDuplicate(nums ) == 3
nums = [1,2,3,4,5,6,7,8,9,12,3,3,3,3,10]
assert s.findDuplicate(nums ) == 3