http://leetcode.com/2011/03/median-of-two-sorted-arrays.html

TwoArrayMedian

public class Solution {
    /*
    Special cases:
    * A.length == 0 && B.length == 0
    * A.length != 0 && B.length == 0
    * A.length == 1 && B.length == 1
    
    [2], [1,3,4]
    */
    public double findMedianSortedArrays(int A[], int B[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length == 0 && B.length == 0) {
            return 0;
        } else if(A.length == 0) {
            return findMedian(B);
        } else if(B.length == 0) {
            return findMedian(A);
        } else if(A.length == 1 && B.length == 1) {
            return (A[0] + B[0]) / 2.0;
        } else {
            double mA = findMedian(A), mB = findMedian(B);
            // watch out for cases when both two arrays become empty in the next recursive call
            // need to consider odd and even cases when eliminating non-medians
            int deduction = A.length < B.length ? (A.length + 1) / 2 : (B.length + 1) / 2;
            if(mA > mB) {
                return findMedianSortedArrays(Arrays.copyOfRange(A, 0, A.length - deduction), Arrays.copyOfRange(B, deduction, B.length));
            } else if(mA < mB) {
                return findMedianSortedArrays(Arrays.copyOfRange(A, deduction, A.length), Arrays.copyOfRange(B, 0, B.length - deduction));
            } else { // mA == mB
                return mA;
            }
        }
    }
    
    // assume a.length > 0
    /*
    Special cases:
    a.length == 1
    a.length == 2
    */
    public double findMedian(int a[]) {
        if(a.length % 2 == 1) {
            return a[a.length/2];
        } else {
            return (a[a.length/2 - 1] + a[a.length/2])/2.0;
        }
    }
}