扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找，又称二分查找，是软考软件设计师数据结构板块中每年必考的查找类知识点。教材对其给出的标准定义是：在有序顺序表中，先取表的中间位置的记录的关键字与给定值比较，若相等则查找成功；若给定值小于中间记录的关键字，则在表的前半部分继续查找；若给定值大于中间记录的关键字，则在表的后半部分继续查找。这一过程不断重复，直到找到目标记录，或当前查找区间为空，宣告查找失败。定义中的两个限定语必须逐字吃透：一是有序顺序表，即表的物理结构必须是顺序存储，逻辑结构必须是按关键字有序排列；二是比较对象是中间位置的记录，而不是任意位置的记录。
折半查找在查找方法体系中属于静态查找方法，与之并列的是顺序查找、分块查找和散列查找。顺序查找不需要任何前提，但平均比较次数为表长的一半量级；散列查找依赖哈希函数，理想情况下一次比较即可命中，但要付出额外存储空间的代价并处理冲突；折半查找居于两者之间，它要求数据有序且顺序存储，换来的是对数级别的查找效率。折半查找之所以能折半，不是算法有多聪明，而是有序这个前提让它能够通过一次比较排除一半候选区间。
软考命题人反复考查的一个点，就是折半查找的适用条件。第一个条件是顺序存储。折半查找在每一次迭代中都要随机访问区间中间位置的元素，顺序存储的数组支持按下标在常量时间内定位任意元素，这是折半的前提。第二个条件是关键字有序，通常默认按升序排列。两个条件缺一不可，任何一个不满足，折半查找都无法正确工作。历年真题曾经直接考查这一前提：要求该表顺序存储且元素有序排列。命题人给出的干扰项往往是把有序和顺序存储拆开，例如双向链表存储且元素有序，或者顺序存储但元素随机排列，前者缺少随机访问能力，后者缺少有序这个比较依据，都属于典型的错误表述。
从更宏观的视角看，查找表可以组织成线性表、树表和散列表三种形态。线性表形态下，数据按顺序或链式存放，查找只能逐个比较或折半排除；树表形态把数据组织成二叉排序树或平衡二叉树，查找过程沿树的路径下行；散列表形态通过哈希函数直接计算存储位置。折半查找属于线性表形态下的最优查找方案，它的判定过程与二叉排序树天然对应，后文判定树部分会详细展开。理解了折半查找在体系中的位置，就能明白软考为什么总是把它和排序、二叉树放在同一个综合题里考查：这三者共享同一套有序化的底层逻辑。
折半查找的底层原理是分治策略。每一次与中间元素比较后，无论比较结果是大于、小于还是等于，都能立刻把查找范围收缩到原区间的一半：相等则命中，大于则在右半区间继续，小于则在左半区间继续。这里的本质在于，有序序列中每个元素的位置都携带大小信息，中间元素像一道分水岭，把区间劈成互不重叠的两段，目标值要么在左边，要么在右边，要么恰好就在分水岭上。正是因为每次比较获得的信息量恒定，查找区间才以二的指数速度收缩，经过至多对数级别次数的比较，区间长度收缩到一，查找必然终止。
区间收缩的实现细节值得深入。算法维护两个指针，下界和上界，初始时分别指向表的第一个和最后一个元素，中间位置由下界和上界相加除以二得到。比较完成后，若目标值小于中间元素，上界收缩到中间位置减一；若大于，下界扩张到中间位置加一。这减一加一的动作是算法正确性的关键，因为中间元素已参与过比较且不相等，必须从下一轮候选区间中剔除，否则区间长度收缩到二时会出现下界始终无法越过上界的情况，算法陷入死循环。这个细节软考不直接考，但它是理解查找过程模拟题的钥匙。
折半查找的完整过程可以用一棵判定树来描述。判定树的构造规则是：把当前区间中间位置的元素作为树的根，左半区间的中间元素作为根的左孩子，右半区间的中间元素作为根的右孩子，递归构造直到区间为空。这样得到的判定树是一棵结构确定的二叉树，树中每个内部结点对应一次成功查找的比较对象，每个外部结点对应一个查找失败的区间。判定树的形状完全由表长决定，与表中元素的具体数值无关，例如十一个元素的判定树，根结点对应第六个元素，第二层对应第三个和第九个元素，依此类推。判定树的高度就是折半查找的最坏比较次数，树中结点所在的层数就是该元素被找到时需要的比较次数，这一对应关系是计算平均查找长度的全部依据。
以十个元素为例，根结点对应第五个元素，各元素所在层数分别为一、二、二、三、三、三、三、四、四、四，比较次数总和为二十九，平均成功查找约二点九次。查找失败对应判定树的外部结点，十个元素共有十一个失败区间，每个失败区间的比较次数为外部结点层数减一，总和三十九，平均失败查找为十一分之三十九。这套计算流程软考连续多年以真题形式考查，是必须练到条件反射程度的得分点。
折半查找的中间位置在实现上有向下取整和向上取整两种约定。取整方向不同，判定树的形态就不同，某些结点所在的层数也会变化，但两者都有一个共同的结论：成功查找的平均比较次数不受取整约定影响。这一点可以用判定树的结构性质解释：无论取整方向如何，判定树的叶子结点层数相差至多为一，即判定树始终近似满二叉树，因而平均比较次数的总量保持稳定。工程实现中通常采用向下取整的写法，也就是下界加上界之和右移一位，因为位运算比除法更快；软考真题的模拟计算题也普遍默认向下取整，考生在推导比较序列时必须先看清题目有没有标注取整约定，没有标注就按向下取整处理。
另一个与取整相关的考点是最坏比较次数的计算公式。判定树高度为下取整的对数值加一，也就是说，最坏比较次数不超过以二为底表长加一的对数再向上取整，该题在真题中以计算填空形式出现过。考生只要记住表长为二的幂次时最坏比较次数恰好等于幂指数加一，就能快速验证答案。
不少考生疑惑：有序链表同样是按关键字有序排列，为什么不能做折半查找。答案指向顺序存储这个前提。链表的元素通过指针链接，物理上分散在内存各处，要访问中间位置的元素，必须从头结点开始逐一遍历，定位一次中间元素的时间代价与表长成正比。折半查找的每次迭代都要定位中间元素，若采用链表存储，单是定位中间元素的总开销就退化到平方级别，完全抵消了折半的收益。更深层的原因是，折半查找依赖下标计算实现随机访问，而下标计算的前提是元素在物理地址上连续分布，这正是顺序存储的定义。这个知识点常被包装成概念辨析题。
软考教材中的折半查找是最朴素的形式：在一个元素互异的有序表中查找是否存在目标值。工程实践中的需求远比这复杂，由此衍生出一系列变体。第一类变体是查找第一个等于目标值的元素，当表中存在重复元素时，朴素算法命中任意一个即可，而变体要求定位最左边的那一个，实现方式是在比较相等时不立即返回，而是继续向左收缩上界，直到区间收敛。第二类变体是查找最后一个等于目标值的元素，与之对称，比较相等时向右推进下界。第三类变体是查找第一个大于等于目标值的位置，也就是常说的下界查找，这是所有变体中最常用的一个。第四类变体是查找第一个大于目标值的位置，称为上界查找。上下界查找的核心意义在于，即使目标值不存在于表中，也能返回目标值应该被插入的位置，从而把查找和插入两个操作统一起来。
上述变体的边界条件比朴素算法严格得多。以查找第一个等于为例，当区间长度收缩到二时，若两个元素都与目标值相等，必须保证返回的是靠左的那个，这就要求循环终止条件写成下界小于上界而非小于等于，否则会错过区间收敛的最后一轮判断。软考尚未深入考查变体实现细节，但掌握变体思想对理解区间收缩逻辑大有裨益，比较序列模拟题本质上就是在跟踪上下界的变化过程。
把朴素折半查找与三类变体放在一起观察，可以发现它们共享同一个框架：维护一个区间，每次比较后要么收缩区间，要么记录当前候选答案。区别仅仅在于相等时如何处理，朴素算法相等即返回，找第一个相等的在相等时收缩右边界，找最后一个相等的在相等时收缩左边界，下界查找把大于等于的情况都记录为候选答案并收缩右边界。理解了这个统一框架，四类变体就不再是四套需要死记的代码，而是一个模板上的四种参数配置。这个框架揭示了折半查找真正的威力：不仅能回答在不在，还能回答应该在哪，后者正是众多数据结构的底层依赖。
折半查找还有两个理论上的近亲，即插值查找和斐波那契查找，软考偶尔在概念题中捎带考查。插值查找根据目
本篇完！