来源：http://www.cnblogs.com/qi09/archive/2011/10/18/2216844.html
题目：现在有两个排好序的整数数组，a[N]和b[N]，要求写一个函数，功能为返回两个数组中第N大数和第N+1大数的中间值，即求解两者的和除以2。
函数原型：double getMedian( int a[], int b[] );
下面，我们先来分析一个类似的问题，假设a和b都是升序的，分别有n1和n2个元素，求两个数组合并后第k大元素值。
分别取两个数组中间索引的数，a[x]和b[y]，比较两个数的大小：
if( a[x] <= a[y] )
——————————————————————————————————————————————————————————————
如果k <= x+y+1，则可以判断出b[y]以及b[y]后面的元素都可以排除在外，减小搜索规模。
如果k > x+y+1，则可以判断出a数组的前半部分元素都不符合条件，减少a一半的搜索规模。
该算法利用了递归的思想，结束条件是：
a中元素排除出去，则选择b中得第k大元素；
b中元素全部排除，选择a中第k大元素。
——————————————————————————————————————————————————————————————
实现的代码如下：
#include <stdio.h>
#include <stdlib.h>
#define N 5
int a[N] = {1, 2, 3, 4, 5};
int b[N] = {4, 5, 6, 7, 8};
//获取数组a中从s1到n1个元素
//数组b中s2到n2个元素，合并后的第k大元素
int getMedian( int s1, int n1, int s2, int n2, int k ) {
//x和y分别记录中间值的索引
int x, y;
x = (s1 + n1) / 2; //记录a的中位数索引
y = (s2 + n2) / 2; //记录b的中位数索引
if( s1 > n1 )
return b[s2+k-1];
if( s2 > n2 )
return a[s1+k-1];
if( a[x] <= b[y] ) {
if( k <= (x-s1) + (y-s2) + 1 ) {
return getMedian( s1, n1, s2, y-1, k );
}
else {
return getMedian( x+1, n1, s2, n2, k-(x-s1)-1 );
}
}
else {
if( k <= (x-s1)+(y-s2)+1 ) {
return getMedian( s1, x-1, s2, n2, k );
}
else {
return getMedian( s1, n1, y+1, n2, k-(y-s2)-1 );
}
}
return 0;
}
int main() {
int i;
i = getMedian(0, 4, 0, 4, 5);
printf( "%d\n", i );
return 0;
}
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
