Median of Two Sorted Arrays

@(算法)[算法, Sorted Array, Divide and Conquer, Array, Zenefits, Uber, Google]

这一题怎样用一句话描述？

给定两个已排序的数组，找出它们合并之后的中位数（大于和小于这个数的一样多）

用到什么算法？什么数据结构？

类似二分法，数组

通过这题学到了什么？

这一题首先想到的是暴力解法：直接将两个数组合并，然后取出下标为 (m + n - 1) / 2 的数（当m + n是奇数时）或者下标为 (m + n ) / 2 和下标为 (m + n ) / 2 - 1 两个数的算数平均值。

暴力法需要 O(m + n) 的时间并且可能要消耗 O(m + n) 的额外空间。暴力法很容易就能写出来，除非连Merge Sorted Array都写不好，那样就面壁思过去吧……

Challenge是要写出 O(log (m + n)) 的方法。原理其实与找出两个合并数组中第K大的元素一样，只不过这里的K变成了 (m + n) / 2。这两篇博客里都提到了该算法的思路：博客1 博客2

这里简单说一下我的理解：

既然是要找第K大的元素，那么就只可能从A数组的前K个元素，和B数组的前K个元素中找。那么我们可以把 A[K / 2 - 1] 元素和 B[K / 2 - 1] 元素进行比较（即A的第 K / 2 大的数和B的第 K / 2 大的数，注意下标是0-based，所以要减1，举例来说：A数组中比 A[K / 2 - 1] 小的数有A[0], A[1], A[2], … A[K / 2 - 2] 总共 K / 2 - 1 个数，所以 A[K / 2 - 1] 是第 K / 2大的数），产生以下比较结果：

A[K / 2 - 1] < B[K / 2 - 1]，此时第K大的元素必定不可能在 A[0 ~ K / 2 - 1] 中。这里可以用反证法，假设第 K 大的元素在 A[0 ~ K / 2 - 1] 中，那么这个第 K 大的元素必然小于等于 A[K / 2 - 1]（最大也就是A[K / 2 - 1]）。不妨就假设第 K 大是 A[K / 2 - 1] ，那么A数组中就有 K / 2 - 1 个数比第 K 大小，我们知道当两个数组合并后总共有 K - 1 个数比第 K 大小。那么剩下的 K / 2 个数就只能从 B 数组里找了，也就是说第 K 大的数比 B[0 ~ K / 2 - 1] 都要大，换句话说就是 A[K / 2 - 1] 比B [0 ~ K / 2 - 1] 都要大，那么 A[K / 2 - 1] > B[K / 2 - 1]，与我们的原命题相矛盾。故反正失败，原命题成立。
B[K / 2 - 1] < A[K / 2 - 1]，此时第K大的元素必定不可能在 B[0 ~ K / 2 - 1] 中，与 (1) 同理。
B[K / 2 - 1] = A[K / 2 - 1]，此时 A[K / 2 - 1] 是 A 中第 K / 2 大的数，而 B[K / 2 - 1] 同时是 B 中第 K / 2 大的数，所以不管是 A[K / 2 - 1] 还是 B[K / 2 - 1] ，它们都比 A 和 B 合并后 K - 2 个数大，此时我们从 A[K / 2 - 1] 的角度去看整个数组，它大于 K - 2 个数，同时又与第 K - 1 个数相等，所以它总共大于等于 K - 1 个数，所以它就是第 K 大的数；反之从 B[K / 2 - 1] 的角度看去亦然。所以直接返回 A[K / 2 - 1] 或者 B[K / 2 - 1] 即可。

不管我们比较的情况是 (1) 还是 (2)，我们都要继续往下搜索，只不过此时的问题变成了在去掉了 A[0 ~ K / 2 - 1] 区间的 A 数组和 B 数组中找出第 K - K / 2 大的数（情况1）；或者从去掉了 B[0 ~ K / 2 - 1] 区间的 B 数组和 A 数组中找出第 K - K / 2 大的数。所以，除了情况 (3) 可以直接返回以外，另外两种情况都要继续往下递归的。

直到 K = 1 时，我们知道此时只要把剩余两个数组的分别取出它们的第一个数，比较得出最小的就行了。

注意：我们在抛弃区间的时候，很可能存在 A 数组剩余部分已经没有 K / 2 个数了，那么此时就直接返回 B 数组的第 K 个数就行了，也就是 B[K - 1]；反之就返回 A[K - 1]。

按照这个思路，我们每次最少可以抛弃掉K / 2个数，由于K = (m + n) / 2，所以我们每次都抛弃了(m + n) / 4个数。而当我们抛弃掉 (m + n) / 2 个数时，就已经找到第K大了，所以最终的时间复杂度是 O(log(m + n))。

可能(已经)遇到的BUG有？

上述的分析，如果不能完全理解的话，边界条件一定会挂……