折半查找(Binary Search,又称二分查找)是一种在有序线性表中进行的高效查找算法。它的标准定义可以表述为:在采用顺序存储结构且关键字有序排列的线性表中,每次将待查找区间与区间中点位置的关键字进行比较,若相等则查找成功,若不相等则根据大小关系舍弃一半的区间,将查找范围缩小到剩余的一半,如此反复,直到查找成功或查找区间为空为止。
教科书通常给出这样的形式化描述:设查找表为 R[1..n],其中关键字按非递减顺序排列,即 R[1].key ≤ R[2].key ≤ ... ≤ R[n].key。查找目标为给定值 K。折半查找首先令 low=1、high=n,计算中点 mid=⌊(low+high)/2⌋,将 K 与 R[mid].key 比较:若 K 等于 R[mid].key,查找成功,返回位置 mid;若 K 小于 R[mid].key,说明 K 只可能落在左半区间,令 high = mid - 1;若 K 大于 R[mid].key,说明 K 只可能落在右半区间,令 low = mid + 1。重复上述过程,直到 low > high 时仍未找到,则查找失败。
折半查找的本质,是在每一轮比较中利用"有序"这一前提,将搜索空间以近似对半的方式削减。因为每比较一次,问题规模就缩小为原来的一半,所以它的时间复杂度为 O(log2n),这比顺序查找的 O(n) 有数量级上的优势。当 n 取 1024 时,折半查找最多比较约 10 次,而顺序查找平均要比较 512 次,两者相差数十倍。
折半查找并非万能,它有两个不可违背的前提条件。第一,存储结构必须是顺序存储结构,即数据必须存放在可以随机存取的数组中。链表虽然也能保持有序,但由于链表结点之间靠指针连接,无法在 O(1) 时间内直接定位到第 mid 个结点,因此链表无法使用折半查找。第二,关键字必须有序。无序的数组即使套用折半查找的逻辑,也无法保证"舍弃一半"的正确性,因为无法通过中间元素的大小判断目标在哪一侧。
这两个条件常常是软考命题人设置陷阱的落点。考生需要牢记一个判断:折半查找等于顺序存储加上有序。任何一个条件不满足,折半查找都无法成立。反过来说,凡是满足这两个条件的有序顺序表,折半查找几乎总是优于顺序查找。
折半查找与顺序查找的差异,本质上体现的是"有序"这一附加信息带来的收益。顺序查找不要求数据有序,因此它无法利用关键字之间的偏序关系,只能逐个比对,平均要比较约 n/2 次。折半查找则把"有序"转化为"可以排除一半"的能力,把比较次数压到了对数级。这一对比揭示了一条重要的设计原则:当数据集合能够提供额外结构信息时,利用这些信息往往能带来数量级的效率提升。软考也常常以此设问,要求考生在给定场景下判断应选用顺序查找还是折半查找,判断的唯一依据就是查找表是否满足"顺序存储且有序"这两个前提。
查找算法的效率用平均查找长度(ASL,Average Search Length)来衡量。ASL 的定义是:为确定记录在查找表中的位置,需要与给定值进行比较的关键字个数的期望值。对含有 n 个记录的查找表,查找成功时的平均查找长度记为 ASL_succ,它是所有记录查找成功所需比较次数的加权平均;查找失败时的平均查找长度记为 ASL_fail,它是所有可能的失败区间查找失败所需比较次数的平均。
对折半查找而言,其查找过程可以抽象为一棵二叉树,这棵二叉树被称为判定树。判定树的形态决定了 ASL 的数值。对含有 n 个记录的折半查找,查找成功时的平均查找长度近似等于 log2(n+1) 减去 1。这一公式的推导依赖于判定树的平衡特性,是后文原理机制部分要展开的核心内容。
折半查找之所以高效,根源在于它的查找过程对应着一棵近似满二叉树的判定树。理解判定树,就等于理解了折半查找的全部底层逻辑。判定树不仅是推导 ASL 的工具,更是软考计算题的解题核心。
把折半查找的每一轮比较看作判定树的一个结点,结点的值是本轮比较的中间位置下标对应的关键字。第一次比较的 mid 是整棵判定树的根;此后,向左子区间查找的动作对应走向根的左子树,向右子区间查找的动作对应走向根的右子树。如此递归展开,就能得到一棵完整的判定树。
以包含 10 个元素的有序表(3,14,27,39,42,55,70,85,93,98)为例。第一轮 mid 等于 5(向下取整),对应关键字 42,它是根结点。左子区间为下标 1 到 4,其中点 mid 等于 2,对应 14,成为根的左孩子;右子区间为下标 6 到 10,中点 mid 等于 8,对应 85,成为根的右孩子。继续递归,14 的左孩子是下标 1 的 3,右孩子是下标 3 的 27;27 的右孩子是下标 4 的 39。85 的左孩子是下标 6 的 55,右孩子是下标 9 的 93;55 的右孩子是下标 7 的 70,93 的右孩子是下标 10 的 98。
最终这棵判定树的形态是:根结点 42;第二层是 14 和 85;第三层是 3、27、55、93 四个结点;第四层是 39、70、98 三个结点。显然,这棵树是一棵近似完全二叉树,除最后一层外其余各层全部填满。
判定树有一个极其重要的性质:某个记录的查找成功所需的比较次数,恰好等于该记录对应结点在判定树中的深度,根结点深度记为 1。根结点 42 只需比较 1 次即可命中;第二层的 14、85 需要比较 2 次;第三层的 3、27、55、93 需要比较 3 次;第四层的 39、70、98 需要比较 4 次。
由此可以计算查找成功的平均比较次数。上述 10 个元素的例子中,比较次数总和为 1 乘以 1 加 2 乘以 2 加 3 乘以 4 加 4 乘以 3,结果为 29,除以记录总数 10,得到成功平均查找长度等于 29 除以 10,即 2.9。这就是软考计算题的标准解法:先画出判定树,统计各层结点数,再按"深度乘结点数求和除以 n"得出答案。
查找失败的情形同样可以用判定树刻画。判定树中每一个空缺的孩子位置(空指针)都对应一个失败区间。对 n 个元素的有序表,判定树共有 n+1 个失败结点。上述例子中,失败结点共有 11 个,其中深度为 3 的失败结点有 5 个,深度为 4 的失败结点有 6 个,于是查找失败的平均比较次数为 5 乘以 3 加 6 乘以 4 再除以 11,结果等于 39 除以 11。这正是 2022 年下半年软考软件设计师真题的考点。
判定树的高度决定了折半查找在最坏情况下需要比较的次数。对含有 n 个元素的有序表,判定树的高度为 log2(n+1) 向上取整。这意味着折半查找无论成功与否,最多比较 log2(n+1) 向上取整次,时间复杂度为 O(log2n)。
为什么判定树能保持近似满二叉树?因为每一轮取中点 mid 等于 low 加 high 之和除以 2 向下取整,左子区间和右子区间的元素个数最多相差 1,保证了左右子树高度差不超过 1。这正是折半查找判定树天然平衡的原因。若把 mid 的取法改成偏向一侧,判定树就会失衡,最坏情况下退化为近似线性,效率随之下降。软考命题有时会考查"若 mid 取法不同,判定树形态如何变化",考生需理解中点取法对平衡性的影响。
折半查找的基本形态是"查找是否存在",但在实际工程中,需求往往更复杂,由此衍生出一系列变体。理解这些变体,既能应对算法设计题,也能在真实的软件开发中写出正确的二分逻辑。
第一类是查找第一个等于目标值的元素。当有序表中存在多个相同的关键字时,标准折半查找可能命中任意一个相等元素,而变体要求返回最左边的那个。实现时,当 mid 命中目标后不能立即返回,而是继续令 high = mid - 1 向左收缩,同时记录当前候选位置,直到 low 大于 high 为止,最后记录的候选位置就是第一个等于目标的位置。
第二类是查找第一个大于等于目标值的元素,即所谓的下界,通常称为 lower_bound。当 mid 位置的关键字大于等于目标时,令 high = mid - 1 并记录候选位置;否则令 low = mid + 1。循环结束时 low 指向的位置就是第一个大于等于目标的元素。这个变体在"求有序序列中某个值的插入位置"问题中极为常用。
第三类是查找第一个大于目标值的元素,即上界,通常称为 upper_bound。它和下界的区别仅在于判定条件从"大于等于"改为"严格大于"。这三个变体的核心差异都体现在边界收缩时对 mid 的处理上，是二分查找最容易写出死循环或漏解的地方。
除这三类变体外，折半查找还可与分块查找对照理解。分块查找又称索引顺序查找，它把查找表分为若干块，块内记录可以无序，但块与块之间必须按关键字有序，即前一块中任一记录的关键字都小于后一块中任一记录的关键字，同时另建一个索引表，索引项存放每块的最大关键字和该块的起始位置。查找时先在索引表中用折半查找确定目标所在的块，再在该块内用顺序查找定位目标。分块查找正是折半查找与顺序查找的结合，它放松了折半查找对全表有序的严格要求，只需块间有序，因此在数据频繁插入删除的场合更具实用性。软考常把三者放在一起考查效率：折半查找平均查找长度约为对数级，分块查找介于顺序查找与折半查找之间，顺序查找约为线性级。理解分块查找，有助于考生从整体上把握查找算法的设计权衡。
折半查找还与二叉排序树存在深刻联系。将折半查找的判定树当作一棵二叉排序树来看待，会发现二者在结构上完全同构：判定树中任意结点的左子树关键字都小于它，右子树关键字都大于它，这正是二叉排序树的定义性质。折半查找适用于静态的顺序有序表，而二
本篇完！