汉扬编程 C语言入门 C语言:数据结构-线性表的查找-折半查找

C语言:数据结构-线性表的查找-折半查找

折半查找 (1)折半查找的存储结构

C语言:数据结构-线性表的查找-折半查找

查找表(顺序表)中记录所相应的关键字必须有序。

C语言:数据结构-线性表的查找-折半查找

(2)折半查找的基本思想

C语言:数据结构-线性表的查找-折半查找

从有序表的中间位置元素开始查找,若没有查到,可以排除掉大约一半的元素,缩小查找范围,反复上述过程。

结构数组a中存放查找表的元素,查找范围[0、n-1],Low下界,high上界,mid中间位置,查找值 k。

1.low= 0,high =n-1

2.mid=(Low+high)/2

3.若 k==a [mid].key,返回mid

k< a [mid].key,high = mid-1 (取前半区间)

k> a [mid].key,low = mid+1 (取后半区间)

重复①~③,直到Low>high,说明整个表已查找完毕,此时若表中仍查不到关键字为K的记录,则查找失败。

例8-1:设顺序表中有8个记录,它们的关键字依次为{8,11,18,28,45,55,63,80},用折半查找的方法在该顺序表中查找关键字为55和20的记录。查找关键字为55的记录的过程见图8-1:

初始状态时low=0,high=7,mid=⌊(0+7)/2⌋=3,low指向a[0].key=8,mid指向a[3].key=28,high指向a[7].key=80,见图8-1(a)。k=55,将k与a[mid].key相比较,k>a[mid].key,表明若待查记录存在,则必定在区间[mid+1,high]中,所以,此时令low=mid+1,有low=4,high=7,从而求得新的mid=⌊(4+7)/2⌋=5,见图8-1(b)。k继续与a[mid].key进行比较,由于k= =a[mid].key,查找成功,返回记录的下标为5。

折半查找过程示意图

若查找关键字为20的记录,则其查找过程见图8-2。初始状态时low=0,high=7,mid=⌊(0+7)/2⌋=3,low指向a[0].key=8,mid指向a[3].key=28,high指向a[7].key=80,见图8-2 (a)。因为k<a[mid].key,所以令high=mid-1,mid=⌊(0+2)/2⌋=1,见图8-2(b),继续比较,又因为k>a[mid].key,所以令low=mid+1,mid=⌊(2+2)/2⌋=2,见图8-2(c)。

折半查找过程示例

k>a[mid].key,所以令low=mid+1,low=3,low>high,说明整个表已经查询完毕,没有找到关键字等于k的记录,查找失败。

折半查找算法 int Binary_Search(NODE a[],int n, int k) /* 在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1 */ { int low,mid,high; low=0; high=n-1; while(low<=high) { mid=(low+high)/2; if(a[mid].key==k) return mid; /*查找成功,返回查找到的记录的下标*/ else if(a[mid].key<k) low=mid+1; /*取后半查找区间*/ else high=mid-1; /*取前半查找区间*/ } return -1; /*查找失败*/ } (4)折半查找对应的判定树

折半查找的过程可以用一棵二叉树来描述,树中的每个结点相应于查找表中的一个记录,结点的值为相应记录在查找表中的位置值。根结点的值是查找表的中间元素的下标,左子树的结点是关键字小于中间元素的左子表,左子树的根结点是左子表的中间元素的下标;右子树的结点是关键字大于中间元素的右子表,右子树的根结点是右子表的中间元素的下标,依次类推得到相应的判定树。

设查找表为(6,14,20,21,38,56,68,78,85,85,100),元素的下标位置依次为0,1,2,…,10,相应的判定树如图8-3所示,从表中看出查找21要经过3次比较,查找100要经过4次比较。在等概率条件下,可求得成功查找的平均查找长度为:

ASL=(1+2*2+3*4+4*4)/11=3

折半查找对应的判定树

当查找成功时,最好情况下的比较次数为1次。而查到每个记录的比较次数等于该结点在判定树中的深度。折半查找算法的时间复杂度为O(log 2 n)。很显然,折半查找的效率要比顺序查找高的多。但是,该方法只适用于顺序存储结构的有序表,没有顺序查找使用的范围广。

折半查找算法不适合链表结构的序列。虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列的,但因其存储结构为单链表,查找结点时只能从头指针开始顺序查找,不能进行随机查找,所以不适合采用折半查找。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6064.html

步进电机和伺服电机的优缺点?

干货!C语言高级编程教学:学不会?我们送学习源码!

发表评论

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

返回顶部