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

所以本题的「判定条件」为：对于特定的 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 为偶数时，两部分长度一致，且第一部分最大值小于等于第二部分最小值，即：