287. 寻找重复数 (opens new window)

1.二分查找

这里要打破二分查找的思维局限：

• 二分查找的查找空间可以是题目所给的索引下标，这种情况下一般要求数组本身是有序的。
• 二分查找空间是数组下标索引的情况下，并不要求数组一定有序，只需要保证结果一定会出现在另外一边即可。
• 二分查找的查找空间可以是一个序列或者是一个连续范围，mid代表一个target，每次遍历用target和数据进行比较。

对于某个元素target而言，数组里小于等于target的所有元素个数为count，count大于target，那么说明要找的那个多余的数一定出现在[1,target]之间。

基于这个规律，要查找一个有范围的数，可以考虑二分查找，通过二分查找对所有可能的target进行枚举,如果当前count大于target，那么说明重复的数在[1,target]之间，缩小右边界进一步逼近target最准确范围。

⚠️注意这里如果count小于target，我们并不需要关注这个target，因为题目当中已经指明了两点限制：①重复的整数只有一个②重复的数量大于等于2。因此求解过程实际上就是使用二分查找的方法不断逼近满足count>target的连续序列的最左边的值。

class Solution {
    public int findDuplicate(int[] nums) {
        int ans=0;
        int left=1,right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            int count=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]<=mid){
                    count++;
                }
            }
            if(count>mid){
                right=mid-1;
                ans=mid;
            }else{
                left=mid+1;
            }
        }
        return ans;
    }
}