Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).
https://leetcode.com/problems/median-of-two-sorted-arrays/

分析：
对于一个数x和连个排好序的数组a，b。如果x在a中是第ax个数，在b中是第bx个数。那么，x在a，b合并后的数组中是第（ax + bx - 1）个数。

充分利用两个数组已经排好序的特征，取a中前cntA = （k * lenA /（lenA + lenB））个元素（按数组中元素比例取元素，以避免边界情况），取b中cntB = k - 1 - cntA个元素。比较a[begA + cntA]和b[begB + cntB]：

1. a[begA + cntA] == b[begB + cntB]，a[begA + cntA]即为a，b中第k个元素
2. a[begA + cntA] < b[begB + cntB]，a[begA + cntA]，丢弃a[begA ~ begA + cntA]共cntA + 1个元素
3. a[begA + cntA] > b[begB + cntB]，a[begA + cntA]，丢弃b[begB ~ begB + cntB]共cntB + 1个元素

寻找两数组中第k大元素的函数如下：

int findKth(int[] a, int[] b, int k, int begA, int endA, int begB, int endB) {
    int lenA = endA - begA + 1;
    int lenB = endB - begB + 1;
    
    if(lenA == 0) return b[begB + k];
    if(lenB == 0) return a[begA + k];
    if(k == 0) return Math.min(a[begA], b[begB]);
    
    int cntA = k * lenA / (lenA + lenB);
    int cntB = k - 1 - cntA;
    
    if(a[begA + cntA] == b[begB + cntB]) return a[begA + cntA];
    else if(a[begA + cntA] < b[begB + cntB]) {
        k = k - cntA - 1;
        begA = begA + cntA + 1;
        endB = begB + cntB;
    } else {
        k = k - cntB - 1;
        begB = begB + cntB + 1;
        endA = begA + cntA;
    }
    return findKth(a, b, k, begA, endA, begB, endB);
}

寻找两数组中位数的主函数为：

public double findMedianSortedArrays(int[] a, int[] b) {
    int lenA = a.length, lenB = b.length;
    if((lenA + lenB) % 2 == 0) {
        return  (findKth(a, b, (lenA + lenB) / 2, 0, lenA - 1, 0, lenB -1) + 
        findKth(a, b, (lenA + lenB) / 2 - 1, 0, lenA - 1, 0, lenB - 1)) * 0.5;
    } else {
        return (double)findKth(a, b, (lenA + lenB) / 2, 0, lenA - 1, 0, lenB - 1);
    }
}