要求时间复杂度是O（log（m+n）），一看时间复杂度是log，那肯定是采用了二分(分治)的方法才能达到log的效果～～～
废话不多说，直接开干，顺带说一下，c语言是世界上最好的语言～～～～～～
设有如下两个有序数组：
a[3] = {1,2,3};
b[6] = {2,3,4,5,6,7}
以下分析步骤
- 求第k大的数，我们设这k个数，包含在数组a中的有p个，包含b中的有q个，则有p+q=k; a数组的起始索引astart = 0，b数组的起始索引bstart=0
- 那么怎么确定p呢，我们设p = min（k/2，m）,这里我们假设m是比较短的那个数组的长度，取p= k/2和m的较小者，保证数组不越界。则q=k-p
- 以 a b 为例 m = 3，n = 6； 假如要求中位数（k=4）；p=min（k/2，m）= 2，q= k-p=2
- 如果 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);
}
}
