《顺序查找与折半查找小总结》 一、 顺序查找 1、 基本思想:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。 若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。
2、 存储结构要求:既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表 作存储结构时,扫描必须从第一个结点开始)
3、 基于顺序结构的顺序查找算法
(1)//类型说明
typedef struct{ KeyType key; InfoType otherinfo; //此类型依赖于应用 }NodeType; typedef NodeType SeqList[n+1]; //0号单元用作哨兵
(2) //具体算法 int SeqSearch(Seqlist R,KeyType K) { //在顺序表R[1..n]中顺序查找关键字为K的结点, //成功时返回找到的结点位置,失败时返回0 int i; R[0].key=K; //设置哨兵 for(i=n;R.key!=K;i--); //从表后往前找 return i; //若i为0,表示查找失败,否则R是要找的结点 } //SeqSearch
4、 优点:算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点, 也无论结点之间是否按关键字有序,它都同样适用。
5、 缺点:查找效率低,因此,当n较大时不宜采用顺序查找。
二、 折半查找
折半查找,又称二分查找,是种效率较高的查找算法。
1、要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
2、基本思想:
(1)首先确定该区间的中点位置:mid = (low + high) / 2
(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,
继续二分查找,具体方法如下:
①若R[mid].key>K,则由表的有序性可知R[mid..n].keys 均大于K,因此若表中存在关键字等于K的结点,
则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
②类似地,若R[mid].key<k,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。
下一次查找是针对新的查找区间进行的。</k
因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,
就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点
3、算法:
int BinSearch(SeqList R,KeyType K) { //在有序表R[1..n]中进行二分查找,成功时返回结点的位置,失败时返回零 int low=1,high=n,mid; //置当前查找区间上、下界的初值 while(low<=high){ //当前查找区间R[low..high]非空 mid=(low+high)/2; if(R[mid].key==K) return mid; //查找成功返回 if(R[mid].key>K) high=mid-1; //继续在R[low..mid-1]中查找 else low=mid+1; //继续在R[mid+1..high]中查找 } return 0; //当low>high时表示查找区间为空,查找失败 } //BinSeareh
|