折半查找
如果从文件中读取的数据记录的关键字是有序排列的(递增的或是递减的),则可以用一种更有效率的查找方法来查找文件中的记录,这就是折半查找法,又称为二分搜索。
折半查找的基本思想:减少查找序列的长度,分而治之地进行关键字的查找。他的查找过程是:先确定待查找记录的所在的范围,然后逐渐缩小查找的范围,直至找到该记录为止(也可能查找失败)。例如文件记录的关键字序列为:
(1,3,5,7,9,11,13,17,21,28,32)
该序列包含11个元素,而且关键字单调递增。现在想查找关键字key为28的记录。如果应用顺序查找法进行查找,需要将28之前的所有关键字与key进行比较,共需10次,如果用折半查找可以这样做:
设指针low和high分别指向关键字序列的上界和下界,即low=0,high=10。指针mid指向序列的中间位置,即mid=[low+high)/2]=5。在这里low指向关键字1,high指向关键字32,mid指向关键字11。
(1,3,5,7,9,11,13,17,21,28,32)
↑ ↑ ↑
low mid high
1)首先将mid所指向的元素与key进行比较,因为key=28,大于11,这就是说明待查找的关键字一定位于mid和high之间。这是因为原关键字序列是有序递增的。因此下面的查找工作只需在[mid+1,high]中进行。于是指针low指向mid+1的位置,即low=6,也就是指向关键字13,并将mid调整到指向关键字21,即mid=8。
(1,3,5,7,9,11,13,17,21,28,32)
↑ ↑ ↑
low mid high
2)再将mid所指向的元素与key进行比较,因为key=28,大于21,说明待查找的关键字一定位于mid和high之间。所以下面的查找工作仍然只需在[mid+1,high]中进行。于是指针low指向mid+1的位置,即low=9,也就是指向关键字28,并将mid调整到指向关键字28,即mid=9。high保持不变。
(1,3,5,7,9,11,13,17,21,28,32)
↑ ↑
mid high
low
3)接下来仍然将mid所指元素与key进行比较,比较相等,查找成功,返回mid的值9。
假设要查找的关键字key为29,那么上述的查找还要继继续下去。由于当前mid所指的元素是28,小于29,因此下面的查找工作仍然只需在[mid+1,high]中进行。将指针iow指向mid+1的位置,并调整指针mid的位置。这时指针mid,low与high三者重合,都指向关键字32,它们的值都为10。
(1,3,5,7,9,11,13,17,21,28,32)
↑
high
mid
low
再将mid所指的元素与key进行比较,因为key=29,小于32,说明待查找的关键字一定位于low和mid之间。所以下面的查找工作仍然只需在[low,mid-1]中进行。于是令指针high指向mid-1的位置,即high=9,也就是指向关键字28.这是指针high小于指针low,这表明本次查找失败。
折半查找的算法如下:
int searchkeytype key[],int n,keytype k){ int low=0,high=n-1,mid; whilelow<=high) { mid=low+high)/2; ifkey[mid]==k) return mid;//查找成功,返回mid ifk>key[mid]) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } return -1;//查找失败,返回-1 }
在算法中,n表示记录的个数。key表示要查找的关键字。key[]为关键字顺序表,每个元素都是对应记录的关键字。例如key[0]为第0个记录的关键字。如果每条记录的信息与它的关键字都存放在一个记录里,如下定义:
typedef struct{ keytype key;//keytype类型的关键字key datatype data; //记录中的其他信息 }RecordType;
每个记录中包含一个关键字key和一个数据域data。这种记录的折半查找法可描述为:
int searchRecordType r[],int n,keytype k){ int low=0,high=n-1,mid; whilelow<=high) { mid=low+high)/2;//设置mid指针的值 ifr[mid].key==k) return mid;//查找成功,返回mid ifk>r[mid].key) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } return -1;//查找失败,返回-1 }
这里要注意,以上算法只适用于关键字顺序递增的有序表查找。如果该顺序表是关键字递减的,则算法需要改动,在low指针与high指针的修改上对调即可。
折半查找法的优点:折半查找法的效率比顺序查找法的效率要高很多。如果一个顺序表中有1000个关键字,应用顺序查找法查找指定的关键字,平均要比较500次。而应用折半查找法,平均只用比较9次。因此对于顺序文件记录的查找,应当使用折半查找法。
折半查找法的缺点:只能应用于关键字有序的顺序表的查找,且一般不适用于对链表中记录的查找。
折半查找法的优化:在使用折半查找前,将关键字key与上下界low与High先进行比较,若与其中一个相匹配可直接跳出,无需继续折半。
【实例】
有一个数组A[10],里面存放了10个整数,顺序递增。任意输入一个数字n,找到n在数组中的位置。如果n不属于该数组A,显示错误提示。
A[10]={2,3,5,7,9,11,12,15,19,22}
【分析】
#include<stdio.h>int searchint A[],int n,int key){ int low=0,high=n-1,mid; ifA[low]==key) return low; else ifA[high]==key) return high; else { whilelow<=high) { mid=low+high)/2; ifA[mid]==key) return mid;//查找成功,返回mid ifkey>A[mid]) low=mid+1;//在后半序列中查找 else high=mid-1;//在前半序列中查找 } } return -1;//查找失败,返回-1 }main){ int A[10]={2,3,5,7,9,11,12,15,19,22},i,n,addr; printf”A[10]:”); fori=0;i<10;i++) printf”%d “,A[i]);//显示数组A的内容 printf”\n输入要查找元素:”); scanf”%d”,&n);//输入待查找元素 addr=searchA,10,n);//折半查找返回该元素在数组中的下标 ifaddr!=-1)//查找成功 printf”%d是数组中的第%d个元素”,n,addr+1); else//查找失败 printf”A数组中无%d”,n); return 0;}
运行结果如图所示:
注意:数组的下标从0开始,故要在原返回值上+1,才为元素的位置。