扫码获取 VIP 码
添加管理员微信获取 VIP 码
查找是数据结构里最基础、也最容易被考生轻视的一类操作。绝大多数考生拿到查找题，第一反应是"这不就是找个数吗"，草草选个答案了事。可正是这种轻敌心态，让查找题成了软考软件设计师考试里每年必考、每年都有人栽跟头的丢分重灾区。而在所有查找算法中，折半查找（又称二分查找）又是命题人最偏爱的一个。它的前提条件、判定树结构、平均查找长度计算，以及让人头疼的比较序列合法性判断，每个环节都藏着可以设陷阱的细节。这篇文章就沿着概念定义、原理机制、分类应用、常见误区、真题关联、备考总结六条线索，把折半查找从头拆解一遍，让读者看完之后遇到折半查找的题目都能稳稳拿分。
在讲任何算法之前，我们都要先给它下一个足够精确的定义。折半查找，英文叫 Binary Search，中文里又常被写作二分查找，是一种建立在有序顺序表之上的查找算法。它的正式定义可以这样表述：折半查找是在一个按关键字有序排列的顺序存储线性表中，通过不断将待查找区间对半缩小，从而定位目标记录位置的一种查找方法。
这个定义里藏着两个绝对不能忽略的前提。第一个前提是顺序存储，也就是说，这个线性表必须是用一段连续的存储空间存放的，能够支持通过下标直接访问任意位置的元素。第二个前提是有序，也就是说，表中的记录必须按照关键字排好了序，要么从小到大，要么从大到小。这两个前提缺一不可，任何一个不满足，折半查找都无法成立。
从算法设计策略的角度看，折半查找采用分治思想，是把一个规模为 n 的问题分解成子问题、逐个求解再合并。折半查找的特殊之处在于，它每一轮只处理一半、直接舍弃另一半，是一种只减不并的分治，教科书通常把它归到减治策略范畴。这一点在考试里有直接对应，后面的真题部分会专门考察。
折半查找的查找效率之所以高，根源就在于这个"对半"的动作。每比较一次，查找范围就缩小一半。如果表中有 n 个元素，那么在最坏情况下，折半查找需要的比较次数大约是 log2n 这个量级，这和顺序查找最坏情况下需要 n 次比较相比，是一个质的飞跃。当 n 很大时，log2n 的威力会体现得淋漓尽致：一张一百万元素的表，顺序查找最坏要找一百万次，折半查找最多约二十次。
理解了定义，我们再来看看折半查找在计算机内部到底是怎么一步一步运行起来的。这个过程如果只看文字描述会显得抽象，所以我们不妨把它想象成一个不断收缩的区间。
折半查找在实现上，通常用两个下标来标记当前的查找范围。习惯上把它们记作 low 和 high，low 指向区间的左端，high 指向区间的右端。一开始，low 指向整个表的第一个元素，也就是下标 0，high 指向最后一个元素，也就是下标 n 减 1。整个算法的核心，就是在这两个指针之间取中点，然后根据比较结果，让其中一个指针跳过来，从而把区间缩小到原来的一半。
中点的计算方式是取 low 和 high 的算术平均值。这里有一个特别容易出错的细节，就是取整的方向。当 low 加 high 的结果是奇数时，平均值会带有小数部分，此时到底是向下取整还是向上取整，必须有一个统一的规定。在绝大多数教材和历年真题中，折半查找的中间位置都采用向下取整的方式，也就是 floor。这个取整方向看似是个无关紧要的实现细节，但它会直接影响查找过程中实际参与比较的元素序列，进而影响比较序列判断题和平均查找长度计算题的答案，所以必须从一开始就牢牢锁定。
取到中点之后，算法要做的就是把中点位置的元素和待查找的关键字进行比较。比较的结果无非三种，对应三种不同的走向。如果中点元素恰好等于目标关键字，那么查找立即成功，算法结束，返回这个中点的下标。如果目标关键字小于中点元素，由于表是有序的，说明目标元素如果存在，一定只可能落在左半部分，于是把 high 移动到 mid 减 1 的位置，在左半个区间里继续同样的操作。反之，如果目标关键字大于中点元素，说明目标只可能落在右半部分，于是把 low 移动到 mid 加 1 的位置，在右半个区间里继续查找。
这三种走向构成了一个完整的循环体。这个循环会一直执行下去，直到两种结局之一出现：要么在某一轮比较中命中目标，查找成功；要么 low 越过了 high，也就是说查找区间变成了空区间，此时说明目标元素根本不在表里，查找失败。这里要特别强调循环的终止条件，它是 low 大于 high，而不是 low 等于 high。很多初学者会把条件写成 low 小于 high，这样一来，当区间收缩到只剩一个元素的时候，循环就提前退出了，那唯一一个还没被检查的元素就永远被漏掉了。这个错误在笔试和机试里都极其常见。
折半查找的整个过程，其实可以用一棵二叉树来精确刻画，这棵树叫折半查找判定树，是理解折半查找所有考点的一把钥匙。判定树的构造方式是这样的：把每一次比较对应的那个中点元素当作树的一个结点，第一次比较的根结点，就是整个表的中间位置；如果目标比它小，下一步向左走，左子树的根就是左半区间的中间元素；如果目标比它大，下一步向右走，右子树的根就是右半区间的中间元素。如此递归下去，每一个可能的查找路径，都对应判定树里从根到某个结点的一条路径。
判定树有一个优美的性质：查找某元素所需的比较次数，恰好等于它在判定树中所处的层数。根结点在第一层、比较一次命中，第二层比较两次，第三层比较三次，以此类推。这样一来，平均查找长度的计算就转化为对判定树各层结点个数的加权求和。判定树还纳入了查找失败的情况：当查找区间为空时，对应位置是判定树里的空指针位置，称为外部结点或失败结点。含 n 个元素的表，判定树内部结点有 n 个，外部结点即失败结点有 n 加 1 个。这个 n 加 1 是计算失败查找平均比较次数的核心，也是历年真题反复考察的点。
折半查找并不是孤立的，它处在一整个查找算法的家族里。要真正吃透折半查找，就必须把它放到这个家族里，和它的两个近亲做一个横向对比，看清各自的适用边界。
线性表的查找，从算法设计上讲，最经典的就是三种：顺序查找、折半查找和分块查找。顺序查找最朴素，从表头逐个往后扫描直到找到目标或扫完整个表。它最大的优点是对表没有任何要求，不管顺序存储还是链式存储、有序还是无序都能用；缺点是效率低，平均要比较约 n 的一半这么多次，时间复杂度是线性量级。
折半查找则走向了另一个极端，它对表的要求最苛刻，必须顺序存储且有序，但换来的是对数级的高效率。分块查找，又叫索引顺序查找，是前两者的一种折中。它把整个表分成若干块，块与块之间保证有序，也就是前一块里所有的元素都小于后一块里所有的元素，但每一块内部的元素可以随意排列。查找的时候，先用顺序查找或者折半查找定位到目标所在的块，然后再到那一块内部去做顺序查找。分块查找的平均查找长度，就落在顺序查找和折半查找之间。这三种查找算法的对比，是历年考试里一道绕不过去的基础题，考察的核心就是它们各自对表结构的要求和各自的效率高低。
折半查找的两个前提条件，决定了它的适用边界。第一个边界是存储结构必须是顺序的，也就是数组。为什么链表不行？根本原因在于折半查找需要在常数时间内随机访问任意下标的元素，而链表做不到这一点。链表的元素是通过指针串联起来的，要访问第 i 个元素，必须从头结点开始顺着指针链走 i 步，这个开销是线性的。如果硬要在链表上做折半查找，那么每一轮"取中点"都要先遍历到中点位置，整个算法的效率会退化，得不偿失。
第二个边界是元素必须有序。这个要求看起来理所当然，但它背后的逻辑值得说清楚。折半查找之所以敢每轮舍弃一半，靠的就是有序性提供的"排除依据"：一旦知道目标比中点小，那么中点右边所有元素必然都比目标大，右半区可以放心地整体丢弃。如果表是无序的，中点左边和右边的元素和目标的大小关系没有任何规律，就无法做出这种整体判断，折半查找的逻辑前提就崩塌了。
还有一个容易被忽略的边界，就是折半查找通常用于静态的查找表。所谓静态查找表，是指这个表在查找期间不进行插入和删除操作。因为折半查找依赖元素的有序性，一旦插入或删除了元素，就必须重新排序或者重新调整，维护成本很高。所以折半查找特别适合那些一次性建立、之后频繁查询而很少变动的数据，比如一个排序好的字典、一份按编号排列的客户名单这类场景。
软考命题人在出折半查找题目时，有一套成熟的挖坑手法。这些坑不是凭空捏造的，每个都对应着考生理解折半查找时最容易出现的认知偏差。把这几个坑认清楚，考场上就能少掉进一半的陷阱。
第一个坑，也是最基础的一个，就是把折半查找的前提条件张冠李戴。命题人经常在选项里构造一些似是而非的表述，比如"双向链表存储、元素有序排列""顺序存储、元素随机排列"。这两种表述各自满足了一个条件，却破坏了另一个。前者满足了有序，却破坏了顺序存储；后者满足了顺序存储，却破坏了有序。正确的答案只有一个，那就是"顺序存储且元素有序排列"。这道题几乎每年都会以某种变形出现，考察的就是考生对这两个前提是否真的记住了，而不是似懂非懂。
第二个坑，是折半查找题目里难度最高的一个，就是比较序列的合法性判断。这类题给一个有序顺序表，再给一个"查找过程中依次比较的关键字序列"，让考生判断这个序列是否可能由折半查找产生。它的本质是考察对判定树的深刻理解：在有序表确定的情况下，每次比较后目标可能的落点范围被严格限定，如果给出的序列违反了这种范围的收
本篇完！