《两个已经排好序的数组,找中位数.docx》由会员分享，可在线阅读，更多相关《两个已经排好序的数组,找中位数.docx（2页珍藏版）》请在三一办公上搜索。
1、两个已经排好序的数组,找中位数两个已经排好序的数组，找中位数 题目：现在有两个排好序的整数数组，aN和bN，要求写一个函数，功能为返回两个数组中第N大数和第N+1大数的中间值，即求解两者的和除以2。 函数原型：doublegetMedian( int a, int b ); 下面，我们先来分析一个类似的问题，假设a和b都是升序的，分别有n1和n2个元素，求两个数组合并后第k大元素值。 分别取两个数组中间索引的数，ax和by，比较两个数的大小： if( ax = ay ) 如果k x+y+1，则可以判断出a数组的前半部分元素都不符合条件，减少a一半的搜索规模。 该算法利用了递归的思想，结束条件是
2、： a中元素排除出去，则选择b中得第k大元素； b中元素全部排除，选择a中第k大元素。 实现的代码如下： #include #include #define N 5 int aN = 1, 2, 3, 4, 5; int bN = 4, 5, 6, 7, 8; /获取数组a中从s1到n1个元素 /数组b中s2到n2个元素，合并后的第k大元素 intgetMedian( int s1, int n1, int s2, int n2, int k ) /x和y分别记录中间值的索引 int x, y; x = (s1 + n1) / 2; /记录a的中位数索引 y = (s2 + n2) / 2;
3、/记录b的中位数索引 if( s1 n1 ) return bs2+k-1; if( s2 n2 ) return as1+k-1; if( ax = by ) if( k = (x-s1) + (y-s2) + 1 ) returngetMedian( s1, n1, s2, y-1, k ); else returngetMedian( x+1, n1, s2, n2, k-(x-s1)-1 ); else if( k = (x-s1)+(y-s2)+1 ) returngetMedian( s1, x-1, s2, n2, k ); else returngetMedian( s1, n1, y+1, n2, k-(y-s2)-1 ); return0; int main inti; i = getMedian(0, 4, 0, 4, 5); printf( %dn, i ); return0;
