求两个有序数组的中位数

题目描述
有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。
思路分析
两个大小分别为m和n的有序数组，我们要找出它们的中位数，而且要求时间复杂度是对数级别的，那么我们自然而然地就会想到二分查找算法，可是要怎么进行呢？寻找这两个数组的中位数相当于在数组A和B中找到中间元素，如果数组元素总数是奇数那么就是最中间的那个元素((m+n)/2+1)，如果是偶数那么就是最中间的两个元素((m+n)/2、(m+n)/2+1)。这样问题就转化成给定两个有序数组，求第k小元素了。
接下来就处理转化来的问题，在数组A中找到第k/2小元素a，在数组B中找到第k/2小元素b，如果a和b相等，那么第k小元素就是a或者b了，如果a小于b，那么总体的第k小元素不可能在a的第k/2小元素之前，那么就可以将其舍弃了，反之如果a大于b，也就可以舍弃b的第k/2小之前的元素了。
当然在实际代码中，数组A和数组B的元素个数可能小于k/2，我们就令其为pa=min(k/2,m or n)，另外一个数组就是第pb=k-pa小元素了。

    double findMedianSortedArrays(int A[], int m, int B[], int n) 
    {
        int total=m+n; //两个数组的元素总个数
        if((total&0x1)) //奇数个，那么中间元素就是第total/2+1小元素了
            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;
    }
    //在数组A和数组B整体中寻找第k小数字
    double findKth(int A[],int m,int B[],int n,int k)
    {
        if(m>n)
            return findKth(B, n, A, m, k); //让元素少的放在前面，方便处理
        if(m==0)
            return B[k-1]; //如果元素少的数组为空，那么就返回另一个数组的第k小元素即可
        if(k==1) //如果求第1小元素
            return min(A[0],B[0]);
        int pa=min(k/2,m),pb=k-pa;
        if(A[pa-1]<B[pb-1])
            return findKth(A+pa, m-pa, B, n, k-pa);
        else if(A[pa-1]>B[pb-1])
            return findKth(A, m, B+pb, n-pb, k-pb);
        else
            return A[pa-1];
    }