折半查找法
标签: 数据结构
学习人数: 4863


全屏播放
赞赏支持

折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先对该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进行排序的意思是:若查找表中存储的数据元素含有多个关键字时,使用哪种关键字做折半查找,就需要提前以该关键字对所有数据进行排序。

 

折半查找算法
对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为:


 

如上图所示,指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字,指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较,由于整个表中的数据是有序的,因...

登录查看完整内容


课后作业

课后习题

 

【2017年真题】下列二叉树中,可能成为折半查找判定树(不含外部结点)的是()

参考答案:A

 

【2015年真题】下列选项中,不能构成折半查找中关键字比较序列的是()。

A.500,200,450,180    B.500,450,200,180
C.180,500,200,450    D.180,200,500,450

参考答案:A

 

【2010年真题】已知一个长度为 16 的顺序表 L,其元素按关键字有序排列。若采用折半查 找法查找一个 L 中不存在的元素,则关键字的比较次数最多的是()。 
A.4 B.5 C.6 D.7 

参考答案:B
答案解析:考查折半查找的过程。 
具有 n 个结点的判定树的高度为log2n + 1,长度为 16,高度为 5,所以最多比较 5 次。 


登录后发布评论

暂无评论,来抢沙发