软考-软件设计师：查找算法-二分查找（折半查找） 作者：马育民 • 2025-04-10 07:24 • 阅读：10005 # 介绍 二分查找，也叫折半查找 [](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)$$ # 技巧 有上图可知：比较的中间值会越来越趋于中间 一旦出现“折返”，不可能出现一次最大值，然后又出现一次更大的值；同理，不可能出现一次最小值，然后又出现一次更小的值 详见下面例子 ### 例子 对某有序表进行折半查找（二分查找）时，进行比较的关键字序列不可能是（） 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/1GWvUbaIUvj.png) 选项B如下图，是有可能的： [](https://www.malaoshi.top/upload/0/0/1GWvUcfxY6o.png) 选项C如下图，出现一次最小值，又出现一次更小的值，是没有可能的： [](https://www.malaoshi.top/upload/0/0/1GWvUg4d1fy.png) 选项D如下图，是有可能的： [](https://www.malaoshi.top/upload/0/0/1GWvUhSCuI4.png) # 题 在线性表L中进行二分查找，要求L（） A、顺序存储，元素随机排列 B、双向链表存储，元素随机排列 C、顺序存储，元素有序排列 D、双向链表存储，元素有序排列 ### 答案 C 原文出处：http://malaoshi.top/show_1GWvY9LAMNU.html