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

文章插图

（此处为整除）。
又因为 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
声明：本文归 “力扣” 版权所有，如需转载请联系。文中部分图片来源于网络，如有侵权联系删除。

【面试必考的「二分算法」系统梳理】