4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

原题链接：median-of-two-sorted-arrays

题目分析

就是求两个有序数组合并后的中位数。O(n)的解法比较直观，直接merge两个数组，然后求中间值。而对于O(log(m+n))显然是用二分搜索了，相当于“Kth element in 2 sorted array”的变形。如果(m+n)为奇数，那么找到“(m+n)/2+1 th element in 2 sorted array”即可。如果（m+n）为偶数，需要找到(m+n)/2 th 及(m+n)/2+1 th，然后求平均。

这里假设两个原序列是升序排列的，假设数组A和B的元素个数都大于k/2，我们比较A的第k/2小的元素和B的第k/2小的元素，即A[k/2-1]和B[k/2-1]。共有三种情况：>、<和=。

1、A[k/2-1]<B[k/2-1]：这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。也就是说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
2、A[k/2-1]>B[k/2-1]：同理，B[0]到B[k/2-1]的元素被抛弃。
3、A[k/2-1]=B[k/2-1]：这时就已经找到了第k小的数，也即这个相等的元素。

两种边界条件：

1、如果A或者B为空，则直接返回B[k-1]或者A[k-1]，也就是在另一个非空序列中寻找 Kth；
2、如果k为1，我们只需要返回A[0]和B[0]中的较小值；

代码如下

double findKth(int a[], int m, int b[], int n, int k)
{
    //始终保持m<=n
    if (m > n)
        return findKth(b, n, a, m, k);

    //两种边界条件
    if (m == 0)
        return b[k - 1];//m为0，则在b中寻找第k小的值
    if (k == 1)    //k为1，返回两个数组中最小的
        return min(a[0], b[0]);

    //将k分成两部分
    int pa = min(k / 2, m), pb = k - pa;       //这里保证了pa+pb=k
    if (a[pa - 1] < b[pb - 1])
        return findKth(a + pa, m - pa, b, n, k - pa);//a的左半部分被摒弃
                                                     //A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。
                                                     //换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
                                                     //然后寻找第k小的值就变成寻找第k-pa小的值
    else if (a[pa - 1] > b[pb - 1])                  //b的左半部分被摒弃
        return findKth(a, m, b + pb, n - pb, k - pb);
    else
        return a[pa - 1];   //相等的话返回其值
}

class Solution
{
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        int total = m + n;
        if (total & 0x1)                               //如果是奇数，返回中间那个
            return findKth(A, m, B, n, total / 2 + 1);
        else                                            //否则返回中间两个数的均值
            return (findKth(A, m, B, n, total / 2)
            + findKth(A, m, B, n, total / 2 + 1)) / 2;
    }
};

4. Median of Two Sorted Arrays