源于Google的一道笔试题：给出两个升序排列的n维整数数组，求这2n个数中的第n大数。(算法导论：Exercise 9.3-8)
笔试的时候有一个想法，但是写的很草率，回来仔细想了下，把它写出来。我想这个应该是别人已经做过的东西，但我也不知道怎么查，第一次自己写查找算法，在我这就把它叫做“顺序存储双有序列的二分折叠查找算法”吧。其实这个算法好象没什么实际作用，有序列的查找嘛，计算量都不大。
算法描述太累赘了，就写个基本思想吧：把每个数组尾部的指针向前移动n/2个数，然后比较这两个数的大小，如果a中的大，就把这个数与b从尾部开始比较直到某个数小于它，这样，第n个数肯定不在两个指针后面，把两个指针后面的数字个数加起来，作为count。n-count就是执行下次类似查找的n。主要工作量节省在每次跨n/2上。至于最后如何选择第n个数，需要分析一下具体情况。
int search4n(int *a, int *b, int n)
{
int *p,*q,*p1,*q1,range;
p = a+n;
q = b+n;
if( a[0]>b[n-1] ) return a[0];
if( b[0]>a[n-1] ) return b[0];
while(n>1)
{
range = ( n+1 ) / 2;
p1 = p-range;
q1 = q-range;
if( *p1>*q1 ){
n -= range;
p = p1;
q--;
while( *q>*p1 ){
q--;
n--;
}
}
else{
n -= range;
q = q1;
p--;
while(*p>*q1){
p--;
n--;
}
}
}
if( n==0 ) return *p > *q ? *p : *q;
else if( n==1 ) return *(--p) > *(--q) ? *p : *q;
else return 0;
}
其实这个算法可以推而广之到任意两个有序列的第n大数查找，见下面。但是为了控制指针越界需要浪费一些判断语句，其实有很多判断语句只有在足够接近边界时候才起作用。这算法也可以推广到链表，但似乎效率要低些。
int search4n(int *a, int *b, int an, int bn, int n)
{
int *p, *q, *p1, *q1, range;
p = a+an;
q = b+bn;
if( a[0]>b[bn-1] ) return n <= an ? a[an-n] : b[an+bn-n];
if( b[0]>a[an-1] ) return n <= bn ? b[bn-n] : a[an+bn-n];
while( n>1 ){
range = ( n+1 ) / 2;
p1 = p-range>a ? ( q==b ? p-n : p-range) : a;
if(q1==b && *q1>*(p-1)) return *(p-n);
q1 = q-range>b ? ( p==a ? q-n : q-range) : b;
if(p1==a && *p1>*(q-1)) return *(q-n);
if( *p1>*q1 ){
n -= (p-p1);
p = p1;
q--;
while( *q>*p && q>b ){
n--;
q--;
}
*q>*p ? q : q++;
}
else{
n -= (q-q1);
q = q1;
p--;
while( *p>*q && p>a ){
n--;
p--;
}
*p>*q ? p : p++;
}
}
if( n==0 ) return *p<*q ? *p : *q;
else if( n==1 ) return (p1==a || q1==b) ? ( p1==a ? *(--q) : *(--p) ) : ( *(--p)>*(--q) ? *p : *q );
else return 0;
}
算法复杂度：
时间复杂度，显然最优状况下，比较只需要常数次(如果比较次数不包括各种边界条件的比较)；最坏状况下，比较主要在中间那个while双循环，假设n对应的比较次数为f(n)，则f(n)=1+k+f(n-[(n+1)/2]-k)，其中1=<k<[(n+1)/2];f(1)=1;f(2)=2。则f(n)的最大值就是最差情况下的比较次数，我估计不出来，所以无法说它的平均算法复杂度了，但由f(n)的下降速度可以看出比较次数是介于log(n)和n之间的,究竟是多少数量级不太清楚，回头再想想怎么估计平均复杂度，应该是需要考虑k的分布。
空间复杂度，需要4个指针空间和1个整型变量空间，常数级。
我估计这个算法应该不是最优的，尤其对题目来说这种算法肯定不是最优的，因为求中位数的话可以更简单，但它可以推广到任意两有序列的查找，也算是一种途径。不过我觉得这个算法里可能还有漏洞，只是我没检查出来，也该有优化的可能，以后再慢慢想吧。
Copyright © 2005-2006 Solrex Yang. All rights reserved.