用于数列寻空的蛙跳算法

摘要：提出一种新的蛙跳算法，主要应用于数列或线性表的快速寻空(空元素)，即在连续存放的数列中，如果数列未放满，采用蛙跳的方式快速定位到第一个空元素的位置。该算法能大幅降低查找的平均查找长度，其复杂度仅为O(log n)，具有较高的效率。

关键词：蛙跳算法；数列；寻空；平均查找长度

中图分类号：TP392文献标识码：A文章编号：1009-3044(2011)10-2322-05

Leapfrogging Algorithm Used in Searching Empty in Series

SU Xiao-hu

(Dept. of Computer Science, Anhui University of Technology, Ma'anshan 243002, China)

Abstract: A new leapfrogging algorithm is proposed, and mainly used in quickly searching the empty(empty element) in series or linear list, if the continuous storing series is not filled, the way of frog-leaping is used to quickly find the position of empty element. The algorithm can significantly reduce the average search length, and its complexity is only O(log n) with high efficiency.

Key words: leapfrogging Algorithm; series; searching empty; ASL

1 概述

关于查找，在现有的书籍或论文中的介绍一般都是在给定数列(或序列)中查找特定的值(非空)，如在连续存放的数列A中，经常需要查找某个特定的关键字key，这类问题一般称为数列查找问题。数列查找问题在实际中应用广泛，例如数据库中常用到B树的数据结构，在B树的每个内部节点中都有很多元素节点，在对整个B树的查找过程中，当遍历到某个内部节点时就要判定应该进入下层节点的哪一个分支中，这时就要在此节点的数列中查找。因此数列查找效率的高低直接影响到整个B数的操作效率，进而影响到整个数据库的执行效率。而在其它很多问题中，数列查找一般是作为其中的一个子问题且被频繁调用，它的查找速度将直接影响到整个问题的执行速度。目前，关于数列查找的算法有很多，针对不同数列的特定情况可以采取不同的算法。当数列有序时，经典的算法就是二分法查找(Binary Search[1-2])(折半查找)，其复杂度为O(log n)[3-5](其中n为数列中包含的元素个数)，较之顺序查找的复杂度O(n)[3-5]来说，效率提升很多。实际上，根据判定树模型可知，二分法查找实际上已经达到了数列查找问题的下界[6]，可见其效率很高。

但在实际应用中，如数列依次插入操作中，也经常会遇到如下问题，在连续存放的数列A中要依次插入元素，如果数列未满，那么第一个空元素的位置在哪呢？如果采用顺序查找，其时间复杂度为O(n)。有没有更好的方法呢？本文根据二战中的“蛙跳(跳岛)”战术[7]思想，提出了一种新的“蛙跳”算法，该新算法经过几番改进后，发现其思想根源还是二分法。为了便于说明，本文还是首先分析二分法查找，然后给出蛙跳算法及其复杂度分析。

2 二分法查找

对包含n个元素的递增有序数列A中，二分法查找基本思想是将待查值key与数列“中间”元素比较，如果相等，则查找成功。如果不相等，若key大于中间元素，由于数列是有序的，要查找的key必然在数列中间位置的后半段范围内，则可跳过其中前一半的元素，继续对后半段使用二分法查找；否则，则key必在数列中间位置的前半段范围内，继续对前半段使用二分法查找，直到查找成功。当然也有可能数列中本来就没有与key相等的值，即直到查找失败为止。

为了讨论的方便，假设数列A[low，…，high]为一个递增的有序数组。low为数组的下界，high为数组的上界，middle= ?W（low+high）/2，则中间元素即为A[middle]。假设待查值key在A数组中，如果key>A[middle]，那么key必在A[middle+1，…，high]之中，即只需要在数组的后半段中继续查找便可；反之，如key

Int BinarySearch(A[]，int n，key)

{/*在数组A[1…n]中二分查找key*/

Int low =1,high =n,middle;

While(low

{middle = (low+high)/2;

If(A[middle]==key)

Return(middle);

Else if(A[middle] < key)

low = middle +1;

Else

high = middleC1;

}

Return(0);

}

若找到，则返回key在数组中的位置index=middle；否则返回0。如例1.。

例1：在数组A[10，11，13，15，18，19，20]中查找给定值key=18，使用二分法查找的过程如下所示。

1) 令low=1,high=7,则middle=(low+high)/2=4，如下：

2) 因key=18，A[middle]=15

3) 因key=18，A[middle]=19>key，则low=5,high=middle-1=5，middle=(5+5)/2=5，如下：

此时A[middle]=A[5]=18，与给定值key相等，查找成功，它在数组中的位置为5。

由上述分析可知，每经过一轮比较，查找的元素减半。第一轮比较后，只要从个元素中再查找；第二轮比较后，只要从个元素中再查找；那么，第k轮只需要从个元素中再查找。这样在最坏情况下，直到数组中只剩下最后一个元素，也就是要查找的元素。于是，有以下关系：

=1 (1)

公式1等价于1≤n/2k-1≤2

同乘以2k-1，亦即2k-1≤n≤2k

同取以2为底的对数，从而有 k-1 ≤log n ≤ k

因为k为整数，从而有

k=(2)

也就是说在最坏情况下的比较次数为。所以其复杂度为O(log n)。

对于二分法查找过程，也可用一颗二叉树来表示。那么，第一次比较的中间位置的元素就是二叉树的根结点，前面的所有元素按照相同的规律构成二叉树的左子树，后面的所有元素按照相同的规律构成二叉树的右子树。由此可以得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)[6]。如图1所示。

此时，判定树中深色的结点即为每次比较过的元素，每比较一次就深入一层，直到查到指定值key。那么，最大查找次数实际上也就是判定树的高度加1，也即。另根据二叉树结点遍历的方法，也可以把上述二分法算法改为递归的形式，二分法的递归算法略。

3 蛙跳算法

在可以存放n个元素的数列中，假定已经从左至右依次存放了k(k

实际操作中，就必须要找到待插入的位置k+1，也就是从左至右查找第一个为空的元素位置。为了讨论的方便，现假设数列A[1，…，n]为一个可以存放n个元素的数组(未放满)。如果以顺序查找的方法来做，从左至右逐个元素查看，当第一次遇到空的位置时就停止搜索，返回空位置序号；如果数组已满，则返回0。具体算法如下：

Int SearchNull(A[]，int n)

{//在可以存放n个元素的数组A中查找第一个为空的元素位置

Index=1;

While(index≤n)

{if(A[index]==Null)

Return(index);

Index++;

}

Return(0);

}

顺序查找第一个空元素的方法简单，但查找效率较低。假如对每个数组元素的查找概率相同，及pi=1/n，那么，在数组A中查找第i个元素成功时的比较次数为ci=n-i+1次，则对数组进行顺序查找，在查找成功时的ASL(Average Searching Length，平均查找长度)为：

(3)

也就是说，在等概率情况下，查找成功时的平均查找长度是约为数组长度(数组中包含的元素个数)的一半。若数组满时，即数组中不存在空元素时，则需要经过n+1次比较后才知道查找失败。这样的效率是很低的。

顺序查找是从左至右逐个试探，每次向有跳一个元素位置，亦即每次间隔一个元素的跳跃。蛙跳算法的基本思想就是从左至右，逐步以间隔多元素跳跃的方式向右试探元素为空的位置。具体做法是，假定每次跳跃的间隔为s=10(称之为步长，步长为大于1的正整数)，第一次跳跃，查看第10个元素是否为空，若空，那么首个空元素位置必在1-10之间，就可在1-10这10个元素中顺序查找空元素位置；若不空，进行第二次跳跃，再查看第20个元素是否为空，若空，那么首个空元素位置必在11-20之间，就可在11-20这10个元素中顺序查找空元素位置；若不空，继续第三次跳跃，……，第k次跳跃(k*10+10

Int LeapFrogging (A[]，int n)

{ //在可以存放n个元素的数组A中查找第一个“空区间”，“空区间”是指区间内所有元素全为空

Index=1;

While(index≤n)

{Index= Index +s; //s为步长

if(A[index]==Null)

//找到第一个“空区间”后，回跳到相邻的前一个区间，再顺序查找第一个空元素的位置

For(k=index-s+1;k

if(A[k]==Null)

Return(k);

}

Return(0);

}

这种蛙跳方法实际是把顺序查找空元素，改为顺序查找空区间，空区间找到后，再在找到的区间的前相邻区间内采用顺序查找或继续采用步长减半(直到步长为1为止)的递归调用蛙跳法查找，直到找到第一个空元素或空区间的位置。若采用步长减半的递归蛙跳法，那么当步长s=1时，区间内只包含一个元素了，此时查找到的空区间也就成为空元素了。蛙跳的递归算法的伪代码描述如下：

Int LeapFrogging (A[],PosStart,PosEnd,step s )

// PosStart为区间开始位置，PosEnd 区间结束位置，s为步长

{ //在可以存放n个元素的数组A中查找第一个“空区间”,“空区间”是指区间内所有元素全为空

Index=1;

While(s≥1)

{ Index= Index +s; //s为步长

if(A[index]==Null)

{ //找到第一个“空区间”后，回跳到相邻的前一个区间,再用蛙跳法查找第一个空区间位置

s=s/2;

PosStart=Index-s+1:PosEnd=Index-1;

LeapFrogging(A[],PosStart,PosEnd,step s);

}

}

Return(Index);

}

这种蛙跳方法，相当于首先给数组划分n/s(s为步长，s>1)个区间，假如对每个区间的查找概率相同，及pi=1/n/s=1/sn，那么，在数组A中查找的元素落在第i个区间成功时的比较次数为ci=n/s-i+1次，则对数组进行蛙跳式查找，在查找区间成功时的ASL即相当于把公式3中的n替换为n/s，即有：

(4)

整个蛙跳法在查找元素成功时的ASL即为查找区间的ASL再加上顺序查找区间内元素的ASL，即：

(5)

由于s为常数，故该算法的复杂度约为O(n/s)。

当n值较大，对于包含n个元素的数组的元素查找，就转化为蛙跳算法中对区间的查找，区间的长度即为步长s(s>1)，与传统的顺序查找方法相比，其ASL成s倍降低，由于效率与ASL成反比，所以其效率大致成s倍增长。当s=2时，效率提高约一倍；而当s=1时，蛙跳法就退化为顺序法。

实际上，在公式5中，当n值不变时，s的取值会影响整个蛙跳法的效率高低，s取值不合理时，不但不能提高效率，反而会降低效率，参见图2、3。图2是N=100，s=(1，…，N-1)时ASL变化曲线。s=(8，9，…，13)时ASL获得最小值11。图3是N=1000，s=(1，…，N-1)时ASL变化曲线。s=(26，27，…，39)时ASL获得最小值33。

图2 N=100时，ASL变化曲线 图3 N=1000时，ASL变化曲线

那么，对任意的n，s值取多大才合适呢？这就涉及到ASL=F(n,s)=(n+s2+2s)/2s寻优问题了。如果继续在此处研究寻优，可能使整个问题复杂化。所以换个思路来改进蛙跳算法，前面提到每找到一个空区间后，在空区间的前一个区间内，再继续递归调用蛙跳法，但蛙跳的步长每次减半；如此反复，直到步长为1为止。这样的变化实际上并不能提高效率，也不能解决寻优问题，但既然有每次减半的思路，那么是否可以参照二分法查找方法来改进跳跃方式呢？答案是肯定的。

4 改进的蛙跳算法

在第3节中描述的蛙跳方法中，其跳跃方向和跳跃的步长均是固定的。此法有两个明显的缺点：一是步长需要估计；二是效率不稳定。下面参照二分法中的减半思路来改进第3节中的蛙跳法。

现假设数列A[1，…，n]为一个可以存放n个元素的数组(未放满，参表1)。现low=1，high=n，middle=。蛙跳法寻空算法的思路就是：首先跳到中间位置查看中间元素A[middle]是否为空，若为空，那么第一个为空的元素位置必在中间元素的左半边元素中，即在A[low，…，middle-1]区间中，则下一步往左跳；若不空，那么第一个为空的元素位置必在中间元素的右半边元素中，即在A[middle+1，…，high]区间中，则下一步往左跳。无论在左或在右跳，继续使用此蛙跳法查找，直到low>=high时终止，此时middle=low或middle=high，并且要么A[low]为第一个“空”元素，要么A[high] 为第一个“空”元素。即要么A[middle]为第一个空元素，要么A[middle+1]为第一个空元素。亦即如果A[middle]的值为空，那么第一空元素的位置就是middle，否则第一空元素的位置就是middle+1。算法的伪代码描述如下：

Int LeapFrogging (A[]，int n)

{//在可以存放n个元素的数组A中查找第一个为空的元素所在的位置

If(A[1]==Null)Return(1);//

If(A[n]==Null)

Return(n);

else

Return(0);//数组已存满

Int low =1,high =n,middle;

While(low

{middle = (low+high)/2；

If(A[middle]==Null)

high = middle C 1;

Else

low = middle + 1;

}

If(A[middle]==Null)

Return(middle);

Else

Return(middle + 1);

}

如果数组未存满，则返回第一个为空的元素位置，否则返回0，表示数组已经存满。如下面两个例子。

例2：在数组A[10，11，13，15，空，空，空]中采用蛙跳法查找第一个空元素的位置的过程如下所示。

1) 令low=1，high=7，则middle=(low+high)/2=4，如下：

2)因A[middle]= A[4]=15不空，那么第一个空元素位置必在A[4]的右半部分，则令low=middle+1=5，high=7，middle=(5+7)/2=6，如下：

3) 因A[middle]=A[6]=空，那么第一个空元素位置必在A[6]的左半部分，则令low=5,high=middle-1=5，middle=(5+5)/2=5，如下：

4) 此时low=high，返回middle=5的值，此是middle值即为第一个空元素的位置。

例3：在数组A[10，11，13，空，空，空，空]中采用蛙跳法查找第一个空元素的位置的过程如下所示。

1) 令low=1，high=7，则middle=(low+high)/2=4，如下：

2) 因A[middle] = A[4] = 空，那么第一个空元素位置必在A[4]的左半部分，则令low=1，high=middle-1=4-1=3，middle=(1+3)/2=2，如下：

3) 因A[middle]=A[2]=11，不空，那么第一个空元素位置必在A[2]的右半部分，则令low=middle+1=2+1=3,high=3，middle=(3+3)/2=3，如下：

4) 此时low=high，返回middle=3的值，此时middle值加1即为第一个空元素的位置。

由上述分析可知，每经过一轮跳跃，待查找的元素减半。参照第1节中对二分法的分析可知，对于可以存放n个元素的数组，最坏情况下的总跳跃次数亦为定值，其ASL曲线变化图如图4所示。其算法复杂度也为O(log n)。

图4 改进的蛙跳算法ASL变化曲线 图5 原始蛙跳与改进蛙跳算法的ASL对比

通过对原始蛙跳与改进蛙跳算法的ASL对比，见图5，可以看出改进后蛙跳算法ASL降低明显，反之即效率提升很多，而且不必考虑步长s，也就不存在对步长s的寻优问题。

5 结束语

对于数列或线性表的插入问题中，涉及到快速定位第一个空元素位置的问题，该文提出了一个新的基于数列寻空的蛙跳算法，主要针对特定数列插入的寻空问题，该算法完全不同于文献[8]中提及的SFLA算法。并基于二分法思想对其作了改进，经改进，其复杂度已达到O(logn)，相比于一般的线性搜索方法，效率提高很多。

参考文献：

[1] Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms[M]. Cambridge,MA:MIT Press,1992.

[2] Knuth D E. The Art of Computer Programming, 3th:Sorting and Searching[M]. Addison Wesley,1973.

[3] Hopcroft A. Ullman. The Design and Analyis of Computer Algorithms[M]. Addison Wesley,1974.

[4] Kozen D C. The Design and Analysis of Algorithms[M]. Berlin:Spring-Verlag,1992.

[5] Alsuwaiyel M H.Algorithms Design Techniques and Analysis[M]. Beijing:Publishing House of Electronics Industry, 2003.

[6] Yosi Ben-Asher,Eitan Farchi,Ilan Newman. Optimal Search in Trees[J]. SIMA Journal on Computing, 1999,28(6):2090-2102.

[7] Island hopping[EB/OL]. /zh-cn/.

[8] Eusuff M M,Lansey K E. Optimization of water distribution network design using shuffled frog leaping algorithm[J]. Journal of Water Resources Planning and Management, 2003,129(3):210-225.