扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找是软考软件设计师、系统分析师数据结构模块中出镜率最高的查找算法之一。它在试卷上的身份十分特殊：题目通常不考实现代码，而是考查找过程中参与比较的元素序列、平均查找长度 ASL 的计算，以及它苛刻的适用前提。正因为它不考代码，许多考生反而容易在概念边界上翻车，把送分题做成丢分题。本文从折半查找的严格定义出发，一路拆解到判定树、ASL 计算公式和历年真题的命题套路，帮助读者把这一个知识点彻底吃透。
折半查找，英文名称 Binary Search，中文也常译作二分查找，是建立在有序顺序表基础之上的一种查找算法。教材中给出的标准定义是：折半查找每次将待查找的区间划分为前后两个长度大致相等的子区间，取中间位置的元素与目标关键字进行比较，根据比较结果决定下一次查找是在前半个区间还是后半个区间继续进行，如此反复，直到找到目标元素或查找区间为空为止。
这个定义背后隐藏着两个必须同时满足的前提条件，缺少任何一个，折半查找都无法成立。第一，查找表必须采用顺序存储结构。折半查找的核心动作是每次跳到区间中间位置取元素，这一跳要求存储结构支持随机访问，能够在常数时间内定位到任意下标。第二，查找表中的元素必须按照关键字有序排列，通常约定为升序，也可以约定为降序。有序性是折半查找能够依据比较结果果断放弃一半区间的根本依据。
折半查找的成立条件可以被提炼为三点，这三点在真题中反复以选择题的形式出现。第一是顺序存储，即元素必须存放在一片连续的内存空间中，用数组实现。第二是关键字有序，要么整体升序，要么整体降序，但必须方向一致。第三是静态查找表，即查找过程中不进行插入和删除操作，因为任何插入删除都会破坏有序性并引发大量元素移动。这三点中，前两点是硬性前提，第三点则是应用层面的隐含要求。
与之相对的是顺序查找，顺序查找对存储结构没有任何要求，顺序存储和链式存储都可以，对关键字的有序性也没有要求。折半查找用苛刻的前提换来了极高的查找效率，这是一笔用约束换性能的交易。理解了这一点，就能理解为什么折半查找只出现在数组这种连续存储的场景里，而链表场景只能退而使用顺序查找。
折半查找的整个查找过程可以抽象成一棵二叉树，这棵树被称为判定树，或者更具体地称为二叉判定树。判定树的根节点对应第一次比较的中间位置元素，它的左子树对应左半区间的查找过程，右子树对应右半区间的查找过程。每一次比较，相当于在判定树上从当前节点走向左孩子或者右孩子，查找成功就是走到了某个内部节点，查找失败则是走到了判定树的空指针位置。
判定树的引入让折半查找的时间复杂度分析变得一目了然。折半查找每比较一次，查找区间就缩小一半，因此查找长度最多不超过判定树的高度。对于含有 n 个元素的有序表，判定树的高度近似等于 log2 的 n 取整再加一，所以折半查找的时间复杂度是 O(log n)。这个量级的优越性在 n 较大时体现得极为明显，例如在一万个元素中查找，最坏情况也只需要大约十四次比较。
折半查找的实现原理可以用三个下标变量来完整描述，这三个变量是 low、high 和 mid。low 指向当前查找区间的第一个位置，high 指向当前查找区间的最后一个位置，mid 则取 low 与 high 的中间位置，即 mid 等于 low 加 high 之和除以二。查找开始时，low 取一，high 取表长 n。每一步取出下标为 mid 的元素，将其关键字与目标值进行比较。
每一次比较会出现三种可能的结果，分别对应三种不同的区间收缩动作。第一种情况是中间元素的关键字恰好等于目标值，此时查找成功，算法立即返回 mid 位置。第二种情况是中间元素的关键字大于目标值，说明目标元素如果存在，只能落在左半区间，于是把 high 调整为 mid 减一。第三种情况是中间元素的关键字小于目标值，说明目标元素如果存在只能落在右半区间，于是把 low 调整为 mid 加一。每一次比较，要么成功返回，要么把查找区间缩小一半。
当 low 大于 high 时，说明查找区间已经收缩为空，目标元素不存在于表中，查找以失败告终。这个 low 大于 high 的终止条件是折半查找实现中最容易写错的地方。很多初学者在写循环条件时，会把 low 小于 high 和 low 小于等于 high 混淆。正确的做法是，只要 low 小于等于 high，区间内就至少还有一个待比较元素，循环就应当继续，直到 low 越过 high 才结束。
把这三个变量和三种分支理解透彻之后，就能自己复现折半查找的完整执行轨迹。以查找序列 A 的第十三个元素为例，low 从一出发，high 从二十出发，第一次 mid 等于十，比较后目标大于中间值，low 更新为十一；第二次 mid 等于十五，比较后目标小于中间值，high 更新为十四；第三次 mid 等于十二，比较后目标大于中间值，low 更新为十三；第四次 mid 等于十三，命中返回。整个过程中 low 与 high 不断向目标位置逼近，区间长度依次从二十缩到十、再缩到四、再缩到二、最后缩到一，完美体现了每次比较缩小一半区间的核心思想。掌握了这条执行轨迹，任何一道区间收缩还原题都能迎刃而解。
判定树的深度直接决定了折半查找在最坏情况下需要比较的次数。对于一个含有 n 个元素的升序有序表，折半查找的判定树是一棵近乎满的二叉树，其高度为 log2 的 n 向下取整再加一。查找任意一个元素的过程中，比较次数等于该元素在判定树中所处节点的层数，最坏情况就是走到判定树最深的一层。因此折半查找的最大查找长度就是判定树的高度。
这里需要特别说明的是，折半查找的判定树并不一定是一棵完全平衡的二叉树，因为当区间长度是偶数时，中间位置存在向下取整和向上取整两种约定，不同的取整方向会让判定树略微左倾或右倾。但无论采用哪种取整约定，判定树的高度都稳定在 log2 的 n 加一的量级上，时间复杂度保持不变。软考真题在考察这一点时，往往会给出一个具体的查找序列，让考生判断中间位置到底取的是哪个元素，从而检验考生对取整方向的掌握程度。
折半查找的时间复杂度推导可以从最坏情况的比较次数入手。假设有序表长度为 n，第一次比较后区间长度不超过 n 除以二，第二次比较后不超过 n 除以四，依此类推，第 k 次比较后区间长度不超过 n 除以二的 k 次方。查找结束意味着区间长度收缩到一以下，也就是 n 除以二的 k 次方小于一，解得 k 大于 log2 的 n，因此最坏比较次数约为 log2 的 n，时间复杂度为 O(log n)。
折半查找的空间复杂度是 O(1)，因为它只需要 low、high、mid 三个变量，不随问题规模增长。相比之下，顺序查找的时间复杂度是 O(n)，平均查找长度约为 n 加一除以二。当 n 较大时，O(log n) 对 O(n) 的优势是碾压性的，这就是折半查找被广泛使用的原因。折半查找也有局限性，它只适用于有序的顺序表，对于需要频繁插入删除的动态查找场景，二叉排序树才是更合适的选择。
查找算法在软考考纲中是一个完整的知识族，折半查找只是其中的一员。要真正理解折半查找的定位，必须把它放回整个查找算法体系中，与顺序查找、分块查找进行横向对比，同时了解插值查找、斐波那契查找这两个在它基础上衍生出来的变体。这种体系化的理解方式，恰恰是软考命题人喜欢考察的视角。
顺序查找是最朴素的查找方式，从头到尾逐个扫描，对存储结构没有要求，对有序性没有要求，优点是简单通用，缺点是平均查找长度较长。折半查找要求顺序存储和有序排列，用这两个约束换来了 O(log n) 的时间复杂度。分块查找又称索引顺序查找，它是前两者的折中方案，先把表分成若干块，块内元素可以无序，但块与块之间必须有序，即前一块中所有元素都小于后一块中所有元素，再为每一块建立一个索引表，记录该块的最大关键字和起始地址。
分块查找的查找过程分两步进行：第一步在索引表中查找，确定目标元素可能落在哪一个块，索引表是有序的，可以用折半查找，也可以用顺序查找；第二步在确定的块内进行顺序查找。分块查找的平均查找长度等于索引查找的平均查找长度加上块内查找的平均查找长度。这种三段式的对比，是软考在查找这一章最经典的出题框架，考生需要明确三者各自的适用条件、存储结构要求和平均查找长度的计算方法。