顺序存储双有序列的二分折叠查找算法

目录 编程, 计算机

源于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.

长按识别二维码关注《边际效应》
长按识别二维码关注《边际效应》

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注