扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找，又称二分查找，是数据结构与算法中静态查找表部分的三大查找方法之一。在软件设计师上午题里，它与顺序查找、分块查找并列为几乎每年必考的知识点。教材给出的标准定义是：折半查找是一种在有序顺序表上进行的查找方法，其基本思想是先令查找表中间位置记录的关键字与给定值比较，若相等则查找成功；若不等，则根据比较结果把查找区间缩小到前半部分或后半部分，如此反复，直到查找成功，或者查找区间为空、查找失败为止。这段定义看似简单，但每一句话都对应着一个命题点，稍后逐一拆开。
要真正理解折半查找，必须先回到一个更根本的问题：查找到底在优化什么。顺序查找是最朴素的查找方式，它从表的一端开始，逐个记录与给定值比较，找到则返回，找不到则从头到尾比较一遍。顺序查找的时间复杂度是线性的，最坏情况下要比较 n 次。折半查找之所以能把这个代价压到对数级别，靠的是牺牲一种自由——它要求查找表必须先排好序，并且必须采用顺序存储结构。换句话说，折半查找是用"有序"这个前置代价，换取了"每次排除一半"的搜索效率。理解了这个权衡，就理解了折半查找在整个查找算法谱系中的位置。
折半查找的适用有两个硬性前提，缺一不可，而这两个前提本身就是命题人反复考查的对象。
第一个前提是关键字必须有序。查找表中的记录必须已经按关键字递增或者递减排列。这里的"有序"是相对关键字的，不是相对物理存储顺序的某种抽象约定，而是要求任意相邻两个记录的关键字都满足确定的比较关系。一旦表无序，折半查找的"折半"就失去了依据，因为你无法从中间元素的比较结果推断目标元素落在哪一半。
第二个前提是必须采用顺序存储结构。折半查找依赖下标运算来确定中间位置，也就是随机访问。只有用数组这种顺序结构存储，才能用常数时间拿到任意位置的元素。链表虽然可以逻辑有序，但链式存储只能顺序访问，无法用下标直接跳到中间节点，因此链表不能支持折半查找。这一点在概念题里经常以"链表上能否做折半查找"的形式出现，标准答案是：不能，因为折半查找要求随机访问，而链表只能顺序访问。
把折半查找放进查找方法的整体框架里，能更清楚地看清它的边界。顺序查找对表结构没有任何要求，记录有序无序、顺序存储还是链式存储都能用，代价是平均比较次数约为表长的一半，效率偏低但适应面最广。折半查找正好相反，它对表有严格的有序和顺序存储要求，换来对数级的查找效率。分块查找则介于二者之间，它把表分成若干块，块内可以无序、块间必须有序，再建一张有序的索引表，先查索引定位块、再在块内顺序查找，性能介于顺序查找和折半查找之间。三者的这个"效率—约束"的递进关系，是概念辨析题的高频考点，考生必须能在一句话里说清每种方法牺牲了什么、换来了什么。
从算法思想的发展脉络看，折半查找属于典型的减治思想：它不是把问题划分成多个子问题分别求解，而是每一步都把待解规模减半，只保留可能包含答案的那一半。这种"排除法"的思想与日常的猜数游戏同源——在从一到一百之间猜一个数，每次都猜中点，最多七次就能确定答案。但折半查找的意义远不止于一个猜数技巧，它是后续理解平衡查找树、数据库索引乃至各种基于单调性的二分算法的基础。软件设计师考试之所以年年考它，正是因为它的机制简单、边界清晰、计算规范，能够稳定地测量考生对"算法细节"的把握程度。
折半查找的运行机制，本质上是维护一个不断收缩的查找区间，而这个区间由两个边界下标和它们的中点共同刻画。理解了区间收缩的精确规则，就理解了折半查找的全部运算细节，也理解了为什么它会有对数级的复杂度。
折半查找在实现上维护三个关键下标。low 指向当前查找区间的下界，high 指向上界，mid 指向区间的中点。设查找表的元素存储在一维数组中，下标从 low 到 high，那么中点 mid 的计算规则是取 low 与 high 之和的一半并向下取整。查找的每一轮，都先把给定值与 mid 位置记录的关键字比较，三种结果对应三种动作：若相等，查找成功，返回 mid；若给定值小于 mid 处的关键字，说明目标元素只可能落在前半区，于是把 high 更新为 mid 减一；若给定值大于 mid 处的关键字，说明目标元素只可能落在后半区，于是把 low 更新为 mid 加一。然后进入下一轮，重复同样的比较。
这里有一个极易被忽视、却直接决定算法正确性的细节：更新边界时必须是 mid 加一或 mid 减一，而不是直接把 low 或 high 赋值为 mid。原因在于，mid 这个位置刚刚已经和给定值比较过且不相等，它不可能再是目标位置，若不把它排除出区间，当区间收缩到只剩两个元素时就会陷入死循环。命题人在代码补全题里，最喜欢在 low 和 high 的更新处设空，考查考生是否记得加一减一这个细节。
整个循环的终止条件也值得深究。折半查找的循环条件是 low 小于等于 high，当 low 大于 high 时区间为空，表示查找失败。为什么是小于等于而不是小于？因为当 low 与 high 相等时，区间内还有一个待查元素，它完全可能就是目标，若此时就退出循环，就会漏掉这个元素。这个边界条件的精确把握，是手算模拟和代码填空共同的基础。
mid 的计算涉及取整，而取整方式的统一性是折半查找最容易踩的坑之一。教材默认的做法是向下取整，即 mid 等于 low 加 high 之和除以二的整数部分。关键结论是：在一棵判定树、一次查找过程中，取整方式必须前后统一，要么全部向下取整，要么全部向上取整，绝不能混用。因为取整方向决定了中点落在左半区还是右半区，一旦中途变换，判定的路径就会错乱，导致推导出的比较序列与实际不符。软考的惯例是向下取整，除非题干特别注明，否则一律按向下取整来推导。
从复杂度的角度看，折半查找每比较一次，查找区间就至少缩小一半。长度为 n 的表，经过第一次比较后区间不超过 n 的一半，第二次比较后不超过四分之一，依此类推，最多经过约以二为底 n 的对数次比较，区间就会收缩到只有一个元素或为空。因此折半查找的平均时间复杂度和最坏时间复杂度都是对数级的，远优于顺序查找的线性复杂度。这种"每次砍一半"的收敛方式，正是它高效的根源，也是它与顺序查找最本质的差别。
为了把上述机制落到实处，不妨手动模拟一个具体过程。设有序表为十五、十八、二十三、二十六、三十一、四十、六十五、九十一，共八个元素，下标从零到七，要查找关键字二十六。第一轮，low 为零，high 为七，mid 等于三，取到二十六，恰好命中，一轮成功。若要查找关键字六十五，第一轮 mid 为三取到二十六，六十五大于二十六，于是 low 更新为四；第二轮 low 为四、high 为七，mid 等于五，取到四十，六十五大于四十，low 更新为六；第三轮 low 为六、high 为七，mid 等于六，取到六十五，命中。可见查找六十五经历三次比较，路径依次为二十六、四十、六十五。若查找一个不存在的关键字，比如五十，则会在第二轮之后 low 越过 high，区间为空而失败。这个例子同时说明两件事：一是比较序列必须严格沿着半区方向推进，二是查找失败同样要一路比较到区间耗尽，而非提前终止。考生在考场上遇到比较序列题，用这套"区间标注法"在草稿纸上逐轮写出 low、high、mid 三个值，比任何死记硬背都可靠。
折半查找的概念和原理掌握之后，能不能拿到分，关键在会不会算。软考对折半查找的考查，一大半集中在两件事上：判定树的构造，以及平均查找长度 ASL 的计算。这两件事都建立在同一个工具——折半查找判定树——之上。
折半查找的每一次比较，都可以用一棵二叉树来刻画，这棵树称为折半查找判定树。构造方法是递归的：以当前查找区间的中间位置作为根节点，中间位置左边的子表递归地构造成左子树，右边的子表构造成右子树。根节点的左子区间里所有元素都小于根，右子区间里所有元素都大于根，因此这棵判定树天然是一棵二叉排序树，它的中序遍历恰好就是有序表原来的排列顺序。这个性质是判断某棵树是否为合法判定树的重要依据。
判定树上的每一个内部节点对应一次"比较成功"的情形，节点所在的层数就是查到该元素所需的比较次数。把每个内部节点的空指针
本篇完！