1 class Solution { 2 public: 3     double findMedianSortedArrays(int A[], int m, int B[], int n) { 4         int total = m + n; 5         if(total & 1) 6             return find_kth(A, m, B, n, total/2 + 1); 7         else return (find_kth(A, m, B, n, total/2) + find_kth(A, m, B, n, total/2 + 1))/2.0; 8     } 9     int find_kth(int A[], int m, int B[], int n, int k){10         if(m > n) return find_kth(B, n, A, m, k);11         if(m == 0) return B[k-1];12         if(k == 1) return min(A[0], B[0]);13         14         int ia = min(k/2, m);15         int ib = k - ia;16         17         if(A[ia-1] < B[ib-1])18             return find_kth(A+ia, m-ia, B, n, k - ia);19         else if(A[ia-1] > B[ib-1])20                 return find_kth(A, m, B+ib, n-ib, k - ib);21         else return A[ia-1];22     }23 };