Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

This problem is an implementation of the Find k-th smallest number in two sorted array .

Note that if the total number of elements of two arrays is odd, we need to find the( (A.length + B.length) / 2 + 1 )-th element. If it is even, we need to find that number and the number before that and take the average.

The following code compares between B[j - 1] and A[i], and thus reduces the comparison among B[j - 1], A[i] and B[j]. This may reduce couple lines of code. Yet the trade-off is that each time we only discard 1/4 of the total number of elements in each recursion, even though the solution can still be accepted.

I prefer to write couple more lines. :)

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        if (A == null || B == null)
            throw new NullPointerException("Null array(s)!");
        if (A.length == 0 && B.length == 0)
            return 0.0;
        int len = A.length + B.length;
        if (len % 2 != 0)
            return (double)findMedian(A, 0, B, 0, len / 2 + 1);
        int r1 = findMedian(A, 0, B, 0, len / 2);
        int r2 = findMedian(A, 0, B, 0, len / 2 + 1);
        double rst = (double)(r1 + r2) / 2.0;
        return rst;
        
    }
    private int findMedian(int[] A, int A_start, int[] B, int B_start, int k) {
        if (A_start >= A.length)
            return B[B_start + k - 1];
        if (B_start >= B.length)
            return A[A_start + k - 1];
        if (k == 1)
            return Math.min(A[A_start], B[B_start]);
        //A_key = k / 2 - 1
        //B_key - 1 = k / 2 - 1
        int index_A = A_start + k / 2 - 1;
        int index_B = B_start + k / 2 - 1;
        int A_i = (index_A >= A.length) ? Integer.MAX_VALUE : A[index_A];
        int B_i = (index_B >= B.length) ? Integer.MAX_VALUE : B[index_B];
        if (A_i < B_i)
            return findMedian(A, index_A + 1, B, B_start, k - k / 2);
        else
            return findMedian(A, A_start, B, index_B + 1, k - k / 2);
    }
}

Update: 2015 - 01 - 15
I realize that if I use the code in the post Find k-th smallest number in two sorted array, it will exceed time limit.