median of two sorted arrays example

median-two-sorted-arrays.cpp

int getOrderStatistic(const vector<int>& A, int as, int ae, const vector<int>& B, int bs, int be, int k) {  
    int n = ae - as + 1, m = be - bs + 1;
    if (n > m)
        return getOrderStatistic(B, bs, be, A, as, ae, k);
    if (n <= 0)
        return B[bs + k - 1];
    if (k == 1)
        return min(A[as], B[bs]);
    int pa = min(k/2, n), pb = k - pa;
    return A[as+pa-1] <= B[bs+pb-1]
        ? getOrderStatistic(A, as+pa, ae, B, bs, bs+pb-1, k-pa)
        : getOrderStatistic(A, as, as+pa-1, B, bs+pb, be, k-pb);
}

double findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
    int n = A.size(), m = B.size();
    return (n + m) % 2 != 0
        ? getOrderStatistic(A, 0, n-1, B, 0, m-1, (n+m)/2 + 1)
        : (getOrderStatistic(A, 0, n-1, B, 0, m-1, (n+m)/2) + getOrderStatistic(A, 0, n-1, B, 0, m-1, (n+m)/2 + 1)) / 2.0;
}