折半查找-软考在线

折半查找


知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 查找 >
被考次数：2次被考频率：低频率总体答错率：39% 知识难度系数：	由软考在线用户真实做题大数据统计生成
相关知识点：12个

折半查找也称为二分查找，其基本思想是：先令查找表中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时（表明查找不成功）为止。

设查找表的元素存储在一维数组r［1..n］中，那么在表中的元素已经按关键字递增（或递减）排序的情况下，进行折半查找的方法是：首先比较key值与表r中间位置（下标为mid）的记录的关键字，若相等，则查找成功。若key>r［mid］.key，则说明待查记录只可能在后半个子表r［mid+1..n］中，下一步应在后半个子表中再进行折半查找；若keyr的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。

【函数】设有一个整型数组中的元素是按非递减的方式排列的，在其中进行折半查找的算法如下：

折半查找的过程可以用一棵二叉树描述，方法是：以当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树上的结点，这样构造的二叉树称为折半查找判定树。例如，具有11个结点的折半查找判定树如下图所示，结点中的数字表示元素的序号。

具有11个结点的折半查找判定树

从折半查找判定树可以看出，查找成功时，折半查找的过程恰好走了一条从根结点到被查结点的路径，关键字进行比较的次数即为被查找结点在树中的层数。因此，折半查找在查找成功时进行比较的关键字数最多不超过树的高度，而具有n个结点的判定树的高度为

，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为

。

给判定树中所有结点的空指针域加上一个指向一个方型结点的指针，称这些方型结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），如下图所示。那么折半查找不成功的过程就是走了一条从根结点到外部结点的路径。和给定值进行比较的关键字个数等于该路径上内部结点个数。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过

。

加上外部结点的判定树

那么折半查找的平均查找长度是多少呢？为了方便起见，不妨设结点总数为n=2^h-1，则判定树是深度为h=log₂（n+1）的满二叉树。在等概率情况下，折半查找的平均查找长度为：

当n值较大时，ASL_bs≈log₂（n+1）-1。

折半查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列。因此，折半查找适用于表不易变动，且又经常进行查找的情况。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2022年上半年
   数据库系统工程..
   上午试卷综合知识

第9题
选择题

折半查找要求查找表中的数据为（）。

26%

   2020年下半年
   数据库系统工程..
   上午试卷综合知识

第10题
选择题

查找算法中，（）要求查找表进行顺序存储并且按照关键字有序排列，一般不进行表的插入与删除操作。

52%


	相关知识点：
	索引顺序查找顺序查找哈希查找处理冲突 B_树哈希造表二叉查找树中插入结点的操作查找树表查找查找表及查找效率二叉查找树的查找过程哈希查找

	软考在线指南
	优惠劵及余额
	在线支付
	修改密码
	下载及使用
	购买流程
	取消订单

	联系我们
	关于我们
	联系我们
	商务合作

旗下网站群

高级资格科目
信息系统项目管理师	系统分析师
系统架构设计师	网络规划设计师
系统规划与管理师
初级资格科目
程序员	网络管理员
信息处理技术员	信息系统运行管理员

中级资格科目
系统集成项目管理工程师	网络工程师
软件设计师	信息系统监理师
信息系统管理工程师	数据库系统工程师
多媒体应用设计师	软件评测师
嵌入式系统设计师	电子商务设计师
信息安全工程师

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

商务合作

客服邮箱service@rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5 |