两个有序数组的第K大的数，看不会包打！

要求时间复杂度是O（log（m+n）），一看时间复杂度是log，那肯定是采用了二分(分治)的方法才能达到log的效果～～～

废话不多说，直接开干，顺带说一下，c语言是世界上最好的语言～～～～～～
设有如下两个有序数组：

a[3] = {1,2,3}; 
b[6] = {2,3,4,5,6,7}

以下分析步骤

1. 求第k大的数，我们设这k个数，包含在数组a中的有p个，包含b中的有q个，则有p+q=k; a数组的起始索引astart = 0，b数组的起始索引bstart=0
2. 那么怎么确定p呢，我们设p = min（k/2，m）,这里我们假设m是比较短的那个数组的长度，取p= k/2和m的较小者，保证数组不越界。则q=k-p
3. 以 a b 为例 m = 3，n = 6； 假如要求中位数（k=4）；p=min（k/2，m）= 2，q= k-p=2
4. 如果 a[astart+p-1] < b[bstart+q-1]; 我们就可以把a数组中包括索引p在内的比较小的数都抛弃，形成一个新的数组a' 与 b 再来一次上述过程，如果a[astart+p-1] > b[bstart+q-1]; 就抛弃b中的较小的数 形成一个新的数组b'，与a再来一次；如果相等 那这个数就是要找的中位数

️：循环的结束条件是 如果较短的数组长度为0（比如a数组）了，则返回b[bstart+k-1]; 如果k==1了 则返回 a[astart]与b[bstart]中的较小者

代码如下

float findTheKBigNum(int *a, int *b,int aStart, int bStart, int aLen, int bLen, int k) {
    // 这里使用较短的数组作为a，保证不越界
    if (aLen > bLen) {
        findTheKBigNum(b, a, bStart ,aStart, bLen, aLen, k);
    }
    if (aLen == 0) {
        return b[bStart+k-1];
    }
    if (k == 1) {
        return a[aStart] < b[bStart] ? a[aStart] : b[bStart];
    }
    
    int p1 = k/2 < aLen ? k/2:aLen;
    int p2 = k-p1;
    if (a[aStart+p1-1] < b[bStart+p2-1]) {
        return findTheKBigNum(a, b, aStart+p1, bStart, aLen-p1, bLen, k-p1);
    } else if (a[aStart+p1-1] > b[bStart+p2-1]) {
        return findTheKBigNum(a, b, aStart, bStart+p2, aLen, bLen-p2, k-p2);
    } else {
        return a[aStart+p1-1];
    }
}

查找中位数函数

float mediumNum(int *a, int *b, int m, int n) {
    int k = (m+n)/2;
    if ((m+n)%2 == 0) {
      //  如果合并后的数组长度是偶数，中位数为第k大和第k+1大之和的一半
        return (findTheKBigNum(a, b, 0, 0, m, n, k)+findTheKBigNum（a, b, 0, 0, m, n, k+1))/2;
    } else {
        return findTheKBigNum(a, b, 0, 0, m, n, k+1);
    }
}