Description

There are two sorted arrays _A _and _B _of size _m _and _n _respectively. Find the median of the two sorted arrays.

Example

GivenA=[1,2,3,4,5,6]andB=[2,3,4,5], the median is3.5.

GivenA=[1,2,3]andB=[4,5], the median is3.

Solution

比对A[k/2]和B[k/2],如果A[k/2]比较小，那么A的前k/2必然在前k个里面，所以把A的前k/2项去掉，继续比对剩下的第(k - k/2)项的大小
注意是k - k/2而不是k/2.
如果数据长度差距很大，比如A的长度小于k/2，那么B的前k/2项必定全在合起来的前k项中，毕竟A中剩下的数都不足k-k/2个。此时，把A的k/2项假定为max value以强制去掉B的前k/2项

public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        if (A == null || B == null) {
            return 0.0;
        }

        int length = A.length + B.length;
        if (length % 2 == 1) {
            return findMedianSortedArray(A, 0, B, 0, length / 2 + 1);
        } else {
            return (findMedianSortedArray(A, 0, B, 0, length / 2 + 1) + findMedianSortedArray(A, 0, B, 0, length / 2)) / 2.0;
        }
    }

    private double findMedianSortedArray(int[] A, int startA, int[] B, int startB, int k) {
        if (startA >= A.length) {
            return B[startB + k - 1];
        }

        if (startB >= B.length) {
            return A[startA + k - 1];
        }

        if (k == 1) {
            return Math.min(A[startA], B[startB]);
        }

        int valA = startA + k/2 - 1 < A.length ? A[startA + k/2 - 1] : Integer.MAX_VALUE;
        int valB = startB + k/2 - 1 < B.length ? B[startB + k/2 - 1] : Integer.MAX_VALUE;
        if (valA < valB) {
            return findMedianSortedArray(A, startA + k/2, B, startB, k - k/2); //k - k/2, not k/2
        } else {
            return findMedianSortedArray(A, startA, B, startB + k/2, k - k/2);
        }
    }
}