软考-软件设计师：查找算法-二分查找（折半查找） 作者：马育民 • 2025-04-10 07:24 • 阅读：10007 # 介绍 二分查找，也叫折半查找 [](https://www.malaoshi.top/upload/0/0/1GWuydQzc9C.png) ### 工作原理 1. **排序：**先对数组进行排序：升序或降序，因为折半查找依赖于数据的有序性 2. **初始化：**确定数组的起始点（通常为索引`0`）和结束点（`数组长度减1`） 3. **查找过程：** - 计算中间位置mid，公式一般为 `mid = (start + end) // 2` （使用整除以确保mid为整数）。 - 比较目标值与中间位置的值： - 如果目标值等于中间位置的值，则查找成功，返回该位置。 - 如果目标值小于中间位置的值，在数组的左半部分继续查找，即：更新结束位置为 `mid - 1` - 如果目标值大于中间位置的值，在数组的右半部分继续查找，即：更新起始位置为 `mid + 1` 4. **终止条件：**当找到目标值或者不存在目标值（起始位置超过结束位置时），查找过程结束。 ### 最多查找次数 总共有 `n` 个元素，操作如下： 1. 初始时，数组长度为 $$n$$ 2. 第1次比较后，搜索范围缩小一半，因此剩下的元素数量 $$\frac{n}{2}$$ 3. 第2次比较后，剩下的元素数量 $$\frac{n}{4}$$ 4. 第k次比较后，剩下的元素数量 $$\frac{n}{2^k}$$ 当剩下的元素数量为 `1` 时，表示找到了，所以： $$\frac{n}{2^k}=1$$ 可得 $$ k = \log_2n$$,（是以 `2` 为底，`n` 的对数） 最多查找次数：$$\log_2n$$ ### 时间复杂度 由上可知，时间复杂度：$$O(\log_2n)$$ # 技巧 有上图可知：比较的中间值会越来越趋于中间 - **上一次 往左** ，本次 **往右折返**，那上一次的最大值一定比本次的值 **大**。 - **上一次 往右** ，本次 **往左折返**，那上一次的最小值一定比本次的值 **小**。如下图的第4步是不合理的： [](https://www.malaoshi.top/upload/0/0/1GW16gRHdkaO.png) 详见下面例子 ### 例子 对某有序表进行折半查找（二分查找）时，进行比较的关键字序列不可能是（） A、42,61,90,85,77 B、42,90,85,61,77 C、90,85,61,77,42 D、90,85,77,61,42 ### 分析 **技巧：**不可能出现一次最大值，然后又出现一次更大的值；同理，不可能出现一次最小值，然后又出现一次更小的值 选项A如下图，是有可能的： [](https://www.malaoshi.top/upload/0/0/1GW16gGNYSkg.png) 选项B如下图，是有可能的： [](https://www.malaoshi.top/upload/0/0/1GWvUcfxY6o.png) 选项C如下图，**第4步 往左折返后** 出现 `42` ，比 **第3步 往右折返后** 出现 `61` 还要小，是不合理的： [](https://www.malaoshi.top/upload/0/0/1GW16gRHdkaO.png) 选项D如下图，是有可能的： [](https://www.malaoshi.top/upload/0/0/1GWvUhSCuI4.png) # 判定树和平衡二叉树 对序列进行折半查找（即二分查找）的过程可用一棵 **判定树** 表示，该判定树的形态符合 **平衡二叉树** 的特点 # 题 在线性表L中进行二分查找，要求L（） A、顺序存储，元素随机排列 B、双向链表存储，元素随机排列 C、顺序存储，元素有序排列 D、双向链表存储，元素有序排列 ### 答案 C # 题 # 题 折半查找在有序数组A中查找特定的记录K：通过比较K和数组中的中间元素A[mid]进行，如果相等，则算法结束；如果K小于A[mid]，则对数组的前半部分进行折半查找；否则对数组的后半部分进行折半查找。根据上述描述，折半查找算法采用了（）算法设计策略。对有序数组（3，14，27，39，42，55，70，85，93，98），成功查找和失败查找所需要的平均比较次数分别是（(假设查找每个元素的概率是相同的) 问题1 A.分治 B.动态规划 C.贪心 D.回溯 问题2 A.29/10和29/11 B.30/10和30/11 C.29/10和39/11 D.30/10和40/11 ### 分析 构造对应的折半查找判定树如下： [](https://www.malaoshi.top/upload/0/0/1GW16hCNWovZ.png) - 根为42，即：第5个元素，算法：`(1 + 10) / 2 = 5` - 第二层结点： - 第2个元素14，算法：`(1+4)/2 = 2` - 第8个元素85，算法：`(6+10)/2 = 8` - 第三层结点： - 第1个元素3 - 第3个元素27，算法：`(3+4)/2 = 3` - 第6个元素55，算法：`(6+7)/2 = 6` - 第9个元素93，算法：`(9+10)/2 = 9` - 第四层结点： - 39 - 70 - 98 ##### 成功查找次数 - 41：在第一层，所以比较1次就能找到 - 14、85：在第二层，所以比较2次能找到 - 3、27、55、98：在第三层，所以比较3次能找到 - 39、70、98：在第四层，所以比较4次能找到 总共查找次数：`1+2*2+3*4+4*3 = 29` 平均查找次数：`29次/10个` ##### 失败查找次数 折半查找失败的过程，可以理解为对处于这10个元素之前的间隔位置的数进行了查找，对各个元素间隔进行编号依次为1、2、3、.….、11，此时： - 1号间隔位于3的左侧（要查找的数字比3还小），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3; - 2号位置位于3和14之间（要查找的数字在3-14之间），此时需要分别与元素42、14、3比较后才会查找失败，比较次数为3; - 3号位置位于14和27之间，此时需要分别与元素42、14、27比较后才会查找失败，比较次数为3； - 4号位置位于27和39之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4; - 5号位置位于39和42之间，此时需要分别与元素42、14、27、39比较后才会查找失败，比较次数为4; - 6号位置位于42和55之间，此时需要分别与元素42、85、55比较后才会查找失败，比较次数为3； - 7号位置位于55和77之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4; - 8号位置位于77和85之间，此时需要分别与元素42、85、55、77比较后才会查找失败，比较次数为4; - 9号位置位于85和93之间，此时需要分别与元素42、85、93比较后才会查找失败，比较次数为3； - 10号位置位于93和98之间，此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4; - 11号位置位于98右侧（要查找的数字比98还大），此时需要分别与元素42、85、93、98比较后才会查找失败，比较次数为4; 此时平均查找次数为 `（3*5+4*6）/11=39/11` 因此第二问选择C选项。 原文出处：http://malaoshi.top/show_1GWvY9LAMNU.html