Median of Two Sorted Arrays.txt

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if ((m+n)%2)
            return findKth(A, m, B, n, (m+n+1)/2);
        else
            return (findKth(A, m, B, n, (m+n)/2) + findKth(A, m, B, n, (m+n)/2+1))/(double)2;
        
    }
    int findKth(int A[], int m, int B[], int n, int k) {
        int i = ((double)m/(m+n))*(k-1);
        int j = (k-1) - i;
        int ai_1 = (i==0)?INT_MIN:A[i-1];
        int bj_1 = (j==0)?INT_MIN:B[j-1];
        int ai = (i==m)?INT_MAX:A[i];
        int bj = (j==n)?INT_MAX:B[j];
        
        if ((ai_1 <= bj) && (bj <= ai))
            return bj;
        if ((bj_1 <= ai) && (ai <= bj))
            return ai;
        if (ai < bj)
            return findKth(A + i + 1, m - i - 1, B, n, k - i - 1);
        else
            return findKth(A, m, B + j + 1, n - j - 1, k - j - 1);
    }
};