思路

# 抽屉原理
# 当苹果个数大于抽屉个数时，必定至少有一个抽屉有两个或以上苹果
# 此处，苹果就是数字个数（n+1），抽屉是坑位(<=n)

分析：

难点：

1、切分的区间是什么？
2、如何切分区间

误区：

• 作为算法小白，我一开始以为要二分的区间肯定就是题目给出的区间啊！
• 其实不然，有些题目就需要二分虚拟的想象出来的区间
• 本题巧妙之处在于不用管给出数组区间和它的索引，而是在一个抽象出来的值域线段中进行二分

步骤

1、每次把值域分成两段，遍历给定的整个数组，统计其落在左半边子值域之间值的数字的个数 ！！！难点
2、若落在此值域的数字个数大于该值域长度，说明该值域区间的数字必有重复
3、那么我们再将该值域切分两个，再统计其中一个子值域中，有多少数字落入其中
4、当值域越切越小，最终成为一个值，则该值就是解

时复

每次二分后都要遍历整个数组，所以时间复杂度为o(nlogn)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        l = 1; r = len(nums) # l,r在这里代表值域左右边界
        while l < r:
            mid = l + r >> 1
            cnt = 0 # 每次统计整个数组中 值落在左半边值域 的数字的个数
            for x in nums:
                if x >= l and x <= mid: # 注意取等号
                    cnt += 1
            if cnt > mid - l + 1: # 如统计的数字个数大于此值域区间长度，则说明左半边必有重复
                r = mid 
            else:
                l = mid + 1
        return r