Median of Two Sorted Arrays (LeetCode Array)

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

Idea: Think about the process of merging two sorted array. Each time we need to compare the first element of A and the first element of B then append the smaller one to the merged array. In our question, we do not need to finish the merge process but need to stop if the (m+n)/2'th elements has been merged. If we use the merge algorithm, the time will be O(m+n) in worse case. So we can not merge the elements one by one, instead, we need an algorithm to throw away a bunch of impossible elements in each step.

Assume integer k=(m+n)/2. When m+n is even, the median is the average of the k'th and the k+1'th elements of the merged array. When m+n is odd, the median is the k'th element of the merged array. Now we talk about how to throw away a bunch of impossible elements in each step to find the k'th element. Similar to binary search, let us first let array A contribute k/2 elements and let array B contribute k/2 elements. If A[k/2-1]>B[k/2-1], that means the elements in array B will go faster than the elements in array A during the merge. Therefore, when B[k/2-1] goes to the merged array, the number of elements leaving from A to the merged array should not be over k/2. In other words, the k'th element can not be from B[0]->B[k/2-1].  So we can throw away these elements in B. Vice era for A if A[k/2-1]<=B[k/2-1]. This can be formally proved by contradiction.

Time: O(lg(m+n)) Space: O(lg(m+n)).

Code: 

 public class Solution {  
   public double findMedianSortedArrays(int A[], int B[]) {  
     int len=A.length+B.length;  
     int k=len/2;  
     if(len%2==0)  
       return (findKth(A,0,B,0,k)+findKth(A,0,B,0,k+1))/2.0;  
     else  
       return findKth(A,0,B,0,k+1);  
   }  
   double findKth(int A[],int aStart,int B[],int bStart,int k)  
   {  
     if(aStart>=A.length)  
       return B[bStart+k-1];  
     if(bStart>=B.length)  
       return A[aStart+k-1];  
     if(k==1)  
       return Math.min(A[aStart],B[bStart]);  
     int aMid=aStart+k/2-1<A.length?A[aStart+k/2-1]:Integer.MAX_VALUE;  
     int bMid=bStart+k/2-1<B.length?B[bStart+k/2-1]:Integer.MAX_VALUE;  
     if(aMid>bMid)  
       return findKth(A,aStart,B,bStart+k/2,k-k/2);  
     else  
       return findKth(A,aStart+k/2,B,bStart,k-k/2);  
   }  
 }