两个排序数组的中位数

时间复杂度为O(log(m+n))，直接想到二分法。

求两个排序数组的中位数，即求两个排序数组中：

1. 第k个数（k=(m+n+1)/2，如果m+n为奇数）
2. 第k个数与第k+1个数的平均值（k=(m+n)/2,k+1=1+(m+n)/2，如果m+n为偶数）

问题转化为求两个数组中的第k个数，分情况讨论：

1. 如果一个数组为空，另一个数组不为空，直接返回另一个数组第k个值
2. 如果两个数组都不为空，且k==1，返回两个数组起始值中较小的那一个
3. 如果两个数组都不为空，且k!=1，那么采取类似二分法的思想，每次从其中一个数组中排除一部分值，具体见代码

//
// Created by jt on 2020/8/15.
//
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m + n) % 2 != 0) return findKth(A, m, B, n, (m + n + 1) / 2);
        else return (findKth(A, m, B, n, (m + n) / 2) + findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
    }
    double 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 pa = min(k / 2, m), pb = k - pa;
        if (A[pa - 1] < B[pb - 1]) return findKth(A + pa, m - pa, B, n, k - pa);
        else if (A[pa - 1] > B[pb - 1]) return findKth(A, m, B + pb, n - pb, k - pb);
        else return A[pa - 1];
    }
};