引言
这是笔者的第一篇公众号文章，思来想去一直没决定好写什么（因为想写的东西太多了。最后决定讲一道我个人觉得很有意思的一道题，那就是LeetCode上大名鼎鼎的Median of Two Sorted Arrays。这道题是一道非常经典并且有相当难度的二分查找问题，彻底理解和实现之后其他二分查找问题相信都会迎刃而解。
题目详情
原题如下：
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m n)).You may assume nums1 and nums2 cannot be both empty.
翻译如下：有两个有序数组 nums1和 nums2，长度分别为m和n，在最大时间复杂度为 O(log(m n))的要求下找到将两个数组合并成的有序数组 nums3的中位数。
例子：A=[1,3,8,10,11], B=[2,4,6,7,9], 将两数组有序合并后得到 C=[1,2,3,4,6,7,8,9,10,11]，此时中位数为 (6 7)/2=6.5.
题目分析
初次看到这道题时可能会毫无头绪，只知道肯定用二分查找（因为有个log)，但是并不知道应该二分求解什么对象，很多人会直奔二分求解数组 C的中位数，但是发现构造数组 C需要手动将两个数组合并，这将直接导致我们的时间复杂度达到 O(n)。并且令人头大的是当合并数组C的长度为奇数或者偶数时，中位数的求法甚至都不一样。因此，我们需要另辟蹊径。
我们先来看一下数组C有偶数个元素的情况
我们不妨如上图所示将融合的过程画出来。可以发现，数组C的左半部分（黄色）由数组A的左边一部分(左paritition)和数组B的左边一部分构成，C的右半部分(绿色)由数组A的右边一部分（右partition）和数组B的右边一部分构成。数组A被 partitionA=2分为左partition和右partition，同样，数组B被 partitionB=3分为左partition和右partition。
不难发现， partitionA和 partitionB必须满足以下关系。
partitionA partitionB == C.Length() / 2
A[partitionA - 1] <= B[partitionB]
B[partitionB - 1] <= A[partitionA]简单的说就是，A的右partition加上B的右partition必须等于C长度的一半，A左边的最大值必须小于B右边的最小值，同样B左边的最大值必须小于A右边的最小值。
当我们找到满足条件的这一组数时，中位数将等于：
代码语言：javascript复制简单的说就是，取所有左partition的的最大值和所有右partition的的最小值的平均数， 6=max(3,6), 7=max(7,8), 因此中位数为 (6 7)/2=6.5。
因此，只要确定 partitionA或 partitionB 中任意一个值，我们就能推出另外一个值，并且求得中位数!
比方说我们可以选择求 partitionB的值。数组B的长度为5， partitionB可以是0到5的任意一个值，那么我们必须要把正确的值试出来，怎么试呢？我们可以利用数组A和B的有序性进行二分查找！以下迭代将用伪得不能再伪的伪代码来展示（二分查找窗口从 [0,5]开始）。
iteration 1:
代码语言：javascript复制start = 0;
end = 5;
partitionB = (start end) / 2 = 2;
partitionA = C.Length() / 2 - 2 = 5 - 2 = 3;此时我们查看条件是否满足：
代码语言：javascript复制A[partitionA - 1] = 8
A[partitionA] = 10
B[partitionB - 1] = 4
B[partitionB] = 6
此时 A[partitionA-1]>B[partitionB], 显然不符合我们上面的不等式，值得注意的是，此时的情况是A数组的左partition的最大值大于B的右partition的最小值，因此我们的partitionB应该向右边移动，也就是说二分查找的窗口将从 [0,5] 变为 [partitionB 1,5]也就是 [3,5]。于是我们开始第二轮迭代。
iteration 2:
代码语言：javascript复制start = 3;
end = 5;
partitionB = (start end) / 2 = 4;
partitionA = C.Length() / 2 - 4 = 5 - 4 = 1;我们再次查看条件是否满足：
代码语言：javascript复制A[partitionA - 1] = 1
A[partitionA] = 3
B[partitionB - 1] = 7
B[partitionB] = 9
发现不等式这次仍然无法满足( B[partitionB-1]>A[partitionA])，可是此时的情况与上一轮不同，此时B数组的左partition的最大值比A数组的右partition的最小值大，因此partitionB应该向左移动。二分查找窗口将从 [3,5]变为 [3,partitionB-1]也就是 [3,3]。于是我们开始第三轮迭代。
iteration 3:
代码语言：javascript复制start = 3;
end = 3;
partitionB = (start end) / 2 = 3;
partitionA = C.Length() / 2 - 2 = 5 - 3 = 2;查看条件是否满足：
代码语言：javascript复制A[partitionA - 1] = 3
A[partitionA] = 8
B[partitionB - 1] = 6
B[partitionB] = 7这时可以发现所有的左值都小于右值, 也就是说我们已经得了正确的partition！此时求得中位数为 [max(3,6) min(8,7)]/2=6.5
在上述过程中有一个需要特别注意的边界条件，那就是 partitionB的值为5时， partitionA求得为0，这时 partitionA-1为-1，同理， partitionB的值为0时， partitionA的值为5，超过了数组的最大索引4。这种极限情况如下图所示。
因此，当索引到数组中不存在的元素时，我们要赋值给这个元素一个特殊的值，我们规定：当 A[partitionA-1]不存在时，赋值给其 INTMIN, 因为如果A的左partition不存在，在做比较的时候任何数都可以比它里面的所有元素大。当 A[partitionA]不存在时，赋值给其 INTMAX，此时同理，如果A的右partition不存在，那么做比较的时候任何数都可以比他里面的所有元素小。对B来说同理。
现在我们已经讨论完毕了C数组长度为偶数的情况。那么长度为奇数时如何求得中位数呢？其实答案很简单，如下图所示，只要取 partitionA和 partitionB的最小值即可。
代码
附上完整的C 代码，只需不到三十行，这样一看其实题目并不难（手动狗头
代码语言：javascript复制double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
int lenA = A.size();
int lenB = B.size();
if (lenA > lenB) {
return findMedianSortedArrays(B, A);
}
int start = 0;
int end = lenA;
while (start <= end) {
int partitionA = (start end) / 2;
int partitionB = (lenA lenB) / 2 - partitionA;
int leftA = (partitionA > 0) ? A[partitionA - 1] : INT_MIN;
int rightA = (partitionA < lenA) ? A[partitionA] : INT_MAX;
int leftB = (partitionB > 0) ? B[partitionB - 1] : INT_MIN;
int rightB = (partitionB < lenB) ? B[partitionB] : INT_MAX;
if (leftA <= rightB && leftB <= rightA) {
if ((lenA lenB) % 2) {
return min(rightA, rightB);
} else {
return (max(leftA, leftB) min(rightA, rightB)) / 2.;
}
} else if (leftA > rightB) {
end = partitionA - 1;
} else {
start = partitionA 1;
}
}
return 0;
}总结
这道算法题属于LeetCode中hard级别的题目，难度主要在于确定二分查找对象和极端边界情况的处理。但是一旦将这两点考虑透彻，写代码将如砍瓜切菜一般。
最后祝各位同学面试超常发挥，毕业生找个好工作，想跳槽的人工资翻倍
！！
