两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
在线评测地址：LintCode 领扣
说明
中位数的定义：
这里的中位数等同于数学定义里的中位数。
中位数是排序后数组的中间值。
如果有数组中有n个数且n是奇数，则中位数为A[(n-1)/2]
A[(n−1)/2]。
如果有数组中有n个数且n是偶数，则中位数为 (A[n / 2] + A[n / 2 + 1]) / 2
(A[n/2]+A[n/2+1])/2.
比如：数组A=[1,2,3]的中位数是2，数组A=[1,19]的中位数是10。
样例1
输入:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
输出: 3.5
样例2
输入:
A = [1,2,3]
B = [4,5]
输出: 3
算法：归并
解题思路
最简单的思路是将两个数组合并，然后返回新数组的中位数。九章算法班中讲过，两个有序数组的合并是经典归并排序算法的一步，我们可以新开一个数组，保存合并后的结果。但是我们这样会做额外的工作，因为我们不必保存整个新数组，只需要知道新数组的中位数即可。
因此，更简便的方法是，使用双指针分别对两个数组遍历，比较两个指针下的元素大小，每次移动更小的指针，通过移动次数确定中位数的位置。
算法流程
令指针p1和p2分别指向两个数组，初始指向位置0。我们需要遍历(m + n)/2 + 1次，每次比较两个位置的元素，在第k次比较时，较小的那个值就是两个数组中第k + 1小的数。如果一个指针已经走到了数组末尾，那么移动另一个指针，否则每次将指向较小数的指针后移，直到遍历到中位数。
为了将奇偶情况合并，在代码中用了left和right保存中间值，如果是奇数直接返回right，如果是偶数就返回(left + right) / 2。
复杂度分析
复杂度分析：
时间复杂度：O(m+n)，m和n分别是两个数组的长度。双指针遍历两个数组，指针移动次数是0(m+n)级。
空间复杂度：O(1)。
public class Solution {
/*
* @param A: An integer array
* @param B: An integer array
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length, n = B.length;
int p1 = 0, p2 = 0;
int left = -1, right = -1;
for (int i = 0; i < (m + n) / 2 + 1; i ++){
left = right;
// p2 右移
if (p1 >= A.length || p2 < B.length && A[p1] > B[p2]){
right = B[p2++];
}
// p1 右移
else {
right = A[p1++];
}
}
return (m + n) % 2 == 1 ? right : (left + right) / 2.0;
}}
二分和快速选择等更多解法见：