http://blog.csdn.net/kenby/article/details/6833407
http://blog.csdn.net/kenby/article/details/6833407
o(logn)
两种方法：
一、二分查找
中位数只有一个，它前面有 c = (m+n-1)/2 个数比它小。中位数要么出现在数组A中，
要么出现在数组B中，我们先从数组A开始找。考察数组A中的一个元素A[p]， 在数组A中，
有 p 个数比A[p]小，如果数组B中恰好有 c-p 个数比 A[p] 小， 则俩数组合并后就恰好有 c 个数比A[p]小，
于是A[p]就是要找的中位数。 如下图所示：
如果A[p] 恰好位于 B[c-p-1] 和 B[c-p] 之间，则 A[p] 是中位数
如果A[p] 小于 B[c-p-1] ，说明A[p] 太小了，接下来从 A[p+1] ~A[m-1]开始找
如果A[p] 大于 B[c-p] ，说明A[p] 太大了，接下来从 A[0] ~A[p-1]开始找。
如果数组A没找到，就从数组B找。
二、比较两个数组的中位数
ar1[]和ar2[]为输入的数组
算法过程：
1.得到数组ar1和ar2的中位数m1和m2
2.如果m1==m2，则完成，返回m1或者m2
3.如果m1>m2，则中位数在下面两个子数组中
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4.如果m1<m2，则中位数在下面两个子数组中
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5.重复上面的过程，直到两个子数组的大小都变成2
6.如果两个子数组的大小都变成2，使用下面的式子得到中位数：Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2