扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找是软考中级软件设计师考试中数据结构部分的核心考点，也是历年上午题几乎从不缺席的一类送分题。但恰恰是这种看似简单的算法，命题人每年都能用几个细节陷阱让大量考生丢分。本文从折半查找的概念定义讲起，深挖判定树与平均查找长度的底层原理，逐一拆解mid计算、取整方向、循环条件与边界更新四大陷阱，并结合历年真题还原命题人的出题思路，帮助考生把这部分分数稳稳拿到手。
折半查找又称二分查找，是一种在有序顺序表中查找特定元素的经典算法。其标准定义可以表述为：对于按关键字有序排列的线性表，每次将待查区间从中间位置一分为二，用中间位置的元素与目标值比较，根据比较结果将查找区间缩小为原区间的一半，如此反复，直至找到目标元素或确定目标元素不存在。折半查找属于典型的基于比较的查找算法，与顺序查找、分块查找、哈希查找并列为数据结构课程中最基础的几类查找方法。
折半查找在教材中的正式表述通常强调两个要点：其一是查找对象必须有序，其二是查找对象必须支持随机访问。这两条前提缺一不可，是折半查找区别于其他查找算法的根本标志，也是软考选择题中最常考的一个判断点。
折半查找能够成立，依赖两个严格的先决条件。第一，表中的数据元素必须按关键字有序排列，无论是升序还是降序均可，但必须存在一个明确的、全局一致的大小关系。第二，存储结构必须是顺序存储结构，也就是数组，因为折半查找的核心操作是"取中间位置元素"，这要求能够在常数时间内通过下标直接定位任意元素，而链表虽然也能通过遍历走到中间位置，但那已经退化为线性时间，失去了折半查找的意义。
这两条前提直接决定了折半查找的适用边界。如果一个查找集合本身无序，那么必须先对其进行排序，而排序本身的时间复杂度通常不低于 O(n log n)，如果只是偶尔做一次查找，排序的代价可能远超直接顺序查找，此时折半查找并不划算。软考命题人经常围绕"折半查找是否要求有序""链表能否进行折半查找"这类问题设题，考查的正是对这两条前提的理解深度。
顺序查找是最朴素的查找方式，它从表头开始逐个扫描，最坏情况下需要比较 n 次，平均情况下需要比较约 n/2 次，时间复杂度为 O(n)。折半查找则利用有序这一结构性信息，每次将搜索范围减半，最坏情况下只需要约 log2(n+1) 次比较，时间复杂度为 O(log n)。两者之间不是简单的快慢差别，而是"能否利用数据的结构性信息"这一思想层面的分野。
这一分野在软考中有一个经典命题角度：给定一个包含 n 个元素的有序表，问顺序查找与折半查找的比较次数、平均查找长度分别如何计算。考生需要清楚，顺序查找的平均查找长度 ASL 约为 (n+1)/2，而折半查找的平均查找长度近似为 log2(n+1) 减一，两者在 n 较大时呈现出数量级上的鸿沟，这正是折半查找价值所在。
折半查找的执行过程可以用一个具体的例子完整还原。假设有一个升序排列的数组，元素依次为 3、5、8、12、17、22、30、36、41、55，共十个元素，下标从 1 到 10，现在要查找目标值 22。首先确定查找区间的下界 low 为 1，上界 high 为 10，计算中间位置 mid 为 low 与 high 之和除以二向下取整，即 (1+10) 除以二向下取整得到 5，此时中间位置的元素是 17。目标值 22 大于 17，说明目标如果存在，一定在中间位置的右侧，于是将下界 low 更新为 mid 加一，即 6，上界不变，查找区间缩小为下标 6 到 10 这一半。
第二轮，重新计算中间位置，(6+10) 除以二向下取整得到 8，中间位置元素是 36。目标值 22 小于 36，说明目标在中间位置左侧，于是将上界 high 更新为 mid 减一，即 7，下界不变，区间缩小为 6 到 7。第三轮，(6+7) 除以二向下取整得到 6，中间位置元素是 22，恰好等于目标值，查找成功，整个过程只用了三次比较。
从这个过程可以提炼出折半查找的三个关键动作：计算中间位置、比较、缩小一半区间。三者循环往复，每一轮都能将搜索空间稳定地压缩一半，这是其对数级效率的根本来源。值得强调的是，折半查找每一次比较所带来的信息量远大于顺序查找：顺序查找一次比较只能排除一个元素，而折半查找一次比较能直接排除掉半个区间。随着 n 的增大，这种"每次排除一半"的优势会被指数级放大，因此元素越多，折半查找相对顺序查找的优越性就越明显，这也是它成为有序表查找首选算法的原因。
折半查找的过程可以用一棵二叉判定树来精确描述，这也是软考中最能体现理解深度的一类题目。判定树是一棵特殊的二叉树，树中每个非空结点对应一次比较操作，结点的值就是该次比较所取的中间位置元素。对于前面那个含十个元素的有序表，第一轮比较的是下标 5 的元素 17，因此 17 成为判定树的根结点。若目标值大于 17，进入右子树，对应区间下标 6 到 10；若小于 17，进入左子树，对应区间下标 1 到 4。
对下标 1 到 4 的区间，中间位置为 (1+4) 向下取整得到 2，元素 8 成为根结点左子树的根；对下标 6 到 10 的区间，中间位置为 (6+10) 向下取整得到 8，元素 36 成为右子树的根。如此递归下去，最终得到一棵高度约为 log2(n+1) 的判定树。这棵树的叶子结点对应查找失败的情形，内部结点对应查找成功的情形。
判定树的重要意义在于，它把折半查找的动态过程转化成了一棵静态的树结构，从而可以用树的高度、结点的层数来精确计算查找的比较次数。某元素在判定树中位于第几层，查找它就需要几次比较。这为计算平均查找长度提供了严格的数学工具。
折半查找的时间复杂度推导建立在区间减半这一事实上。假设初始区间长度为 n，经过第一轮比较后区间长度不超过 n 除以二，经过第二轮后不超过 n 除以四，一般地，经过 k 轮比较后，区间长度不超过 n 除以二的 k 次方。查找过程在区间长度为 1 时结束，因此需要满足 n 除以二的 k 次方约等于 1，解出 k 约等于 log2(n)，这就得到了折半查找最坏情况下比较次数为 O(log n) 的结论。
这里有一个软考常考的细节：折半查找最坏情况下需要的比较次数并非精确等于 log2(n)，而是与判定树的高度一致。对于 n 个元素，判定树的高度为 floor(log2(n)) 加一，因此最坏比较次数约为 log2(n+1) 向上取整。例如 n 等于 10 时，判定树高度为 4，最坏需要 4 次比较，而不是简单套用 log2(10) 约等于 3.32 得到 3 次。这种"取整后再加一"的细微差别，正是命题人设置陷阱的惯用位置。
折半查找有两种等价的实现形态，分别是迭代实现和递归实现。迭代实现使用一个循环，在 low 小于等于 high 的条件下反复计算中间位置并更新边界，循环结束时若未找到则返回失败标记。递归实现则把查找区间作为参数递归传入，每次比较后根据结果递归地在左半区或右半区继续查找，直到区间为空或找到目标。
软考对这两种实现的考查侧重点不同。选择题通常考查迭代实现中的边界条件，比如循环应该写成 low 小于等于 high 还是 low 小于 high，以及边界更新时 mid 应该加一还是减一。递归实现则更多出现在与递归复杂度分析相结合的题目中，考查考生对递归调用栈深度、空间复杂度的理解。需要特别指出的是，迭代实现的空间复杂度为 O(1)，只使用常数个辅助变量；而递归实现的空间复杂度为 O(log n)，因为递归深度与判定树高度相当，每一层递归都要占用栈空间。这一差异也是软考的潜在考点。
在实际工程和考试中，折半查找的目标并不总是"找到任意一个等于目标值的元素"，还可能衍生出多种边界查找需求。第一类是查找第一个等于目标值的元素，即当数组中存在多个重复的目标值时，返回最靠左的那个位置。第二类是查找最后一个等于目标值的元素，返回最靠右的位置。第三类是查找第一个大于等于目标值的元素位置，也就是通常所说的下界查找，它常用于维护有序集合的插入位置。
这三类变体虽然都基于折半查找，但边界更新的策略有本质区别。以查找第一个等于目标值的元素为例，当中间元素等于目标值时，不能立即返回，而应继续向左半区收缩，同时记录当前位置，直到区间为空，最终返回记录的位置。理解这些变体，能帮助考生在面对"在有序数组中查找某元素第一次出现的位置"这类题目时不再出错，也体现了折半查找作为一种思想工具的通用性。
折半查找最适合的场景是数据量较大且频繁查询、但很少插入删除的有序集合，例如静态字典、配置表、索引结构中的查找操作。因为折半查找对顺序存储的要求，导致它的插入和删除代价较高，每次插入或删除都可能需要移动大量元素来
本篇完！