287. 寻找重复数

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入： nums = [1,3,4,2,2]
输出： 2
复制代码

示例 2：

输入： nums = [3,1,3,4,2]
输出： 3
复制代码

具体题目链接： 题目链接

思路：

二分题目的思路：
确定二分边界
编写二分的代码框架
设计一个check（性质）
判断一下区间如何更新
如果更新方式写的是l=mid,r=mid-1,那么就在算mid的时候加上1

分析：
1.Binary Search有三个框架
（1）寻找符合条件的最左端的那个
（2）寻找恰好符合条件的那个
（3）寻找符合条件的最右端的那个

2.使用二分搜索的特征:注意是要看mid的定义

1. 答案区间已经有序
2. 最优解在答案区间内

代码：

var findDuplicate = function(nums) {
    const n = nums.length;
    let left = 1, right = n - 1, ans = -1;
    while (left <= right) {
        let mid = (left + right) >> 1;
        let cnt = 0;
        for (let i = 0; i < n; ++i) {
            cnt += nums[i] <= mid;
        }
        if (cnt <= mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
            ans = mid;
        }
    }
    return ans;
};
复制代码

总结：

这是算法系列文章「二分专题」的相关题解