一个求中位数的问题
最近遇到一道题目是这样的：给定两个已排序数组，求这两个数组所有元素的下中位数。求版上大神给出一个运行时间很快的解决办法。类似合并排序的MERGE就太慢了，最好是O（N）以下的

[解决办法]
log(n)*log(m)是朴素的。稍微修改一下就可以得到log(n)+log(m)的算法：
假设我们需要寻找k-th element（中位数就是k=(m+n)/2）。我们依然二分查找i，使得a[i]在a并b里面的rank是k。
朴素做法是每次定位一个a[i]的时候，二分b获取它在b里的rank。但实际上我们并不需要这个。如果我们的i满足b[k-i]<=a[i]<b[k-i+1]，那么a[i]在a并b的rank就是k。而如果j<i的话，b[k-j+1]<a[j]。如果j>i的话，b[k-j]>a[i]。这样，如果中位数在a里的话，就可以用二分的办法，在log(n)的时间里做出这个中位数。如果不在a里的话，那就再多花log(m)的时间在b里找出来。所以总复杂度是log(n)+log(m)。