学步园

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

oj上挺有趣的题目，对简单的问题进行复杂度的优化

class Solution
{
public:
  int KthNum(int A[], int m, int B[], int n, int k){
       if(m > n) return KthNum(B,n,A,m,k);
       if(m==0) return B[k-1];
       if(k==1) return min(A[0],B[0]);
       int a = min(m,k/2), b = k - a;
       if(A[a-1] < B[b-1]) 
        return KthNum(A+a,m-a,B,n,k-a);
       else if(A[a-1] > B[b-1])
        return KthNum(A,m,B+b,n-b,k-b);
       else 
        return A[a-1];
  }
   double findMedianSortedArrays(int A[], int m, int B[],int n){
    if((m+n)/2==0)
      return KthNum(A,m,B,n,(m+n)/2+1);
    else 
      return (KthNum(A,m,B,n,(m+n)/2)+KthNum(A,m,B,n,(m+n)/2+1))/2;
   }
};