Median of Two Sorted Array LeetCode

这个题也可以是findKthElement from two sorted Array。 思路很简单就是不停的把A，B两个Array分别切成两段。这样比较中间值，把小值得小的部分和大数的大的部分（估计只有我自己懂）去掉。最后终止条件为三种，1. A的size为0,2，B的size为0， 3 Kth为0.
当Kth为0的时候，意味着两边都有一个元素，kth为0，我们就选两个剩余元素小的那个。

难点：实现过程中，下标一定要注意。

public double findMedianSortedArrays(int A[], int B[]) {
        int lenA = A.length;
        int lenB = B.length;
        int total = lenA + lenB;
       
        if (total % 2 != 0) {
            return ((double)findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1));
        } else {
            return (findKthElement(A, B, total/2 - 1, 0, lenA - 1, 0, lenB - 1) +
                    findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1)) /2;
        }
    }
   
    private double findKthElement(int[] A, int[] B, int kth, int startA, int endA, int startB, int endB){
        int sizeA = endA - startA + 1;
        int sizeB = endB - startB + 1;
       
        if (sizeA == 0) return B[startB + kth];
        if (sizeB == 0) return A[startA + kth];
        if (kth == 0) return A[startA] > B[startB] ? B[startB] : A[startA];
       
        //Binary Search
        int midA = sizeA * kth /(sizeA + sizeB);
        int midB = kth - midA - 1;
       
        //Match to the original index
        midA += startA;
        midB += startB;
       
        if (A[midA] < B[midB]) {
            kth -= midA - startA + 1;
            endB = midB;
            startA = midA + 1;
        } else {
            kth -= midB - startB + 1;
            endA = midA;
            startB = midB + 1;
        }
        return findKthElement(A, B, kth, startA, endA, startB, endB);
    }