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)).

You may assume nums1 and nums2 cannot be both empty.

解法

1、查找第k小的数
对于数组A，前p个元素A[0]、A[1]、...、A[p-1]，有p-1个元素不大于A[p-1]，同样，对于数组B，前k-p个元素B[0]、B[1]、...、B[k-p-1]，有k-p-1个元素不大于B[k-p-1]。比较A[p-1]和B[k-p-1]存在三种情况：
1) 若A[p-1] = B[k-p-1]，那么共有(p-1)+(k-p-1)+1=k-1个元素不大于A[p-1]，即A[p-1]是第k小的数；
2) 若A[p-1] < B[k-p-1]，那么第k小的数不可能在区间A[0,p-1]之内。反证法证明：不妨设A[p-1]是第k小的数，也就是说最多只有p-1个数不比它大，而B[k-p-1]大于A[p-1]，所以B[k-p-1]之后的所有数都大于A[p-1]，这样即使B[k-p-1]之前的所有数都不比A[p-1]大，B中也只能找到k-p-1个数不比A[p-1]大，那么A和B中最多只有(p-1)+(k-p-1)=k-2个数不大于A[p-1]，因此A[p-1]不可能是第k小的数；同样的，B[k-p-1]之后的数也不可能是第k小的数，因为它至少是B[k-p]，前面有k-p个数不比B[k-p]大，再加上A[0,p-1]有p个数不比B[k-p]大，因此至少有k-p+p=k个数不比B[k-p]大，也就是说B[k-p]至少是第k+1小的数。舍弃区间之后，问题就变成寻找第k-p小的数。
3) 若A[p-1] > B[k-p-1]，同理可舍去B[0,k-p-1]区间和A[p-1]之后的区间。

2、查找中位数
如果合并后的总元素个数为奇数，则中位数的下标是n/2+1，如果为偶数，则中位数是下标n/2和下标n/2+1两个元素的平均值。

参考资料

https://blog.csdn.net/lxhpkm01/article/details/53823595
https://www.cnblogs.com/davidluo/articles/k-smallest-element-of-two-sorted-array.html

#include <stdio.h>

int findMedian(int *a, int m, int *b, int n);
int findk(int *a, int m, int *b, int n, int k);

int main()
{
    int a[] = {1,3,5,7,9};
    int b[] = {2,4,6,8};
    int m = sizeof(a)/sizeof(int);
    int n = sizeof(b)/sizeof(int);
    int median;

    median = findMedian(a,m,b,n);
    printf("the median is: %d\n",median);

    return 0;
}

/**
 * 查找中位数
 */
int findMedian(int *a, int m, int *b, int n)
{
    int len = m + n;

    if ((len&1) == 0) { // len 为偶数
        return (findk(a,m,b,n,len/2) + findk(a,m,b,n,len/2+1))/2;
    } else { // len 为奇数
        return findk(a,m,b,n,len/2+1);
    }
}

/**
 * 查找第k小的数
 */
int findk(int *a, int m, int *b, int n, int k)
{
    if (m == 0) {
        return b[k-1];
    }
    if (n == 0) {
        return a[k-1];
    }
    if (k == 1) {
        return a[0] < b[0] ? a[0] : b[0];
    }

    if (m > n) {
        return findk(b,n,a,m,k);
    }

    int i = m < k/2 ? m : k/2;
    int j = k - i;

    if (a[i-1] == b[j-1]) {
        return a[i-1];
    } else if (a[i-1] < b[j-1]) {
        return findk(a+i,m-i,b,j,k-i);
    } else {
        return findk(a,i,b+j,n-j,k-j);
    }
}