第8章 查找

在数据处理过程中，是否能在最短时间内查找到所需要的数据，是一个相当值得信息从业人员关心的问题。所谓查找(search，或搜索)指的是从数据文件中找出满足某些条件的记录。用以查找的条件称为“键值”(key)，就如同排序所用的键值一样。

例如联系人中找某人的电话号码，那么这个人的姓名就成为在联系人中查找电话号码的键值。通常影响查找时间长短的主要因素包括算法的选择、数据存储的方式和结构。

8-1 常见的查找方法

如果根据数据量的大小，可将查找分为：

1. 内部查找：数据量较小的文件，可以一次性全部加载到内存中进行查找。

2. 外部查找：数据量大的文件，无法一次加载到内存中处理，而需使用辅助存储器来分次处理。

如果从另一个角度来看，查找的技巧又可分为“静态查找”和“动态查找”两种。定义如下所示。

1. 静态查找：指的是在查找过程中，查找的表格或文件的内容不会被改动。例如符号表的查找就是一种静态查找。

2. 动态查找：指的是在查找过程中，查找的表格或文件的内容可能会被改动，例如在树状结构中所谈的B-tree查找就属于一种动态查找。

至于查找技巧中比较常见的方法有顺序法、二分查找法、斐波那契法、插值法、哈希法、m路查找树、B-tree等。为了让大家能确实掌握各种查找的技巧和基本原理，以便应用于日后的各种领域，现将几个主要的查找方法分述于后。

8-1-1 顺序查找法

顺序查找通常用于未经组织化的文件，又称为线性查找。查找的过程从文件及时项数据开始，按序比较每个键值。由于顺序查找法是逐项对比，因此只要一找到数据就可以结束数据的查找。以n项数据为例，使用顺序查找法来查找数据时，有可能在第1项就找到了，在这种情形下仅需执行一次比较操作。如果数据在第2项、第3项…第n项，则其需要的比较次数分别为2、3、4、…、n次。因此，在平均情况下，顺序查找法，查找一项数据需要的平均比较次数为 (n 1)/2。

现在以一个例子来说明，假设已有数列74、53、61、28、99、46、88，若要查找28，则需要比较4次；要查找74仅需比较1次；要查找88则需查找7次，这表示当查找的数列长度n很大时，利用顺序查找是不太适合的，它是一种适用于小数据文件的查找方法。

另外，在最差的情况下，逐一对比后没有找到数据，则必须花费n次，其最坏情况下(Worst Case)的时间复杂度为O(n)。也就是说，除非可以预知要查找的数据大概位于文件的前端，否则当文件的数据项数过大时，顺序查找法在查找的效率上显然不如其他的查找法。

线性查找法的优点是文件或数据事前不需要经过任何的处理与排序，也由于它未考虑到数据的特征对于查找的影响，所以在应用上适合于各种情况，其缺点则是查找的速度较慢。

顺序查找法的C语言算法如下所示。

while (val!=-1

{

find=0;

printf("请输入查找键值(1-150)，输入-1离开：");

scanf("%d",&val);

for (i=0;i

{

if(data[i]==val

{

printf("在第 %3d个位置找到键值 [%3d]\n",i 1,data[i]);

find ;

}

}

if(find==0 && val !=-1

printf("######没有找到 [%3d]######\n",val);

}

8.1.1

请设计一个C程序，以随机数生成1~150之间的80个整数，然后实现顺序查找法的过程。

请参考程序CH08_01.c，本范例程序的运行结果如图8-1所示。

图8-1 实现顺序查找法的范例程序的运行结果

8-1-2 二分查找法

如果要查找的数据已经事先排好序了，则可使用二分查找法来进行查找。二分查找法是将数据平均分割成两份，再比较键值与中间值的大小，如果键值小于中间值，可确定要查找的数据在前半段，否则在后半部。如此分割数次直到找到或确定不存在为止。例如，以下已排序的数列 2、3、5、8、9、11、12、16、18 ，而所要查找值为11时：

首先跟第5个数值 9 比较，如图8-2所示。

图8-2 先和中值比较

因为11>9，所以和后半部的中间值 12 比较，如图8-3所示：

图8-3 再和后半部的中值比较

因为 11<12，所以和前半部的中间值 11比较，如图8-4所示：

图8-4 再和后半部的前半部中值比较

因为 11=11，表示查找到了即查找完成，如果不相等则表示没有找到。

二分查找法的C语言算法如下所示。

int bin_search(int data[50],int val

{

int low,mid,high;

low=0;

high=49;

printf("查找过程中......\n");

while(low

{

mid=(low high)/2;

if(val

{

printf("%d 介于位置 %d[%3d]和中间值 %d[%3d]，找左半边\n",val,low 1, data[low],mid 1,data[mid]);

high=mid-1;

}

else if(val>data[mid]

{

printf("%d 介于中间值位置 %d[%3d] 和 %d[%3d]，找右半边\n",val,mid 1, data[mid],high 1,data[high]);

low=mid 1;

}

else

return mid;

}

return -1;

}

使用二分法查找要求被查找的数列事先已排好序，而且数据量不能太大，必须要能直接在内存中执行。此法适合用于不需增删的静态数据，因为每次的查找都会比上一次少一半的范围，所以最多只需要比较log2n 1或log2(n 1) 次，时间复杂度为O(log n)。

8.1.2

请设计一个C程序，以随机数生成1~150之间的80个整数，然后实现二分查找法的过程与步骤。

请参考程序CH08_02.c，本范例程序的运行结果如图8-5所示。

图8-5 实现二分查找法的范例程序的运行结果

8-1-3 插值查找法

插值查找法(interpolation search)又叫作插补查找法，是二分查找法的改进版。它是按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用插值法是假设数据平均分布在数组中，而每一项数据的差距相当接近或有一定的距离比例。插值法的公式为：

Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low

其中key是要查找的键，data[high]、data[low]是剩余待查找记录中的较大值和最小值，假设数据项数为n，其插值查找法的步骤如下所示。

? 将记录从小到大的顺序给予1、2、3、…、n的编号。

? 令low=1，high=n

? 当low

? 令Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low

? 若key

? 若key=keyMid表示成功查找到键值的位置

? 若key>keyMid且low≠Mid 1，则令low=Mid 1

二分查找法的C语言算法如下所示。

int bin_search(int data[50],int val

{

int low,mid,high;

low=0;

high=49;

printf("查找过程中......\n");

while(low

{

mid=low ((val-data[low])(high-low)/(data[high]-data[low]));

/内插法公式/

if (val==data[mid]

return mid;

else if (val < data[mid]

{

printf("%d 介于位置 %d[%3d]和中间值 %d[%3d]，找左半边

\n",val,low 1,data[low],mid 1,data[mid]);

high=mid-1;

}

else if(val > data[mid]

{

printf("%d 介于中间值位置 %d[%3d] 和 %d[%3d]，找右半边

\n",val,mid 1,data[mid],high 1,data[high]);

low=mid 1;

}

}

return -1;

}

一般而言，使用插值查找法要求数据需先经过排序，这样查找速度才能优于顺序查找法，而如果数据的分布越平均，则查找速度越快，甚至可能及时次就找到数据。此法的时间复杂度取决于数据分布的情况，平均而言优于O(log n)。

8.1.3

请设计一个C程序，以随机数生成1~150之间的50个整数，然后实现插值查找法的过程与步骤。

请参考程序CH08_03.c，本范例程序的运行结果如图8-6所示。

图8-6 实现插值查找法的范例程序的运行结果

8-1-4 斐波那契查找法

斐波那契查找法(fibonacci search)又称为Fibonacci查找法，此法和二分法一样都是以分割范围来进行查找，不同的是斐波那契查找法不以对半分割而是以斐波那契级数的方式来分割。

斐波那契级数F(n)的定义如下所示。

斐波那契级数：0、1、1、2、3、5、8、13、21、34、55、89、……。也就是除了第0个和第1个元素外，级数中的每个值都是前两个值的和。

斐波那契查找法的好处是只用到加减运算而不需用到乘除运算，这从计算机运算的过程来看效率会高于前两种查找法。在尚未介绍斐波那契查找法之前，我们先来认识斐波那契查找树。所谓斐波那契查找树是以斐波那契级数的特性来建立的二叉树，其建立的原则如下所示。

(1)斐波那契树的左右子树均为斐波那契树。

(2)当数据个数n确定，若想确定斐波那契树的层数k值是多少，必须找到一个最小的k值，使得斐波那契层数的Fib(k 1)≥n 1。

(3)斐波那契树的树根一定是一个斐波那契数，且子节点与父节点差值的值为斐波那契数。

(4)当k≥2时，斐波那契树的树根为Fib(k)，左子树为 (k-1) 层斐波那契树(其树根为Fib(k-1))，右子树为 (k-2) 层斐波那契树(其树根为Fib(k) Fib(k-2))。

(5)若n 1值不为斐波那契数的值，则可以找出存在一个m使用Fib(k 1)-m=n 1，m=Fib(k 1)-(n 1)，再按斐波那契树的建立原则完成斐波那契树的建立，斐波那契树的各节点再减去差值m即可，并把小于1的节点去掉。

斐波那契树建立过程的示意图如图8-7所示。

图8-7 斐波那契树建立过程的示意图

也就是说当数据个数为n，且找到一个最小的斐波那契数Fib(k 1)使得Fib(k 1)>n 1，则Fib(k) 就是这棵斐波那契树的树根，而Fib(k-2) 则是与左右子树开始的差值，左子树用减的；右子树用加的。例如实际求取n=33的斐波那契树。

由于n=33，且n 1=34为一个斐波那契树，并知道斐波那契数列的3项特性。

Fib(0) = 0

Fib(1) = 1

Fib(k) = Fib(k-1) Fib(k-2

得知 Fib(0) = 0、Fib(1) = 1、Fib(2) = 1、Fib(3) = 2、Fib(4) = 3、Fib(5) = 5、Fib(6) = 8、Fib(7) = 13、Fib(8) = 21、Fib(9) = 34

从上式可得知Fib(k 1) = 34 à k = 8，建立二叉树的树根为Fib(8) = 21

左子树的树根为Fib(8-1) = Fib(7) = 13

右子树的树根为Fib(8) Fib(8-2) = 21 8 = 29

按此原则可以建立如图8-8所示的斐波那契树。

图8-8 斐波那契树

斐波那契查找法是以斐波那契树来查找数据，如果数据的个数为n，而且n比某一个斐波那契数小，且满足如下表达式。

Fib(k 1)≥n 1

此时Fib(k) 就是这棵斐波那契树的树根，而Fib(k-2) 则是与左右子树开始的差值，若要查找的键值为key，首先比较数组下标Fib(k) 和键值key，此时可以有下列3种比较情况。

? 当key值比较小，表示所查找的键值key落在1到Fib(k)-1之间，故继续查找1到Fib(k)-1之间的数据。

? 如果键值与数组下标Fib(k) 的值相等，表示成功查找到所要的数据。

? 当key值比较大，表示所找的键值key落在Fib(k) 1到Fib(k 1)-1之间，故继续查找Fib(k) 1到Fib(k 1)-1之间的数据。

斐波那契查找法的C语言算法如下所示。

#define MAX 20

int fib(int n

{

if(n==1 || n==0

return n;

else

return fib(n-1) fib(n-2);

}

int fib_search(int data[MAX],int SearchKey

{

int index=2;

/斐波拉契数列的查找/

while(fib(index

index ;

index--;

/ index >=2 /

/起始的斐波拉契数/

int RootNode=fib(index);

/上一个斐波拉契数/

int diff1=fib(index-1);

/上两个斐波拉契数即diff2=fib(index-2)/

int diff2=RootNode-diff1;

RootNode--;/这个表达式是配合数组的下标是从0开始存储数据/

while(1

{

if(SearchKey==data[RootNode]

{

return RootNode;

}

else

{

if(index==2) return MAX; /没有找到/

if(SearchKey

{

RootNode=RootNode-diff2;/左子树的新斐波拉契数 /

int temp=diff1;

diff1=diff2;/上一个斐波拉契数/

diff2=temp-diff2;/上两个斐波拉契数/

index=index-1;

}

else

{

if(index==3) return MAX;

RootNode=RootNode diff2;/右子树的新斐波拉契数 /

diff1=diff1-diff2;/上一个斐波拉契数/

diff2=diff2-diff1;/上两个斐波拉契数/

index=index-2;

&nb