Median of Two Sorted Arrays

 1 public class Solution {
 2     public double findMedianSortedArrays(int A[], int B[]) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         int aLen = A.length;
 6         int bLen = B.length;
 7         if((aLen + bLen) % 2 ==0){
 8             return (getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2) + getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2 + 1)) / 2.0;
 9         } else {
10             return getKthElement(A, 0, aLen - 1, B, 0, bLen - 1, (aLen + bLen) / 2 + 1);
11         }
12     }
13     
14     public int getKthElement(int A[], int aBeg, int aEnd, int B[], int bBeg, int bEnd, int k){
15         if(aBeg > aEnd){
16             return B[bBeg + (k - 1)];
17         }
18         if(bBeg > bEnd){
19             return A[aBeg + (k - 1)];
20         }
21         
22         int aMid = (aBeg + aEnd) >> 1;
23         int bMid = (bBeg + bEnd) >> 1;
24         int len = aMid - aBeg + bMid - bBeg + 2;
25         
26         if(len > k){
27             if(A[aMid] < B[bMid]){
28                 return getKthElement(A, aBeg, aEnd, B, bBeg, bMid - 1, k);
29             } else {
30                 return getKthElement(A, aBeg, aMid - 1, B, bBeg, bEnd, k);
31             }
32         } else {
33             if(A[aMid] < B[bMid]){
34                 return getKthElement(A, aMid + 1, aEnd, B, bBeg, bEnd, k - (aMid - aBeg + 1));
35             } else {
36                 return getKthElement(A, aBeg, aEnd, B, bMid + 1, bEnd, k - (bMid - bBeg + 1));
37             }
38         }
39     }
40 }