面试必考的「二分算法」系统梳理
「二分」有关，算是非常普遍与重要的知识点。然而有很多同学依然没能很好地掌握，总是会在各种细节上跌跟头，因此今天我们将对二分算法进行系统地梳理。
「二分」一共有三类常见应用，分别是「整数二分」、「实数二分」以及「二分答案」，接下来将分别介绍这三类应用的具体形式。
一、整数二分
整数二分即为在整数集合上的二分，常见的用法有：在单调序列中查找「某个数是否出现过」、「某个数最早出现的位置」以及「>= 某个数中最小的数」等。
解决这类问题的思想非常统一，即对坐标区间不断进行折半，以此在 O(log(n)) 的时间复杂度内确定答案，但其「实现方法」却非常多样，由此导致很多同学在此类问题上出错。
因此接下来将通过一个例题来介绍「记录 ans」的二分实现方法，该方法较易理解且不易出错。
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值 target，返回 [-1, -1]。设计并实现时间复杂度为 O(log(n)) 的算法解决此问题。
示例 1
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3
输入：nums = [], target = 0
输出：[-1,-1]
提示
- 0 <= nums.length <= 1e5
- -1e9 <= nums[i] <= 1e9
- nums 是一个非递减数组
- -1e9 <= target <= 1e9
题目讲解
我们以数组 nums = [3 4 4 4 6], target = 4 进行举例，首先是确定 4 的开始位置，具体代码如下：
int l = 0, r = 4, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] >= target) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (nums[ans] != target) ans = -1;
上述代码在二分过程中，[l, r] 始终代表二分搜索的区间，而 ans 则代表「数组中第一个 >= target」的位置。最后再通过判断 nums[ans] 是否等于 target 来确定 target 是否存在于数组中。
我们来模拟一下这个过程，首先二分搜索区间为 [0, 4]，因此 mid = 2。此时 nums[2] >= 4，即 2 可能是「数组中第一个 >= target」的位置，因此更新 ans 为 2。
又因为 nums[mid] >= 4，即答案一定不在右半区间，即 [3, 4]，于是令 r = mid - 1，搜索区间变为 [0, 1]。此时 mid = 0，nums[0] < target，因此 mid 无法更新 ans。
由于 nums[mid] < target，因此答案一定不在左半区间，于是 l = mid + 1，搜索区间变为 [1, 1]。此时 mid = 1，nums[1] >= target，更新 ans = 1。
由于 nums[mid] >= target，于是 r = mid - 1，不再满足 l <= r 的条件，二分过程结束。最终 ans = 1，二分成功。
通过上述这个过程，我们可以总结出「整数二分」的实现规律，首先由 while (l <= r) 来控制二分进程，每次计算 mid = (l + r) / 2，并判断 mid 是否为可能的答案。如果是，则更新 ans，否则不更新。另外根据 mid 判断接下来是搜索左半区间 [l, mid - 1]，还是右半区间 [mid + 1, r]，不断循环。退出循环后，ans 即为要求的答案。
根据上述示例，大家可以自行完成「查找 target 结束位置」的代码，并查看下述完整代码进行验证。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1, ans1 = 0, ans2 = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] >= target) {
ans1 = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] <= target) {
ans2 = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (nums.size() && nums[ans1] == target) return {ans1, ans2};
else return {-1, -1};
}
};
二、实数二分
实数二分即为实数域上的二分，即二分搜索区间 [l, r] 从整数变为了实数。对比整数二分，实数二分的算法思想没有变化，唯一变化的只有二分实现方法。
通常来说实数二分有两种实现方法，第一种是通过确定好的精度 eps（如 1e-6、1e-8 等），以 l + eps < r 为循环条件，每次根据在 mid 上的判定，选择左半区间 [l, mid] 或右半区间 [mid, r]。循环结束后，l 即为最终答案，代码示例如下：
while (l + 1e-6 < r) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
有时精度不容易确定，因此直接固定循环次数进行二分，即第二种方法。与第一种方法仅有「循环条件」的区别，代码示例如下：
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]。
所以本题的「判定条件」为：对于特定的 mid，判断当子数组和的最大值 <= mid 时，子数组是否可以分成 m 个非空的连续子数组。
对于该「判定条件」，我们可以使用贪心算法，从前往后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量。若 sum 加上当前值 nums[i] 大于 x，则将 cnt 加 1，并将当前值作为新的一段分割子数组的开头，即 sum = nums[i]。遍历结束后，若 cnt <= m，则判定条件可以满足，否则无法满足。
由此本题得以解决，具体代码如下所示：
class Solution {
public:
bool check(vector<int>& nums, int m, int mid) {
int len = nums.size(), sum = 0, cnt = 1;
for (int x:nums) {
if (x > mid) return 0;
if (sum + x <= mid) sum += x;
else sum = x, cnt++;
}
return cnt <= m;
}
int splitArray(vector<int>& nums, int m) {
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(nums, m, mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
};
总结一下，当问题的答案具有单调性时，我们可以通过「二分答案」将「问题的求解」转换为「问题的判定」，进而完成解题的过程。
四、综合练习
最后我们以一道经典二分题为例进行综合练习，该题目难度较大，也是一道经典的面试题，希望大家能好好理解并掌握。
4. 寻找两个正序数组的中位数
题目描述
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数，且时间复杂度不高于 O(log (m+n))。
示例 1
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5
输入：nums1 = [2], nums2 = []
输出：2.00000
提示
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -1e6 <= nums1[i], nums2[i] <= 1e6
题目讲解
首先考虑一下本题能否「二分答案」，由于奇数长度与偶数长度解法类似，因此仅考虑 m + n 为奇数时的情况。
当 m + n 为奇数时，中位数即为两个数组排序后第 (m + n + 1) / 2 个数，因此令 f(x) 表示两个数组中 <= x 的数的个数，中位数即为满足 f(x) >= (m + n + 1) / 2 中最小的 x。由于两个数组均为正序，因此对于一个特定的 x，我们可以通过两次二分在 O(log(n) + log(m)) 的时间复杂度内求得 f(x)。
由此我们可以得知「二分答案」的时间复杂度为 O(log(2e6)(log(n)+log(m)))，其中 2e6 为「二分答案」初始区间 [-1e6, 1e6] 的长度。因此「二分答案」无法达到「时间复杂度不高于 O(log (m+n))」的要求，我们需要转换思路。
重新思考中位数的作用，我们可以发现：中位数常用于将一个序列划分为长度最多相差 1 的两部分，且其中一部分的元素始终大于等于另一部分。
为了便于表述，将 nums1 和 nums2 数组分别记为 A 和 B。接下来模拟序列的划分过程，在 A 数组中选取前 i 个数（A[0], A[1], ..., A[i-1]），在 B 数组中选取前 j 个数（B[0], B[1], ..., B[j-1]）。这 i + j 个数组成第一部分，剩下的 n + m - i - j 个数为第二部分。
进一步地，当 m + n 为偶数时，两部分长度一致，且第一部分最大值小于等于第二部分最小值，即：
此时中位数等于
；当 m + n 为奇数时，我们规定第一部分长度比第二部分大 1，且两部分的最值关系依然满足，即：
此时中位数等于
。观察上述两个式子，发现无论 m + n 为奇还是偶，均满足
。因此为了便于计算，我们将
与
统一为
（此处为整除）。
又因为 A、B 均为升序数组，因此上述两个式子可以修改为：
继续观察可以发现，当 i 增大时，j 在减小，即随着 i 的增加，A[i-1] 不断增加，而 B[j] 则不断减小。因此一定存在一个临界点 (i, j) 满足 A[i-1] ≤ B[j] ，而 i 再增加 1 则不再满足，即：
不难发现，临界点 (i, j) 刚好满足 i、j 划分数组的要求，因此本题可以通过二分 i 的位置，寻找最大的满足 A[i-1] ≤ B[j] 的 i，即可完成数组划分并求得中位数。
另外需要注意 i、j 可能会超出数组范围，因此规定 A[-1] = B[-1] = -1e9，A[m] = B[n] = 1e9。由此本题得以解决，时间复杂度为 O(log(min(m, n)))，满足题目要求。
代码实现
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) swap(nums1, nums2);
int n = nums1.size(), m = nums2.size(), l = 0, r = n, ans = 0;
while (l <= r) {
int i = (l + r) / 2, j = (n + m + 1) / 2 - i;
if (i <= 0 || j >= m || nums1[i-1] <= nums2[j]) {
ans = i;
l = i + 1;
}
else r = i - 1;
}
int i = ans, j = (n + m + 1) / 2 - i, x1 = -1e9, x2 = -1e9, x3 = 1e9, x4 = 1e9;
if (i > 0) x1 = nums1[i-1];
if (j > 0) x2 = nums2[j-1];
if (i < n) x3 = nums1[i];
if (j < m) x4 = nums2[j];
if ((n + m) % 2) return max(x1, x2);
else return (max(x1, x2) + min(x3, x4)) / 2.0;
}
};
总结
二分是一个非常常见却又极其精妙的算法，经常成为解题的一个突破口。该算法一共有三类常见应用，即「整数二分」、「实数二分」以及「二分答案」，其中「二分答案」能将「问题的求解」转换为「问题的判定」，因此应用非常广泛。
二分并没有固定的模板与套路，灵活性非常高，因此我们需要深刻理解其算法思想，并加以习题来巩固，以期早日掌握。
本文作者：Gene_Liu
声明：本文归 “力扣” 版权所有，如需转载请联系。文中部分图片来源于网络，如有侵权联系删除。
