折半查找又称二分查找，是数据结构与算法课程中最经典、最基础的查找算法之一。在软件设计师、系统分析师、软件评测师等多个软考科目的考试大纲中，折半查找属于查找章节的核心考点，几乎每年都会以选择题或算法描述题的形式出现。本文将从概念定义、原理机制、分类应用、常见误区、真题关联、备考总结六个层面，把这一考点彻底讲透。
折半查找的严格定义可以表述为：在按关键字有序排列的线性表中，每次将待查关键字与表中间位置元素的关键字进行比较，根据比较结果确定下一次查找的子区间，从而将查找区间每次缩小一半，直至找到目标元素或确定目标元素不存在为止的查找方法。这个定义看似简单，实则包含了若干必须精确把握的限定条件，任何一个条件被忽略，都会导致对算法适用范围与性能的错误判断。
从算法形式化的角度看，折半查找可以描述为一个不断收缩区间的迭代过程。设查找区间为闭区间，左端点为 low，右端点为 high，初始时 low 指向表的第一个元素，high 指向表的最后一个元素。每一次迭代计算中间位置 mid，将待查关键字 key 与表中第 mid 个元素的关键字进行比较：若二者相等，则查找成功，返回 mid；若 key 小于中间元素，则说明 key 只可能出现在 mid 左侧的子区间，于是将 high 更新为 mid 减一；若 key 大于中间元素，则说明 key 只可能出现在 mid 右侧的子区间，于是将 low 更新为 mid 加一。上述过程反复进行，直到 low 大于 high，此时区间为空，说明查找失败。这种以区间为空作为失败判定依据的做法，是折半查找正确性的关键所在。考生在理解这一形式化过程时，务必分清闭区间约定下区间为空的判断条件，即 low 严格大于 high，这是后续边界条件分析的基础。
折半查找的定义中隐含了两个必须同时满足的适用前提。第一个前提是存储结构必须支持随机存取。折半查找之所以能够在一次比较之后直接跳转到中间位置，依赖的是顺序存储结构带来的下标定位能力。如果线性表采用链表存储，即使元素已经有序，也无法在常数时间内定位到中间元素，折半查找的效率优势便会荡然无存。第二个前提是关键字的排列必须有序，通常要求按关键字递增或递减排列。有序性是折半查找每次都能确定性地排除一半候选区间的前提，因为只有有序，才能根据中间元素与目标关键字的比较结果，断言目标关键字要么位于前半段、要么位于后半段，而不是分散在任意位置。
很多考生在记忆折半查找时只记住了"有序"两个字，却忽略了"顺序存储"这一同等重要的前提，这恰恰是命题人常设陷阱的地方。顺序存储保证了对中间元素的随机存取，使每次定位中间元素的时间开销为常数级别。假如把同样的比较逻辑套用在单链表上，虽然逻辑上似乎可行，但为了找到中间元素，每次都必须从头结点开始顺序扫描到中间位置，这一扫描操作本身就耗费线性时间，彻底抵消了折半查找对数级的比较优势。因此，凡是在题目中看到"链式存储"或"链表"与"折半查找"搭配出现，通常就是在考察考生对适用前提的把握，标准答案往往是"折半查找不适用于链表存储结构"。
折半查找的本质是一种典型的分治算法，或者更准确地说，是一种减治算法。它并不像快速排序那样把问题拆分成两个都要处理的子问题，而是在每一次比较之后，直接丢弃掉不可能包含目标的一半区间，只保留可能包含目标的那一半继续处理。这种"每次减半"的策略，决定了折半查找的时间复杂度为对数级别，也决定了它在查找问题中无可替代的高效地位。
从数学本质上讲，折半查找之所以高效，是因为它把查找问题转化成了一个等分缩小的过程。假设初始区间包含 n 个元素，第一次比较之后，无论结果如何，候选区间都会被压缩到不超过 n 的一半；第二次比较之后，候选区间进一步缩小到不超过 n 的四分之一；依此类推，经过 k 次比较，候选区间最多剩下 n 除以 2 的 k 次方个元素。当候选区间被压缩到 1 个元素时，最多再进行一次比较即可确定结果。于是查找的比较次数最多为 log2(n) 向下取整再加 1 次。与顺序查找在最坏情况下需要比较 n 次相比，折半查找在 n 较大时优势极为显著，这正是它被广泛采用的根本原因。
需要强调的是，折半查找的比较次数是相对稳定的，不像顺序查找那样受目标元素位置的影响巨大。对于成功查找而言，目标元素越靠近判定树的根结点，比较次数越少；越靠近叶子层，比较次数越多。对于失败查找而言，比较次数则相对集中在判定树的空指针层附近。这种比较次数与判定树深度的对应关系，是计算平均查找长度的基础，也是命题人考察的重点。考生必须能够从一次比较消除一半候选这一朴素事实出发，推导出对数级的时间复杂度，而不是死记硬背结论。
为了直观刻画折半查找的比较过程，可以把折半查找过程表示为一棵判定树。判定树的根结点是第一次比较的中间元素，左子树对应左半区间，右子树对应右半区间。判定树是一棵平衡的二叉树，它的形状与具体的数据个数有关，但始终满足左右子树的高度差不超过一。查找成功时，比较次数等于目标元素所在结点在判定树中的层次；查找失败时，比较次数等于从根到对应空指针结点所经过的层次。理解判定树，是解折半查找平均比较次数计算题的核心工具。
判定树与普通二叉树的本质区别在于，判定树描述的是查找过程中比较发生的逻辑顺序，而非数据实际存储的物理结构。同一种有序序列，只要折半查找的中间元素取法一致，其判定树就是唯一确定的。判定树的叶子层之下，还悬挂着若干表示失败情况的空指针结点，这些空指针结点的数量恰好等于元素总数加一，对应着所有可能的失败区间。正是这些空指针结点，构成了失败查找平均比较次数计算的依据，这一点在真题解析部分会详细展开。
值得深入思考的一个问题是，为什么折半查找的比较次数波动远小于顺序查找。顺序查找在最坏情况下需要比较 n 次，最好情况下只需要比较 1 次，二者的差距达到 n 倍，性能波动剧烈。而折半查找无论目标元素位于何处，其比较次数都被牢牢限制在判定树的深度范围之内，最好情况与最坏情况之间的差距通常不超过几次。这种稳定性的来源，在于折半查找不依赖目标元素的实际位置，而是依赖区间的几何折半特性，每一次比较都严格地把候选空间压缩一半，从而使查找深度与区间长度之间呈现确定的对数关系。理解了这一点，考生在对比不同查找算法性能时，就不会仅仅停留在比较次数的大小上，而是能够从波动性、稳定性、前提条件等多个维度综合评估，从而在考查查找方法选择的题目中给出有说服力的判断。
折半查找在工程实现上有递归与非递归两种形态，这两种形态在逻辑上完全等价，但在运行开销与适用场景上略有差异。此外，折半查找的思想还衍生出了插值查找、斐波那契查找等变体算法，理解这些变体的来龙去脉，有助于考生从更高的视角把握折半查找的设计精髓。
非递归实现通过显式的循环与区间端点变量来维护查找区间，空间复杂度为常数级别，是工程实践中最常用的形态。递归实现则通过函数自身调用，把查找区间作为参数传递下去，每次递归处理一个子区间。递归实现的代码更为简洁，但由于每次递归调用都会产生函数调用栈的额外开销，在查找区间较大时，递归深度虽为对数级、本身不构成栈溢出风险，但其常数因子略高于非递归实现。软考真题中，涉及折半查找的题目多数以算法流程描述或计算题的形式出现，较少要求考生手写完整代码，但考生仍应准确掌握两种实现中区间收缩的细节，尤其是 low 与 high 的更新规则，因为这直接决定了边界条件是否正确。无论是递归还是非递归实现，其核心都是三件事：计算中间位置、比较并收缩区间、判断是否找到或失败。把握住这三件事，就能在算法描述型题目中准确还原出完整的折半查找流程。
折半查找的思想还衍生出了若干变体算法。插值查找是对折半查找的一种改进，它不再固定取中间位置，而是根据关键字在区间内可能的分布位置，用一个按比例估算的位置来取代 mid，适用于关键字分布均匀且表长较大的场景。在关键字分布极端不均匀时，插值查找可能退化为接近顺序查找的性能。此外，斐波那契查找也是一种利用斐波那契数列来划分区间的变体，它在某些不支持除法运算或除法开销较大的硬件环境下具有一定优势。折半查找的思想还被广泛应用到各种实际问题中，例如有序数组的插入位置定位、旋转
本篇完！