4. Median of Two Sorted Arrays

[LLancelot]

参考：https://www.youtube.com/watch?v=ScCg9v921ns

Binary Search

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int lenA = A.length, lenB = B.length;
        if (lenA > lenB) { return findMedianSortedArrays(B,A); }
        if (lenA == 0)
            return ((double)B[(lenB - 1)/2] + (double)B[lenB/2])/2;
        int len = lenA + lenB;
        int A_startK = 0, A_endK = lenA;
        int cutA, cutB;
        while (A_startK <= A_endK) {
            cutA = (A_endK + A_startK) / 2;
            cutB = (len + 1)/2 - cutA;
            double L1 = (cutA == 0) ? Integer.MIN_VALUE : A[cutA-1];
            double L2 = (cutB == 0) ? Integer.MIN_VALUE : B[cutB-1];
            double R1 = (cutA == lenA) ? Integer.MAX_VALUE : A[cutA];
            double R2 = (cutB == lenB) ? Integer.MAX_VALUE : B[cutB];
            if (L1 > R2) {
                A_endK = cutA - 1;
            }
            else if (L2 > R1) {
                A_startK = cutA + 1;
            }
            else {
                if (len % 2 == 0) {
                    return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
                } 
                else {
                    return Math.max(L1, L2);
                }
            }
        }
        return -1;
    }
}