在软考软件设计师、系统分析师乃至系统架构设计师的上午综合知识里，折半查找几乎是年年必考、年年有人丢分的经典算法考点。它不像图论里的最短路径那样公式复杂，也不像排序算法那样需要背一堆时间复杂度表，折半查找的题干往往很短，选项往往很接近，正因如此，命题人才特别容易在判定树形态、平均查找长度计算和前提条件这些细节上挖坑。很多考生凭直觉选了答案，考完对答案才发现自己栽在了最不该丢分的地方。这篇文章从算法内核出发，把判定树、平均查找长度的数学推导、成功与失败查找的区分，以及历年真题的命题套路一次性讲透，让读者看完之后稳定拿分。
折半查找，又称二分查找、对分查找，是一种在有序顺序表上进行查找的高效算法。它的教材标准定义可以概括为：设顺序表的关键字已经按由小到大或由大到小的次序排列，查找时先用给定值同中间位置元素的关键字比较，若相等则查找成功，若给定值小于中间元素则在前半区间继续查找，若大于则在后半区间继续查找，如此反复，直到区间为空而宣告查找失败。这个定义隐含了两个缺一不可的前提：其一，被查找的表必须有序，即关键字之间存在可比大小的线性次序；其二，必须采用顺序存储结构，即数组这类支持随机访问、能用下标直接定位中间元素的存储方式。
这两个前提看似简单，却是软考命题人最常用的考点来源。很多考生记住了折半查找的效率优势，却忽略了它为什么只有在顺序存储结构下才能发挥出来。原因在于，折半查找的核心动作是每一次都跳跃式地访问区间的中间元素，这种跳跃访问要求底层存储能够在常数时间内根据下标算出地址。顺序表恰好满足这一点，因为元素在内存中连续存放，第几个元素就位于基地址加下标乘以元素大小的位置。链表虽可做到逻辑有序，却只能沿指针逐个遍历，无法直达中间元素，因此在其上做折半查找就失去效率意义。这个细节在真题里反复以判断叙述正误的形式出现，稍后会在真题关联部分专门展开。
为讲清折半查找的位置，需要把它放进查找方法的谱系对比。最基础的顺序查找不要求有序，也不要求特定存储结构，从头到尾逐个比较，时间复杂度为线性。折半查找以有序为前提换来了对数级复杂度，代价是必须顺序存储且保持有序。介于两者之间的分块查找又称索引顺序查找，把表分成若干块，块间有序、块内无序，先由索引定位目标所在块，再在块内顺序查找，插入删除更灵活但查找速度不及折半查找。
这三种方法的适用边界正是命题人常放在一起考的地方：顺序查找适合元素少、无序或频繁变动的场景，折半查找适合静态、元素量大且基本不再变化的场景，分块查找适合既要一定查找效率又需频繁增删的动态表。抓住有序性、存储结构、静态还是动态三个维度，答案往往一目了然。
折半查找的算法内核可以用一句话概括：每一步都把查找范围缩小到原来的一半。设查找区间为一段连续下标，初始时区间的下界是首元素、上界是末元素。算法首先计算出当前区间的中间位置，取中间位置的元素同目标值比较。如果目标值等于中间元素，查找成功；如果目标值小于中间元素，说明目标只可能出现在中间元素的左侧，于是把上界收缩到中间位置的左边；如果目标值大于中间元素，说明目标只可能出现在右侧，于是把下界收缩到中间位置的右边。无论哪种情况，每一轮比较之后，要么立即命中，要么把待查区间的规模削减一半。当区间收缩到空，也就是下界越过了上界时，算法终止并判定查找失败。
这里藏着一个易被忽视的本质：折半查找每次比较都是一次决策，其结果把问题规模对半分割。这种思想在算法设计里称为分治策略，折半查找正是分治思想在查找问题上的典型体现——把大问题分解为规模减半的同类子问题，每次只进入其中一个子问题继续求解，从而避免穷举。每次与中间元素的比较区分小于、等于、大于三态，等于态立即终止，其余两态各把区间减半。正是这种对半削减，使比较次数与元素个数呈对数关系而非线性关系。
理解折半查找最直观的工具是判定树。判定树是一棵二叉树，树中每一个内部节点对应一次比较，也对应顺序表中的一个元素位置。根节点对应第一次比较的中间元素，其左子树对应在左半区间继续查找的所有可能过程，右子树对应在右半区间继续查找的过程。查找成功的情形恰好对应判定树的内部节点，查找失败的情形则对应判定树的外部节点，也就是把每个内部节点的空子树位置都补上一个虚拟的失败节点。由于折半查找每次都是取区间的中间位置，所以这棵判定树天然具有平衡的性质，它的左右子树高度之差不会超过一。
判定树的价值在于把抽象查找过程转化为可计算的树结构，让平均查找长度有了严格推导依据。成功查找的比较次数等于从根走到该元素对应节点经过的节点数，即该节点在树中的层数；最坏情况下的比较次数等于判定树高度，约等于以二为底元素个数加一的对数向上取整。判定树形态并不唯一，因为区间长度为偶数时中间位置可偏左也可偏右，但只要每次对半分割，高度这一数量级就保持不变。理解了判定树，平均查找长度的计算就落在结构基础上，而非死记公式。
平均查找长度是折半查找考题里分值最高、也最易算错的部分。它定义为查找过程中比较次数的数学期望，分为成功查找平均查找长度与失败查找平均查找长度两种。成功查找时假设每个元素被查找概率相等，成功平均查找长度等于判定树所有内部节点层数之和除以节点个数；失败查找时则等于所有外部节点层数之和除以外部节点个数。层数通常约定根节点为第一层，比较次数与层数一一对应。
以十一个元素为例，其判定树是一棵高度为四的平衡二叉树，根节点位于第一层，第二层有两个节点，第三层有四个节点，第四层有四个节点。成功查找时，第一层的一个元素比较一次，第二层的两个元素各比较两次，第三层的四个元素各比较三次，第四层的四个元素各比较四次，把所有节点的比较次数累加后除以十一，就得到成功平均查找长度。失败查找时，判定树对应十二个外部节点，其中一部分位于第四层，另一部分位于第五层，其平均层数构成了失败平均查找长度。真题中给出的结果，例如十元素有序表的成功查找平均比较次数为二十九除以十、失败查找平均比较次数为二十九除以十一，正是沿着这条推导路径得出的。只有亲手推演过一遍判定树的层数分布，才能在考场上对这类数字快速做出判断，而不至于被选项中接近的数值迷惑。
在实际工程中，纯粹的等值查找往往不够用，程序员更常遇到的是查找有序序列中第一个不小于某个值的位置，或最后一个不大于某个值的位置，这类问题分别称为下界查找和上界查找。它们是折半查找思想的直接延伸，也是现代标准库中许多二分接口的底层实现逻辑。下界查找在目标值与中间元素相等时并不立即终止，而是继续向左收缩，直到锁定第一个满足条件的元素；上界查找则对称地向右收缩。这两种变体解决了有序表含重复元素时返回位置不确定的问题，能精确定位重复元素的起止边界，进而得到元素个数。
这种扩展的意义在于，它把折半查找从简单的存在性判断提升为区间定位工具。软考虽然以经典等值查找为主，但理解了下界上界的收缩逻辑，有助于考生在遇到带有边界条件的查找题时举一反三。更重要的是，下界上界查找揭示了折半查找一个通用的思想：当比较结果相等时选择哪一侧继续收缩，本质上是在控制返回结果落在重复区间的哪个端点。掌握这一点，考生就不会在遇到寻找插入位置、统计某值出现次数这类变形题时感到陌生。
折半查找虽然已经是查找方法里的优等生，但它的每次对半分割并不总是最优的，因为对半分割的前提假设是目标值在整个区间内均匀分布。当数据分布已知且极不均匀时，插值查找提供了一种更聪明的选择，它不再机械地取中间位置，而是根据目标
本篇完！