median.cc

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int size = m + n;
        if (size & 1) {
            return find_kth((size >> 1) + 1, A, 0, m - 1, B, 0, n - 1);
        } else {
            return (find_kth(size >> 1, A, 0, m - 1, B, 0, n - 1) + find_kth((size >> 1) + 1, A, 0, m - 1, B, 0, n - 1)) / 2.0;
        }
       
    }
    
    double find_kth(int k, int A[], int al, int au, int B[], int bl, int bu) {
        if (au - al > bu - bl) {
            return find_kth(k, B, bl, bu, A, al, au);
        }
        
        if (al > au) {
            return B[bl + k - 1];
        } else if (k == 1) {
            return min(A[al], B[bl]);
        } else {
            int pa = min(au - al + 1, k >> 1);
            int pb = k - pa;
            if (A[al + pa - 1] < B[bl + pb - 1]) {
                return find_kth(k - pa, A, al + pa, au, B, bl, bu);
            } else if (A[al + pa - 1] == B[bl + pb - 1]) {
                return A[al + pa - 1];
            } else {
                return find_kth(k - pb, A, al, au, B, bl + pb, bu);
            }
        }
    }
};