扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软考软件设计师的上午综合知识考试里，查找算法从来都不是冷门考点。它不像排序算法那样动辄要求你默写八种算法的时间复杂度，也不像图论那样需要你在邻接矩阵和邻接表之间反复横跳，但它有一个鲜明的特点：只要掌握了，就是纯粹的送分题；一旦在细节上栽了跟头，丢分也丢得悄无声息。折半查找，正是查找家族里最典型、考得最频繁、也最容易在"看似简单"的题目里翻车的那一个。
所谓折半查找，又称二分查找，教材里的标准定义是这样的：在有序的顺序表中，先确定待查记录所在的范围区间，然后逐步缩小这个区间，直到找到目标记录或者确定目标记录不存在为止。这个定义虽然只有几十个字，却藏着三个必须精确把握的限定条件。第一，被查找的表必须是顺序存储的线性表，也就是数组。第二，表中的记录必须按照关键字有序排列，通常是升序，当然降序也可以，但必须全表统一。第三，查找过程依赖随机访问能力，也就是能够在常数时间内直接定位到任意一个下标位置。这三个条件缺一不可，缺了任何一个，折半查找就无法成立。
这里需要特别注意"顺序表"和"随机访问"这两个词的分量。很多考生知道折半查找要求"有序"，却常常忽略它同时要求"顺序存储"。一条单向链表里的数据即便排得整整齐齐，也不能用折半查找，因为链表只能从头结点开始逐个遍历，无法直接跳到中间位置。同样地，如果是链式存储的双向链表，虽然可以从两头访问，却依然无法做到下标级的随机定位。这一层限定，恰恰是命题人喜欢用来迷惑考生的地方——他们会在选项里给出一条"有序链表"，问能否用折半查找，正确答案一定是"不能"。
从数据结构的角度看，折半查找的本质是对一个有序区间进行不断的分治。每一轮比较，我们取当前区间的中间位置，把待查关键字和中间元素的关键字做一次比较，根据比较结果把查找范围砍掉一半。如果中间元素恰好等于目标值，查找成功；如果目标值比中间元素小，说明目标只能落在左半区，于是把右边界收缩到中间位置的前一个位置；如果目标值比中间元素大，说明目标只能落在右半区，于是把左边界收缩到中间位置的后一个位置。如此往复，区间的长度以指数速度减半，直到区间缩到空集，此时就可以断定查找失败。
这个概念定义虽然朴素，却支撑起了计算机科学里一个极为重要的思想：通过有序性换取查找效率。顺序查找在长度为 n 的线性表里平均要比较 n 除以 2 次，最坏要比较 n 次，时间复杂度是线性的；而折半查找最坏情况下的比较次数大约是以 2 为底 n 的对数，时间复杂度降到了对数级。当 n 很大时，两者的差距是数量级的。这正是折半查找能够在软考里占据一席之地的根本原因：它用一个"有序"的前提，换来了查找性能的质变。
理解了概念定义，我们还需要回到技术本质，把折半查找的运行机制一层一层拆开。只有真正搞懂了它的底层逻辑，才能在考场上面对各种变形题目时做到以不变应万变。
折半查找的核心动作，可以用一个非常简洁的循环来描述，它由三个步骤反复迭代而成。第一步，确定当前查找区间，用两个指针或者说两个下标来标记，一个指向区间的左端，一个指向区间的右端，初始时左端是整个表的下界，右端是整个表的上界。第二步，计算区间的中间位置，然后取出中间位置的元素，与待查关键字进行比较。第三步，根据比较结果收缩区间：相等则返回成功；小于则把右端收缩到中间位置减一；大于则把左端收缩到中间位置加一。
这里有一个隐藏的关键细节，就是循环的终止条件。什么时候停止？有两种停止情形。一种是中间元素恰好等于目标值，此时立即返回查找成功，算法结束。另一种是左端指针超过了右端指针，也就是查找区间变成了空集，此时说明目标值不在表中，返回查找失败。很多考生在写代码或者推演比较序列的时候，恰恰是在"左端大于右端才停止"这个边界上出错。他们习惯于写成"左端等于右端就停止"，结果漏掉了区间里最后一个元素的比较，导致要么找不到本应存在的元素，要么多算了一次本不该发生的比较。
中间位置的计算方式，是折半查找里最容易出题的第二个细节。标准写法是取左端和右端下标之和除以二，向下取整。这里的"向下取整"四个字，在软考里有着举足轻重的地位，因为历年真题里反复出现的一类计算题，就是给出一个具体的数组和一个目标值，问你查找过程中依次参与比较的元素是什么。这类题目能不能做对，全看你是不是严格按照"向下取整"的规则一步步算下来。一旦你在某个位置向上取整了，整个比较序列就会走岔，答案也就跟着错了。
如果说区间收缩是折半查找的过程视角，那么判定树就是折半查找的结构视角。把折半查找的每一次比较过程抽象成一颗二叉树，每个内部结点代表一次关键字比较，比较结果向左或向右分别进入左子树或右子树，最终落到成功结点或者失败结点上，这棵树就叫做折半查找的判定树。
判定树有一个非常优美的性质：对于长度为 n 的有序表，它的判定树是一颗二叉排序树，并且这颗树近似于一颗完全二叉树。之所以说"近似"，是因为折半查找的中间位置计算方式会让树的具体形状略有波动，但整体上，判定树的高度就是查找成功时最坏情况下的比较次数，这个高度大约是 log2(n+1) 向上取整。这个性质直接解释了折半查找时间复杂度的来源：每比较一次，问题规模缩小一半，缩小到一的次数就是对数的数量级。
判定树在软考里之所以重要，还因为它和平均查找长度直接挂钩。所谓平均查找长度，记为 ASL，指的是在查找过程中关键字比较次数的平均值。对于查找成功的情况，ASL 等于判定树中每个内部结点的深度之和除以结点总数。对于查找失败的情况，ASL 等于判定树中每个失败结点（也就是空指针位置）的深度之和除以失败结点的总数。这类 ASL 计算题在软考里时有出现，而计算的关键，就是先正确地画出判定树，再逐层统计深度。
为什么折半查找的时间复杂度是 O(log n)？这个问题值得从数学上严谨地推一遍，因为理解了这个推导，你就再也不会去死记硬背结论了。假设初始查找区间长度为 n，每比较一次，区间长度至少减半，那么经过 k 次比较之后，区间长度最多是 n 除以 2 的 k 次方。当这个长度小于一，也就是区间彻底清空时，查找结束。于是我们得到不等式 n 除以 2 的 k 次方 小于一，解得 k 大于以 2 为底 n 的对数。也就是说，最坏情况下比较次数不会超过 log2 n 再加一次，因此折半查找的时间复杂度是对数级的。
这个对数级的复杂度，是折半查找相对于顺序查找最核心的优势所在。顺序查找的平均比较次数约为 n 除以二，最坏为 n，是线性复杂度。当 n 等于一百万时，顺序查找最坏要比较一百万次，而折半查找最坏只要比较二十次左右，这个差距是触目惊心的。当然，天下没有免费的午餐，折半查找付出的代价是"表必须有序"，而维护有序性本身需要额外的排序成本。所以在实际工程中，如果表很少变动而查找非常频繁，先排一次序再反复折半查找是划算的；如果表频繁插入删除，那么维持有序的代价可能反而不如直接顺序查找来得经济。这一层权衡，也是软考里偶尔会考到的分析型考点。
折半查找并不是孤立存在的，它身处一个庞大的查找算法家族之中。搞清楚它和家族其他成员之间的区别与联系，是软考综合知识考试里经常出现的一类辨析题。这里我们系统地把查找算法梳理一遍。
最基本的查找方法是顺序查找，它对表的存储结构和有序性都没有任何要求，从表头到表尾逐个比较，适用于任何线性表。顺序查找的优点是适应性极强，缺点是效率低，平均查找长度为 n 加一 除以二，时间复杂度为线性。软考里常把顺序查找和折半查找放在一起考，考的就是"有序 + 顺序存储"这个前提条件的有无。
分块查找，也叫索引顺序查找，是介于顺序查找和折半查找之间的一种折中方案。它把整个表分成若干块，块与块之间按关键字有序，也就是前一块里任意元素都小于后一块里的任意元素，而每一块内部可以无序。查找时先折半查找索引表确定目标落在哪一块，再到那一块内部顺序查找。分块查找兼具了两者的特点，是软考里一个容易被忽略却又可能出现的考点。
折半查找与这两者的本质区别在于，它要求整个表全局有序且顺序存储，从而把查找效率从线性提升到对数。命题人喜欢在选择题里把三者的适用前提、时间复杂度、平均查找长度混在一起，让考生去匹配，这种题目只要把三者的核心特征记牢，就是送分。
折半查找的中间位置是固定的"二分之一"，这其实是假设关键字在整个区间内是均匀分布的。如果分布很不均匀，那么固定取中点就不一定是最优的。插值查找正是对这一点的改进，它根据目标值在区间内的相对位置，动态地估算目标值更可能落在哪里，从而更快地逼近目标。插值查找特别适合关键字均匀分布且表很大的场景，它的平均性能优于折半查找，但在分布极端不均时可能退化。
斐波那契查找则是另一种变体，它利用斐波那契数列来划分查找区间，中间位置不再是简单的二分之一，而是按照黄金分割的比例来切分。斐波那契查找在某些硬件环境下有
本篇完！