扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找，又称二分查找，是软考软件设计师、数据库系统工程师、嵌入式系统设计师等科目中几乎每年都会出现的送分考点。它的原理本身并不复杂，理解一次就能终身受用；但命题人总喜欢在判定树、平均查找长度、取整方向这些看似不起眼的细节上挖坑。本文从概念定义讲到判定树的底层机制，再到挖坑套路和历年真题解析，把折半查找彻底讲透。
折半查找（Binary Search）是一种在有序表中进行查找的高效算法。它的正式定义可以这样表述：假设查找表采用顺序存储结构，并且表中的关键字按值有序排列，折半查找的过程就是每次取当前查找区间的中间位置元素与目标关键字进行比较，根据比较结果将查找区间缩小为原来的一半，如此反复，直到找到目标元素或者查找区间为空。
要准确理解这个定义，必须抓住两个前提条件。第一个前提是存储结构必须是顺序存储。折半查找的核心操作是"跳到中间位置去比较"，这就要求系统能够根据下标直接计算出任意元素的存储地址，也就是具备随机访问能力。顺序表天然具备这种能力，而链表不具备，因为链表只能从头结点开始逐一遍历，无法直接定位到中间结点。第二个前提是表中元素必须有序。这里的"有序"可以是升序，也可以是降序，但必须是全序关系，即任意两个元素都能比较大小。只有满足有序这个前提，比较结果才能提供"目标在左半区还是右半区"的确定性信息，从而支持区间折半。
折半查找的查找过程可以用三句话概括。第一步，确定查找区间的下界和上界，分别记为 low 和 high，初始时 low 指向第一个元素，high 指向最后一个元素。第二步，计算中间位置 mid，通常取 mid 等于 low 与 high 之和的一半并向下取整，然后比较目标关键字 key 与中间位置元素的值。第三步，根据比较结果分三种情况处理：若 key 等于中间元素，则查找成功，返回 mid；若 key 小于中间元素，说明目标只可能位于左半区，于是把 high 调整为 mid 减一；若 key 大于中间元素，说明目标只可能位于右半区，于是把 low 调整为 mid 加一。循环执行第二步和第三步，当 low 大于 high 时，说明查找区间已经为空，查找失败。
从分类角度看，折半查找属于静态查找方法。所谓静态查找，是指查找表在查找过程中不发生插入和删除操作，也就是说查找表一旦建立，其内容就固定不变。与静态查找相对的是动态查找，动态查找表允许在查找过程中插入和删除元素，因此需要配合二叉排序树、平衡二叉树等动态结构来维护。折半查找要求顺序存储且有序，而顺序存储结构插入和删除元素时需要移动大量元素，代价高昂，所以折半查找天然适合静态场景，不适合频繁增删的动态场景。这一分类界限是软考命题人常考的一个角度，考生务必分清。
折半查找之所以高效，其底层原理可以用两个关键词来概括：缩小规模和随机访问。在有序的前提下，一次比较就能排除一半的候选元素，查找范围以指数速度收缩，这是缩小规模；而顺序存储结构支持按下标直接寻址，无需逐个遍历，这是随机访问。两者结合，才成就了折半查找对数级别的时间复杂度。
折半查找的每一步都要计算中间位置 mid。最常见的写法是 mid 等于 low 加 high 除以二的整数部分，也就是向下取整。为什么向下取整如此关键？因为当区间长度为偶数时，low 与 high 之和是奇数，除以二会产生小数，必须明确取整方向，否则不同实现会产生不同的中间元素，进而导致判定树形态不同。软考题目中，凡涉及折半查找的模拟题，几乎都会默认向下取整，因此考生在做题时应默认采用向下取整规则，除非题目另有说明。
以长度为十的有序数组为例，元素下标从一到十。第一次查找时 low 等于一，high 等于十，mid 等于五，指向数组的第五个元素。如果目标大于第五个元素，区间收缩到第六到第十，此时 low 等于六，high 等于十，mid 等于八。可以看到，每次比较后区间长度大约减半，这正是"折半"二字的直观体现。理解向下取整规则后，考生就能在草稿纸上准确模拟出每一轮参与比较的元素下标，这类模拟题也就迎刃而解了。
折半查找的过程可以用一棵特殊的二叉树来描述，这棵二叉树被称为折半查找的判定树。判定树的每个内部结点对应一次成功查找，结点中存放的是参与比较的元素；判定树的外部结点，也就是空指针结点，则对应查找失败的情形。折半查找的判定树本质上是一棵二叉排序树，即对任意结点，其左子树所有结点的值都小于它，右子树所有结点的值都大于它。
判定树有一个非常优美的性质：当折半查找采用向下取整规则，并且元素个数 n 已知时，判定树是一棵深度最浅的平衡二叉树，或者说是一棵完全二叉树结构。这意味着判定树的所有叶子结点，或者出现在最底层，或者出现在倒数第二层，任何两个叶子结点的深度之差不超过一。正是这种"尽可能平衡"的结构，保证了查找路径的长度不会失控，从而保证了查找效率的对数上限。
判定树的深度决定了查找的最坏情况。对于含有 n 个元素的折半查找表，判定树的深度等于 n 加一取以二为底的对数再向上取整。这意味着查找成功的最大比较次数等于判定树的深度，也等于 n 取以二为底的对数向下取整再加一。而查找失败时的最大比较次数，对应判定树中外部结点的深度，其值等于 n 加一取以二为底的对数向上取整。这两个公式是软考计算题的核心，考生必须熟练掌握，并且要注意成功查找和失败查找的次数公式并不相同。
折半查找的时间复杂度是 O(log n)，这一点可以从判定树的深度直接推导出来。查找过程的每一次比较都沿着判定树下降一层，因此比较次数的上界就是判定树的深度。由于判定树是一棵近似满二叉树，其深度与元素个数的对数成正比，所以折半查找的时间复杂度是对数级别。这个对数级别意味着，即使查找表包含一百万条记录，折半查找也最多只需要比较二十次左右就能定位目标，效率远高于平均需要比较五十万次的顺序查找。
值得注意的是，折半查找的对数复杂度建立在一个隐含代价之上，即查找表必须事先排序。因此在静态查找场景中，折半查找的收益最明显，排序只需执行一次，之后的每次查找都能享受对数级效率。而在动态场景中，频繁插入删除会不断破坏有序性，维护有序结构的开销可能抵消折半查找的收益，这也是它不适用于动态表的根本原因。
折半查找并非万能的查找算法，它的适用场景有严格的边界条件。理解这些边界条件，不仅能帮助考生准确判断一道题该不该用折半查找，也能帮助考生在系统设计中做出正确的技术选型。
折半查找的适用前提可以归纳为两条硬性约束：顺序存储和有序排列。这两条约束缺一不可，只要有一条不满足，折半查找就无法使用。对于顺序存储，考生可以这样理解：折半查找需要随机访问，也就是通过下标直接拿到元素，链表结构无法做到这一点，因此链表上的查找只能退化为顺序查找。对于有序排列，考生可以这样理解：折半查找依赖"比较一次排除一半"的机制，这个机制成立的前提是，比较结果能够确定目标元素与当前元素的相对位置关系，而这种确定性只有有序表才能提供。
在实际工程中，折半查找最常见的应用场景是静态数据集合的高频查询。比如数据库索引的页内查找、路由表的路由前缀匹配、字典序的词汇检索等，这些场景的数据相对稳定，排序一次后可以反复查询，正好契合折半查找的特性。软考命题也常常结合这类场景出题，让考生判断某个场景是否适合折半查找，此时考生只需套用顺序存储加有序这两个条件即可作答。
为了更清晰地理解折半查找的定位，有必要将它与其他几种常见的查找方法放在一起对比。顺序查找是最朴素的查找方法，它不要求表有序，也不要求顺序存储，几乎没有任何前提条件，但代价是平均查找长度约为 n 的一半，效率最低。折半查找要求顺序存储和有序排列，但将平均查找长度压缩到对数级别，效率大幅提升。分块查找，也称索引顺序查找，是顺序查找和折半查找的折中方案，它将表分成若干块，块内无序、块间有序，查找时先用折半或顺序方法确定目标所在块，再在块内顺序查找。
从平均查找长度的角度看，三者的效率从低到高依次是顺序查找、分块查找、折半查找。软考题目常要求考生比较三者的平均查找长度或判断某句关于三者叙述的对错，考生只要记住"顺序存储加有序"是折半查找的必要条件，就能准确判断大多数题目。
折半查找既可以递归实现，也可以迭代实现。递归实现的思路是：每次比较后，如果目标在左半区，就对左半区递归调用折半查找；如果目标在右半区，就对右半区递归调用。递归实现代码简洁，直观地体现了"折半"的分治思想，但每次递归调用都会产生额外的函数调用开销，空间复杂度为对数级别。迭代实现则用循环代替递归，只需维护 low 和 high
本篇完！