面试必考的「二分算法」系统梳理( 二 ) _二分算法

有时精度不容易确定，因此直接固定循环次数进行二分，即第二种方法。与第一种方法仅有「循环条件」的区别，代码示例如下：
for (int i = 0; i < 100; i++) {double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}三、二分答案二分算法成立的关键在于单调性，因此任何具有单调性的问题，我们都可以考虑在其上使用二分算法的可能性。正是基于这一点，当问题的答案具有单调性时，我们可以通过二分将「问题的求解」转化为「问题的判定」，该方法即为「二分答案」。
接下来我们将通过两道例题进一步地讲解该算法。
287. 寻找重复数题目描述给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有一个重复的整数，请找出这个重复的数，并只使用 O(1) 的额外空间。

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

2 <= n <= 3e4
nums.length == n + 1
1 <= nums[i] <= n
nums 中只有一个整数出现两次或多次，其余整数均只出现一次

题目讲解本题有很多种做法，但我们主要以该题为例来讲解「二分答案」，因此我们直接进入「二分答案」的思考过程。
一道题想要使用「二分答案」，其最大的前提是「答案有单调性」，而本题所求解的答案是显然的，即「重复数的值」。所以我们需要找到一个「判定条件」，使得对于二分区间 [l, r]，我们可以根据其中值 mid 是否满足「判定条件」，来确定下一个搜索区间是左半部分还是右半部分。
在本题中，我们令 f(x) 表示数组中 <= x 的个数，则不难发现 f(x) 是关于 x 的单调函数，即随着 x 的变大，f(x) 要么变大要么不变。
具体来说，假设重复数为 A，则对于所有小于 A 的数 x，f(x) = x；而所有大于等于 A 的数 y，f(y) > y 。例如对于数组 [1 2 2 2 3]，n = 4，f(1) = 1，f(2) = 4，f(3) = 5，f(4) = 5 。
由此我们可以通过「二分答案」来解决本题，对于二分区间 [l, r]，其中值为 mid，若 f(mid) > mid，则说明重复数小于等于 mid，因此更新 ans = mid，且将二分区间变为 [l, mid - 1]；否则不更新 ans 且二分区间变为 [mid + 1, r] 。
二分答案的时间复杂度为 O(log(n))，对于特定的 mid，求解 f(mid) 的时间复杂度为 O(n)，因此本题总的时间复杂度为 O(nlog(n))，具体代码如下所示：

class Solution {public:bool check(vector<int>& nums, int mid) {int cnt = 0;for (int x:nums) {if (x <= mid) cnt++;}if (cnt > mid) return 1;else return 0;}int findDuplicate(vector<int>& nums) {int l = 1, r = nums.size(), ans = 0;while (l <= r) {int mid = (l + r) / 2;if (check(nums, mid)) {ans = mid;r = mid - 1;}else l = mid + 1;}return ans;}};

其中 while 循环中的 check 函数即为「二分答案」问题中的「判定条件」。对于「二分答案」所适用的题目，我们通常只需对 check 函数进行修改，while 循环中的部分基本不变。

410. 分割数组的最大值题目描述给定一个非负整数数组 nums 和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1

输入：nums = [7,2,5,10,8], m = 2输出：18解释：一共有四种方法将 nums 分割为 2 个子数组 。其中最好的方式是将其分为 [7,2,5] 和 [10,8]。因为此时这两个子数组各自的和的最大值为18，在所有情况中最小 。

示例 2输入：nums = [1,2,3,4,5], m = 2输出：9示例 3输入：nums = [1,4,4], m = 3输出：4提示

1 <= nums.length <= 1000
0 <= nums[i] <= 1e6
1 <= m <= min(50, nums.length)

题目讲解查看题干，「最大值最小」，这是答案具有单调性，可用二分将「问题求解」转换为「问题判定」最常见、最典型的特征之一。
具体来说，在本题中，若「子数组和的最大值小于等于 x」符合数组分割要求，则比 x 更大的答案也一定符合要求。即当 x 为负数时，数组分割要求无法满足，但随着 x 的不断变大，会有一个分界点 A，当 x 大于等于 A 时，数组分割要求即可满足，而这个 A 即为本题答案。
由此本题从「求解 A」转换为了「二分 A 并判断数组分割要求是否可以满足」。对于二分区间 [l, r]，其中值为 mid，若 mid 满足数组分割要求，则更新 ans = mid，二分区间变为 [l, mid - 1]；否则不更新 ans 且二分区间变为 [mid + 1, r] 。