Leet Code : Median of Two Sorted Arrays .cpp

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total=m+n;
        if(total&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;
    }
    
    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];
        if(k==1)return min(A[0],B[0]);
        
        int pa=min(m,k/2),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];
    }
};

find kth element in two sorted Arrays

double findKth(int A[],int m,int B[],int n,int k)
假定m < n .
使用两个指示器pa、pb 且使 pa+pb=k;

最坏情况下m 、n都大于 k/2 ，让pa=k/2 pb=k/2
则每次判断A[k/2-1] B[k/2-1]的大小，舍弃一半的查找区间，并减小k ，当k=1时返回区间头的最小值。

实际情况时，看较短区间长度是否为空，若为空直接返回第二个区间中第k个元素即可。

           pa
           ↓
A    |    |   |   |   |   |   |   |

               pb
               ↓
B    |    |   |   |   |   |   |   |   |   |