题意

找到两个有序数组的中位数

解答一（递归，时间复杂度O(logk)）

首先理解题意两个关键点：有序数组和中位数

• 对于有序数组a，长度为m
  • 如果m为奇数，则中位数为第m/2+1小的数；
  • 如果m为偶数，则中位数为第m/2+1小与第m/2小的数的平均和；
• 对于有序数组a和b，长度分别为m和n
  • 如果m+n为奇数，则两个数组的中位数为第(m+n)/2+1小的数
  • 如果m+n为偶数，则两个数组的中位数为第(m+n)/2+1小和第(m+n)/2小的数平均和；

根据上面性质可知，只要找到第(m+n)/2+1小和第(m+n)/2小的数即可，该题演变成找两个有序数组第k小的数；

如何寻找两个有序数组的第k小数？二分查找

先声明查找第k小数的函数

/* param:
 *      a   数组a起始地址
 *      m   数组a起始地址开始的长度
 *      b   数组b起始地址
 *      n   数组b起始地址开始的长度
 */
int findKth(int* a, int m, int* b, int n, int k);

如果i=k/2，则j=k-i=k/2, 和总共k个数，但这k个数不一定是最小的k个数

• 
  说明的左边部分肯定在最小的k个数里面，右边部分可能存在数在最小的k个数里面；
  这时候需要在和中查找第小的数

findKth(a+i, m-i, b, n, k-i);

• 
  说明的左边部分肯定在最小的k个数里面，右边部分可能存在数在最小的k个数里面；
  这时候需要在和中查找第小的数

findKth(a, m, b+j, n-j, k-j);

• 
  说明找到第k小的数，和总共k个最小的数

二分核心流程：

int i = min(m, k/2), j = k-i;
if (a[i-1] < b[j-1]) {
    return findKth(a+i, m-i, b, n, k-i);
} else if (a[i-1] > b[j-1]) {
    return findKth(a, m, b+j, n-j, k-j);
} else {
    return a[i-1];
}

现在考虑边界情况

• 且
  且
  
  所以当k=1时不能进入上面二分核心流程

if (k==1) return min(a[0], b[0]);`

• 由于要使用a[0]和b[0]，所以a和b必须分别至少有一个元素；如果a没有元素或者b没有元素不能进入k==1的判断条件

if (m == 0) return b[k-1];
if (n == 0) return a[k-1];

• 
  
  
  如果m> n，则需要将数组a和b交换

完整代码：

class Solution {
public:
    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 i = min(m, k/2), j = k - i;
        if (a[i-1] < b[j-1]) {
            return findKth(a+i, m-i, b, n, k-i);
        } else if (a[i-1] > b[j-1]){
            return findKth(a, m, b+j, n-j, k-j);
        } else {
            return a[i-1];
        }
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if ((m+n)%2) {
            return findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
        } else {
            int left = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2);
            int right = findKth(nums1.data(), m, nums2.data(), n, (m+n)/2+1);
            cout<<left<<" "<<right<<endl;
            return (left+right)/2.0;
        }
    }
};

解答二（非递归，时间复杂度O(log(min(m,n)))）

对于数组，有种分隔方式，如下图（a）所示；当的部分长度为时，部分长度为，如下图（b）所示；

• 如果，则，
• 如果，则，
• 如果且，则，

同样的对于数组，有种分隔方式，

• 如果，则，
• 如果，则，
• 如果且，则，
  

如何求数组a和b的中位数？按照上述划分原则，只要把数组a和b划分成left和right两部分，保证，同时，左边元素都小于等于右边元素，则中位数为。

但是数组分偶数和奇数两种情况：

• 如果是偶数，只需要和等分即可，即，又由于整数除法是向下取值的，则，故也满足，中位数为；
• 如果是奇数，将中间元素放到左边，右边将比左边少一个元素，即，中位数为
  

综合上述两个条件，不论m+n是奇数还是偶数，对于数组a和b中位数来说满足j=(m+n+1)/2-i，为了保证，则

故中位数满足的条件是：

• 
• 且

边界条件：
当m+n不论奇数偶数时

• 当时，j=(m+n+1)/2，则最小的数都在数组b，
• 当时，i=(m+n+1)/2，则则最小的数都在数组a，
• 当且，则

当m+n为偶数时，需要

• 当时，数组a都在左边，右边都是b，
• 当时，数组b都在左边，右边都是a，
• 当且，则

当对数组a进行二分查找位置i时，相应的数组b位置j=(m+n+1)/2-i，此时数组a和数组b左右两部分相等，中位数

完整代码：

class Solution {
public:    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);
        int imin = 0, imax = m, i = 0, j = 0, media = 0;
        while (imin <= imax) {
            i = (imin+imax)/2;
            j = (m+n+1)/2 - i;
            if (j-1>=0 && j-1<n && i>=0 && i<m  && nums2[j-1] > nums1[i]) {
                imin = i + 1;
            } else if (i-1>=0 && i-1<m && j>=0 && j< n  && nums1[i-1] > nums2[j]) {
                imax = i - 1;
            } else {    
                if (i == 0) media = nums2[j-1];
                else if (j == 0) media = nums1[i-1];
                else media = max(nums1[i-1], nums2[j-1]);
                break;
            }
        }
        if ((m+n)&1) return media;
        if (i == m) media += nums2[j];
        else if (j == n) media += nums1[i];
        else media += min(nums1[i], nums2[j]);
        return media*0.5;
    }
};