Leetcode---Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

就是两个有序数组，求它们组合成的有序数组的中位数。

当然，可以根据我的另一篇博文“两个等长有序数组的中位数”介绍的原理来求，但是。。。那种方法不够简洁。

有一种通用并且简洁优雅的方法来解决这个问题，那就是转化问题为：

有一个长度为m的有序数组A和一个长度为n的有序数组B，求他们合并后的有序数组（从小到大）中第k个数（当然1<=k<=m+n）

这个问题的解法：

取A中第x个数，1<=x<=k && x<=m，若A[x-1]
也就是说，设pa+pb=k，若A[pa-1]
其他情况不再赘述。

代码：

double f(int a[],int m,int b[],int n,int k){
    assert(k<=m+n && k>=1);
    if(m>n)
        return f(b,n,a,m,k);
    if(m==0)
        return b[k-1];
    if(k==1)
        return min(a[0],b[0]);
    else{
        int pa=min(k/2,m);
        int pb=k-pa;
        if(a[pa-1]<b[pb-1])
            return f(a+pa,m-pa,b,n,k-pa);
        else if(a[pa-1]>b[pb-1])
            return f(a,m,b+pb,n-pb,k-pb);
        else
            return a[pa-1];
    }
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int l=m+n;
    if(l%2!=0)
        return f(A,m,B,n,l/2+1);
    else
        return (f(A,m,B,n,l/2)+f(A,m,B,n,l/2+1))/2;
}