请教：二分查找寻找数组重复数的核心逻辑及条件判断依据

给定一个包含n+1个整数的数组nums，每个整数的取值范围为[1, n]，数组中存在唯一的重复数字，要求在不修改数组nums且仅使用常数额外空间的前提下返回该重复数字。

class Solution(object):
    def findDuplicate(self, nums):
        beg, end = 1, len(nums)-1
        
        while beg + 1 <= end:
            mid, count = (beg + end)//2, 0
            for num in nums:
                if num <= mid: count += 1        
            if count <= mid:
                beg = mid + 1
            else:
                end = mid
        return end

• 示例1：
  输入: nums = [1,3,4,2,2]
  输出: 2
• 示例2：
  输入: nums = [3,1,3,4,2]
  输出: 3

先明确问题的核心前提：数组元素范围是[1,n]，总共有n+1个数，且只有一个重复数。

为什么要统计num <= mid的元素数量？ #

如果没有重复数，范围[1,mid]里恰好有mid个不同的数，对应数组中num<=mid的元素数量也应该是mid。但现在数组多了一个重复数，这个重复数要么在[1,mid]区间，要么在[mid+1, end]区间：

• 若重复数在[1,mid]里，数组中num<=mid的元素数量就会大于mid——原本只有mid个不同数，多了一个重复的，总数自然超标。
• 若重复数不在[1,mid]里（即落在[mid+1, end]），num<=mid的元素数量就等于mid——这部分数没有重复，数量正好是区间内不同数的个数。

条件判断的依据是什么？ #

代码里的判断逻辑是用来缩小查找范围的：

1. 当count <= mid时：说明[1,mid]区间的元素数量没超标，重复数不在这个区间，把查找范围调整为[mid+1, end]，也就是beg = mid + 1。
2. 当count > mid时：说明[1,mid]区间的元素数量超标了，重复数肯定在这个区间里，把查找范围缩小为[beg, mid]，也就是end = mid。

循环不断压缩范围，直到beg和end重合，这个值就是重复的数字。

拿示例1举例：nums = [1,3,4,2,2]，n=4，初始beg=1，end=4。

• 第一次mid=(1+4)//2=2，统计num<=2的数有1、2、2，共3个。3>2，说明重复数在[1,2]，所以end=2。
• 此时beg=1，end=2，mid=(1+2)//2=1，统计num<=1的数只有1，共1个。1<=1，说明重复数不在[1,1]，所以beg=2。
• 现在beg和end都是2，循环结束，返回2，正好是重复数。

内容的提问来源于stack exchange，提问作者CountDOOKU