Google、Microsoft、Uber、Apple 同时考了这道题之后，收到大批反馈信息要求查看最优题解，秋招大门已经打开，你还在等什么？
题目描述
两个已排好序的数组，找出两者合并后的数组的中位数
Example
给出 A=[1,2,3,4,5,6] 和 B=[2,3,4,5]，他们合并后的中位数是 3.5（(3+4)/2）
给出 A=[1,2,3] 和 B=[4,5]，他们合并后的中位数是 3
算法分析
- 这道题的直观解法：就是扫一遍两个数组，找到中间位置的那一个/两个数，然后得到中位数。时间复杂度是 O(m+n)，其中 m 和 n 分别是数组 A 和数组 B 的长度
2. 但是！面试官会这么轻易就放过你吗？显然是不可能滴~~我偷看了一下题目描述下的“challenge”标签，原来这道题的最优解是 O(log(m + n)) 的复杂度。(m + n) 是俩数组合并后的总长度 L，看到 O(log L) 这样的复杂度，而且还是有序数组，能想到哪个算法吗？没错，就是二分查找！那我们试试
a. 如果我取出 A[i] ，用二分查找在数组 B 中找到 A[i] 可以插入的位置，假设 A[i] 在 B 中的插入位置是 j，那么 A[i] 在整个合并数组中的位置就是 (i + j) ，因为要求的中位数的位置是 (m + n) / 2，通过比较 (i + j) 和 (m + n) / 2 的大小可以每次舍弃 A 的一部分，从而收敛数组 A。用同样的方法可以收敛数组 B。但是这样的复杂度是 O(log m * log n)，复杂度大于 O(log(m + n))，显然不是最优的
b. 那如果不是直接使用二分查找算法，而是借用二分查找的思想呢？就是每次有选择地舍弃掉数组的一部分，从而达到收敛数组缩小查找范围的效果
i. 我们重新看题目，要找中位数，就是要找第 k 大的数（k = (L / 2 + 1)，其中L 是上面提到的合并后新数组的长度，当 L 是偶数时，要求第 (L / 2) 大和第 (L / 2 + 1) 大的两个数）。当我们舍弃掉一部分，假设舍弃部分的长度为 length，那么接下来就是在剩下的数组里求第 (k - length) 大的数。逐层缩小范围，直到两数组其中一个走完，或者要求的是第 1 大的元素，就可以直接返回结果了
ii. 那如何“选择”要舍弃哪部分呢？既然是要找合并后的数组 C 的第 k 大元素，即 C[k-1]，那如果我们从 A 和 B 中分别取前 k/2 个元素，其中必然有一部分是是在数组 C 的前 k 个数里。设 mid = k / 2，当 A[mid - 1] < B[mid - 1] 时，可以断定 A 的前 mid 个元素是在 C 的前 k 个数里（此处可用反证法得证），那么我们则舍弃 A 的前 mid 个元素。反之则舍弃 B 的前 mid 个元素。现在数组 A 或者 B 已经舍弃掉 k/2 个元素，缩小查找范围了，那接下来可以按照同样的方法继续选择吗？当然！现在剩下总共 (L - mid) 个元素，且 A 和 B 依旧有序，要找的是第 (k - mid) 大的元素，所以我们可以按照上面的方法继续递归选择下去，直到找到目标元素！
复杂度分析：每次从合并后数组 C 里减少 k/2 个元素，直到找到目标元素。所以时间复杂度是 O(log L) = O(log (m + n)) ！
参考程序
class Solution:
"""
@param A: An integer array.
@param B: An integer array.
@return: a double whose format is *.5 or *.0
"""
def findMedianSortedArrays(self, A, B):
m, n = len(A), len(B)
if m == 0 and n == 0:
return 0.0
total = m + n
if total % 2 == 1:
return self.kth_largest(A, B, total / 2 + 1) * 1.0
else:
a = self.kth_largest(A, B, total / 2)
b = self.kth_largest(A, B, total / 2 + 1)
return (a + b) / 2.0
def kth_largest(self, A, B, kth):
m, n = len(A), len(B)
if m == 0:
return B[kth-1]
if n == 0:
return A[kth-1]
if kth == 1:
return min(A[0], B[0])
mid = kth / 2
a, b = float("inf"), float("inf")
if m >= mid:
a = A[mid - 1]
if n >= mid:
b = B[mid - 1]
if a < b:
return self.kth_largest(A[mid:], B, kth - mid)
else:
return self.kth_largest(A, B[mid:], kth - mid)
面试官角度分析
这道题是二分方法的拓展运用，并且需要对二分有比较高的理解，比如怎么样通过猜测试一试二分来解决问题。如果能够达到二分的方法，当然必然是Strong Hire的等级
