扫码获取 VIP 码
添加管理员微信获取 VIP 码
折半查找，也就是考生常说的二分查找，是软考软件设计师与数据库系统工程师两个科目几乎年年都会触碰的考点。它在考纲里归属数据结构与算法基础这一章，表面上看只是一个"从有序表里找数"的朴素方法，实际上命题人围绕它挖出的坑却相当密集：算法设计策略到底算分治还是贪心，成功查找与失败查找的平均比较次数该怎么数，判定树到底怎么画，时间复杂度为什么是对数级。很多考生背下了"前提必须有序"这句话，却在平均比较次数的计算题上一而再地栽跟头。这篇文章不打算停留在"二分就是不断砍半"这种类比层面，而是要把折半查找的底层机制、判定树结构、平均比较次数的推导过程以及命题人的命题套路全部拆开讲透，让你看完之后面对这一类题目不再靠蒙。
折半查找的正式定义可以这样表述：折半查找又称二分查找，是一种在有序的顺序存储结构中进行的查找方法，它的基本操作是将给定值与有序表的中间位置记录的关键字进行比较，若相等则查找成功，若不相等则根据比较结果缩小查找区间，在表的前半部分或后半部分继续进行同样的比较，直到找到目标记录或者查找区间为空为止。这个定义里有几个关键限定词必须逐字吃透，因为每一个限定词背后都藏着命题人喜欢出的干扰项。
第一个限定词是"有序"。折半查找能够成立的根本前提，是查找表的记录必须按照关键字的值从小到大或从大到小排好序。如果表是无序的，折半查找赖以运行的"中间元素划分"就失去了语义依据，你无法通过一次比较来判断目标值落在前半还是后半，算法随即失效。这一点与顺序查找形成鲜明对照：顺序查找对表的次序没有任何要求，无论是顺序表还是链表、有序还是无序，顺序查找都能工作，代价是平均需要扫描大约一半的记录。
第二个限定词是"顺序存储结构"。折半查找要求查找表必须用数组这类支持随机访问的存储结构来组织，因为算法在每一步都要直接定位到区间的中间下标，也就是用下标运算一步跳转到目标位置。如果查找表是链表这种只能顺序访问的结构，即使元素已经排好序，你也没有办法在常数时间内取到中间元素，折半查找的优势就会荡然无存。这个限定是很多考生忽略的：他们记住了"有序"这个前提，却忘了"顺序存储"同样是硬性条件。所以正确的表述应当是"有序的顺序表"，而不是笼统的"有序表"，命题人恰恰爱在这一点上设置语义陷阱。
第三个限定词是"比较并缩小区间"。折半查找的每一步只做一次关键字的比较，然后根据比较结果把查找区间缩小到原来的一半，这正是它时间效率高的来源。每一次比较都能排除掉一半的候选记录，因此查找的路径在判定树上表现为一条从根到叶（或到某个内部节点）的路径，路径长度与表长度的对数成正比。
从算法设计策略的角度看，折半查找采用的是一种典型的分治思想，但这里的"分治"有一个容易被误解的细节：折半查找并不是把问题分成两个子问题都去求解，而是把问题规模减半之后只求解其中一个子问题。严格来说，这属于减治法的范畴，减治法可以看作分治法的一种特殊形式。不过软考的官方表述通常把折半查找归入分治策略，历年真题的标准答案也是"分治"，考生在答题时应当以教材和真题答案为准，不要因为自己了解到"减治"这个更精细的说法而选了别的选项。
要真正理解折半查找，必须掌握一个核心工具，那就是判定树。判定树是描述折半查找比较过程的一棵二叉树，它把查找过程中每一次比较的走向直观地画出来，是解答平均比较次数一类计算题的唯一可靠依据。下面我们把这个工具彻底讲清楚。
折半查找判定树的构造遵循一条铁律：对于长度为 n 的有序表，第一次比较的对象一定是表的中间位置元素，也就是下标为下取整结果的那个元素。假设有序表的下标从 0 到 n 减 1，那么第一次比较的下标就是 0 加 n 减 1 的差值再除以 2 并向下取整，也就是中间偏左的那个位置。这个中间元素成为判定树的根节点。
根节点确定之后，查找区间被切成两半：比根小的所有元素进入左子树，比根大的所有元素进入右子树。对左半边区间和右半边区间分别重复同样的取中间操作，就得到了根的左孩子和右孩子。如此递归下去，直到每个区间都只剩下一个元素或者为空。最终得到的这棵二叉树，就是折半查找的判定树。
这里有一个非常关键的规律需要记住：判定树的形态是由元素个数 n 唯一决定的，与元素的具体取值无关。也就是说，只要有序表里元素的个数相同，无论这些元素是 3、14、27 还是 99、100、101，判定树的形状都是一模一样的。元素的具体值只决定判定树上每个节点里写什么数，不改变树的结构。理解这一点很重要，因为计算平均比较次数时我们只关心判定树的结构，也就是每个节点在第几层，而完全不用理会节点上具体是什么值。
判定树还有一个重要性质：它是一个比较平衡的二叉树，任意两个叶子节点的深度之差不会超过 1。这是因为折半查找每次都是从区间正中间切分，左右子树的规模最多相差一个元素，因此整棵树天然接近满二叉树。这种接近满二叉树的形态，正是折半查找对数级时间复杂度的直观来源。
折半查找的判定树可以区分为内部节点和外部节点两类。内部节点对应查找表中的真实元素，也就是可能"查找成功"的情况；外部节点对应查找区间为空的位置，也就是可能"查找失败"的情况。对于一棵拥有 n 个内部节点的判定树，外部节点恰好有 n 加 1 个，这个规律与"n 个元素有 n 加 1 个插入空隙"是一致的。
成功查找的比较次数，等于目标元素在判定树中所处节点的深度，也就是从根节点走到该节点所经历的节点个数。例如根节点上的元素只需要比较 1 次就能找到，第二层的元素需要比较 2 次，以此类推。失败查找的比较次数，等于从根节点走到对应外部节点之前所经过的内部节点个数，直观地说，就是查找过程一路比较下来，直到发现区间已经为空所耗费的比较次数。
这里要特别澄清一个容易算错的点：失败查找的比较次数通常比它所在位置的"深度"少 1。以一棵三层深的判定树为例，如果某个外部节点挂在第二层内部节点的下面，那么查找该失败位置的比较次数是 2 次，而不是 3 次。很多考生把外部节点的深度直接当成比较次数，结果在计算失败查找的平均比较次数时多算了。这个细节正是 2022 年下半年那道真题的难点所在，稍后我们会专门展开。
折半查找每次比较都把查找区间缩小为原来的一半，经过 k 次比较之后，查找区间的长度大约缩小为 n 除以 2 的 k 次方。当区间长度缩小到 1 甚至 0 的时候，查找过程终止。因此最坏情况下需要的比较次数 k，满足 2 的 k 次方约等于 n，也就是 k 约等于以 2 为底的 n 的对数。所以折半查找的时间复杂度为对数级，最坏和平均情况下的比较次数都在这个量级。
相比之下，顺序查找的时间复杂度是线性级，最坏情况下需要比较 n 次。当 n 很大时，对数级和线性级的差距是数量级的：一个含一百万条记录的有序表，折半查找最多比较大约二十次就能定位，而顺序查找平均要比较五十万次。这就是为什么在数据量大且查找频繁的场景下，维护一个有序顺序表并采用折半查找是极具价值的。当然，这种效率不是没有代价的，代价就是必须保证表有序，而维持有序本身可能需要额外的排序开销，这也就引出了折半查找适用边界的讨论。
折半查找并不是一个"放之四海而皆准"的方法，它有清晰的使用边界。理解这些边界，既是为了答对选择题，也是为了在真实的工程决策中做出正确判断。
第一个前提是查找表必须有序，关键字要么严格递增、要么严格递减。若表中有重复元素，一般约定仍然可以运行，但命中的是哪一个重复元素取决于具体实现，考生在考试中通常默认元素不重复，无需纠结。
第二个前提是查找表必须采用顺序存储结构，也就是数组。链表即使有序也无法高效折半，因为取中间元素需要从头遍历，省下的比较次数会被寻址开销吃掉。这一条在软考中常以"折半查找适用于哪种存储结构"的形式出现，正确答案是顺序存储的有序表，而不是链表。
第三个前提是查找表应当是静态的，或者说在查找期间不发生频繁的插入和删除。折半查找建立在数组下标随机访问之上，一旦频繁插入或删除元素，为了维持有序性就需要移动大量元素，维护成本会急剧上升。因此在元素频繁变动的场景下，二叉排序树或平衡二叉树往往是更好的选择，它们能够在动态变化中维持较好的查找性能。理解这一点，有助于把折半查找与二叉排序树两个考点关联起来，这是命题人喜欢放在一起辨析的内容。
从平均比较次数看，顺序查找成功查找的平均比较次数约为 n 加 1 再除以 2，是线性量级；折半查找成功查找的平均比较次数约为对数级。对于较小的 n，两者的差距不明显，甚至顺序查找因为实现简单、无需有序前提而在常数上占优；但当 n 增大到一定程度，折半查找的优势会迅速显现。软考的计算题通常不会要求你精确算
本篇完！