【Leetcode】Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

更一般的问题是查找两个数据的第K小/大元素。

除了利用归并过程查找外还有更优的方法：利用二分的思想，充分利用数组已经分别有序的条件，使得每比较一个数，就可以确定该数组中一部分元素是位于第K个位置之前还是之后。因为有两个数组，两者的元素之间大小关系未知，所以应该比较数组的第[k/2]个元素，比较A[k/2 - 1]和B[k/2 - 1]后，可以确定两个数组中的一个里面的前k/2个元素一定是所有元素前K个中的。这样就把问题规模缩小了。

要注意特殊情况的处理，使A的长度总小于B有利于代码的简化。

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int cnt = m + n;
        if (cnt & 0x1) {
            return findKth(A, m, B, n, cnt / 2 + 1);                
        } else {
            return (findKth(A, m, B, n, cnt / 2)
                + findKth(A, m, B, n, cnt / 2 + 1)) / 2.0;
        }
    }
    int findKth(int A[], int m, int B[], int n, int k) {
        if (m > n) return findKth(B, n, A, m, k);
        if (m == 0) return B[k - 1];
        if (k == 1) return min(A[0], B[0]);
        
        int ia = min(k / 2, m), ib = k - ia;
        if (A[ia - 1] < B[ib - 1]) {
            return findKth(A + ia, m - ia, B, n, k - ia);
        } else if (A[ia - 1] > B[ib - 1]) {
            return findKth(A, m, B + ib, n - ib, k - ib);
        } else {
            return A[ia - 1];
        }
    }
};