二分查找：有序数组中位数 | 刷爆LeetCode
大家好，我是小风哥，这是LeetCode刷题系列第4篇。
今天的题目是计算两个有序数组的中位数，要求是这样的：
给定两个有序数组，返回其中位数，示例：
数组: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释: merged array = [1,2,3] and median is 2.
先想一想最简单的解决方法，我们可以把这两个数组进行合并，由于数组有序，因此合并过程的时间复杂度为O(n)，合并后的数组有序因此可以直接返回中位数，此外空间复杂度也为O(n)。
但题目的要求是时间复杂度为O(log(m+n))，m和n分别为两个数组的长度。
想一想有什么更好的方法吗？
一般来说在排好序的数组中找某个符合要求的数字你的第一反应应该是：
二分查找，binary search
这是一种极其高效的搜索方法，每次都丢一半，最终可在O(logn)的时间复杂度内找到答案。
该怎样在这个题目中应用二分搜索呢？
我们可以先把这两个数组等分为两半：
然后呢？然后就能知道这两个数组左边的边界元素是多少，假设第一个数组左半部分最右侧的数组元素是2，第二个数组左半部分最右侧是10：
我们可以得出什么结论呢？
由于2小于10，那么这两个数组合并后a部分一定不超过c部分，因此a和c会合并在一起，b的一部分可能也不超过10，因此b的一部分有可能合并到c，另一部分合并到d。
总之我们一定能确认，合并后的左半部分长度一定大于等于(m+n)/2，这告诉我们什么呢？这告诉我们：
合并后的中位数一定位于b和c两部分而不可能存在于a和d两部分
因此我们可以放心的丢掉a和d，而在b和c中找中位数。
有了这些分析就可以写代码了，我们无需专门写一个找中位数的函数，而是可以写出一个找第k大的数，因为：
有时解决通用问题反而要比解决特定问题简单
最终代码为：
int findk(vector<int>& nums1, int b,int e,
vector<int>& nums2,int f, int s, int k) {
if (b > e) return nums2[f + k - 1];
if (f > s) return nums1[b + k - 1];
if (k == 1) return min(nums1[b], nums2[f]);
if (e - b > s - f) return findk(nums2, f, s, nums1, b, e, k);
int l1 = min(k/2, (e - b + 1));
int l2 = k - l1;
if (nums1[b + l1 - 1] <= nums2[f + l2 - 1]) {
return findk(nums1, b + l1, e, nums2, f, f + l2 - 1, k - l1);
} else {
return findk(nums1, b, b + l1 - 1, nums2, f + l2, s, k - l2);
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size();
int l2 = nums2.size();
int t1 = (l1 + l2 + 1)/2;
int t2 = (l1 + l2 + 2)/2;
return (findk(nums1,0,l1-1,nums2,0,l2-1,t1) +
findk(nums1,0,l1-1,nums2,0,l2-1,t2))/2.0;
}
代码逐行详解
1，代码参数的含义：b，e代表begin、second；f、s代码first、second，都是指两个数组的边界
2， findk函数返回两个数组第k大的数，这是一个通用函数
3， 当一个数组在处理过程中确定不存在中位数后我们可以在另一半数组中直接返回中位数：
if (b > e) return nums2[f + k - 1];
if (f > s) return nums1[b + k - 1];
4， 如果此时k为1，那么只需要返回两个数组比较小的那个起始元素即可：
if (k == 1) return min(nums1[b], nums2[f]);
5， 我们总是假设参数中第一个数组元素更少，目的是为了确认两个数组到底在什么位置切分为两半：
if (e - b > s - f) return findk(nums2, f, s, nums1, b, e, k);
6， 确认两个数组到底在什么位置切分为两半：
int l1 = min(k/2, (e - b + 1));
int l2 = k - l1;
7， 比较两个数组切分位置的元素，丢掉不存在中位数的部分，该过程即为这两张图：
if (nums1[b + l1 - 1] <= nums2[f + l2 - 1]) {
return findk(nums1, b + l1, e, nums2, f, f + l2 - 1, k - l1);
} else {
return findk(nums1, b, b + l1 - 1, nums2, f + l2, s, k - l2);
}
8， 如果一个数组的长度为偶数，比如[1,2,3,4]，那么中位数是(2+3)/2；如果是奇数比如[1,2,3]，那么中位数是2，因此我们需要根据奇数和偶数计算两次，但其实我们可以只计算一次，如果是偶数，那么t1和t2相等，否则指向中间的两个数：
int t1 = (l1 + l2 + 1)/2;
int t2 = (l1 + l2 + 2)/2;
return (findk(..., t1) + findk(..., t2))/2.0;
小风哥之前讲解的计算机底层文章已经全部汇总在了这里:https://github.com/xfenglu/everycodershouldknow,欢迎start提issue。