折半查找，也称二分查找，是软考中级软件设计师、数据库系统工程师以及嵌入式系统设计师等科目中几乎年年必考的一道题。表面上看它只是一个简单的"每次砍一半"的查找算法，但命题人在这个知识点上挖坑的深度远超大多数考生的预期。有的考生背下了时间复杂度是O(log n)，却在计算平均查找长度ASL时屡屡算错；有的考生能默写判定树的形状，却在"比较的关键字序列是否可能"这种题型上频频失手；还有的考生分不清折半查找究竟要求"顺序存储"还是"链式存储"，也不清楚它和顺序查找、分块查找在适用场景上的边界到底在哪里。这篇文章不满足于把折半查找讲成一个会背的结论，而是从它的定义、判定树的底层结构、平均查找长度的严格推导，一直讲到历年真题的命题思路和易错点，帮助你在考场上把这道送分题稳稳拿到手。
折半查找，又称二分查找，是一种在有序顺序表中查找特定元素的高效查找方法。它的正式定义可以这样表述：对于一个采用顺序存储结构、且元素按照关键字有序排列的线性表，折半查找在每一次比较时，都选取当前查找区间中间位置的元素与目标关键字进行比较，若二者相等则查找成功，若目标关键字小于中间元素则在前半区间继续查找，若大于则在后半区间继续查找，如此反复，直到找到目标或查找区间为空为止。
这里有两个关键词必须刻进记忆。第一是"有序顺序表"，折半查找的前提是查找表中的元素已经按照关键字排好序，而且必须是顺序存储，也就是用数组这种地址连续、可以随机访问的结构来存放。第二是"区间折半"，折半查找的本质不是简单地"猜中间那个数"，而是每一次比较都严格地把待查找区间缩小为原来的一半，从而把查找范围以指数级的速度收缩下去。正是这种指数级的收缩，才让折半查找在最坏情况下也只需要对数级别的比较次数。
折半查找对存储结构有两条硬性要求。其一，查找表必须采用顺序存储结构，也就是数组。因为折半查找需要在O(1)时间内随机访问任意下标的元素，只有数组能够做到这一点。其二，表中的元素必须按照关键字有序，通常是升序排列。这两个条件缺一不可：如果一个表是链式存储的，即便元素有序，链表也无法在常数时间内跳到中间节点，折半查找就退化成了低效的线性扫描，失去了它的意义。
这个"顺序存储"的要求，恰恰是命题人最爱挖的第一个坑。很多考生在概念辨析题里看到"折半查找适用于有序链表"这样的表述时犹豫不决，正确答案是折半查找只能用于有序顺序表，不能用于链表。因为链表的中间节点需要从头遍历才能定位，即使链表有序，也无法实现真正的折半。理解这一点，就能稳拿一道选择题的分数。
此外还应当注意，折半查找要求的关键字有序，指的是查找关键字这一维度的有序。在实际的查找表中，元素可能由多个数据域组成，但只要作为查找依据的关键字域是排好序的，就满足了折半查找的前提，其余数据域是否有序并不影响算法的正确性。这个细节在概念题中也时有出现，命题人可能会用"整个记录必须有序"来迷惑考生，实际上只需查找关键字有序即可。
折半查找的完整流程可以用文字精确描述如下：首先设查找区间为[low, high]，初始时low等于1，high等于n；接着在low小于等于high的前提下，反复执行以下操作，计算中间位置mid等于low与high之和的一半并向下取整，将关键字key与第mid个元素比较，若相等则查找成功返回mid，若key小于该元素则令high等于mid减1，若key大于该元素则令low等于mid加1；当low大于high时，说明查找区间已经不存在任何元素，查找失败。这个流程虽然只有寥寥几句，却包含了折半查找的全部精髓，考生最好能够脱离书本完整复述，因为在综合题中，命题人经常用文字描述算法，让考生判断其采用的策略或计算其复杂度。
折半查找的过程，可以用一棵二叉树精确地刻画出来，这棵树就是判定树。把每一次比较的中间元素作为树的节点，比较的结果决定下一步走向左子树还是右子树，整棵判定树就完整地描述了折半查找对所有可能情况的分支结构。
判定树有几个极其重要的性质，它们直接决定了平均查找长度的计算公式。第一，判定树是一棵二叉排序树，左子树的所有关键字都小于根节点，右子树的所有关键字都大于根节点。第二，对于n个元素的折半查找，其判定树的形态是确定的，深度为⌊log₂n⌋+1，也就是说，最多比较⌊log₂n⌋+1次就能完成查找。第三，判定树中叶节点的分布有一个规律：当n较大时，判定树接近于一棵完全二叉树，叶节点最多相差一层。
判定树之所以重要，是因为平均查找长度的本质，就是从根到所有节点（成功查找）或所有外部节点（失败查找）的路径长度的加权平均。一旦把查找过程画成判定树，ASL的计算就从"背公式"变成了"数层数"，这是从机械记忆走向真正理解的分水岭。
需要特别说明的是，判定树上的成功查找对应内部节点，而失败查找对应外部节点。在一棵有n个内部节点的判定树中，外部节点的个数恰好是n加1，即失败查找的可能情况总是比成功查找多一种。这是因为n个元素把整个有序数轴分割成了n加1个区间，每个区间对应一个查找失败的情形。这个n加1的来源，正是失败查找平均比较次数的分母总是n加1的根本原因，理解了它，失败查找的ASL公式就不再需要死记。
为了把判定树看得更透彻，不妨以11个有序元素为例亲手画一遍。按照向下取整的规则，第一次比较第6个元素，它成为根节点；左半区间有5个元素，继续折半，第二次比较第3个元素，右半区间有5个元素，第二次比较第9个元素，于是第二层共有两个节点；第三层，第3个元素两侧分别折半到第1和第4个元素，第9个元素两侧分别折半到第7和第11个元素，第三层共四个节点；第四层，第1个元素的右子节点是第2个，第4个元素的左子节点是第5个，第7个元素的左子节点是第8个，第11个元素的左子节点是第10个，第四层共四个节点。这样得到的判定树共有四层，11个内部节点对应11种成功查找情形，12个外部节点对应12种失败查找情形，每层节点数一目了然，平均查找长度的计算就水到渠成了。
折半查找的每一次迭代，都维护一个闭区间[low, high]，初始时low指向表头，high指向表尾。在每一轮中，计算中间位置mid，比较A[mid]与目标关键字key的大小，然后根据比较结果收缩区间：如果key等于A[mid]则查找成功；如果key小于A[mid]则令high等于mid减1，继续在左半区间查找；如果key大于A[mid]则令low等于mid加1，继续在右半区间查找。当low大于high时，说明区间已经为空，查找失败。
mid的取值规则是这道题的第二大陷阱来源。mid可以取⌊(low+high)/2⌋，即向下取整，这是软考教材和大多数真题采用的标准做法；也可以取⌈(low+high)/2⌉，即向上取整。两种取法都能保证区间每次至少缩小一半，算法正确性不受影响，但会导致判定树的形态略有差异，进而在"查找过程中参与比较的元素序列"这类题目里产生不同的答案。考生在考场上必须紧盯题干中"向下取整"还是"向上取整"的限定，这是决定一道计算题对错的关键细节。
从算法复杂度的角度看，折半查找每经过一次比较，查找区间就缩小为原来的一半。设表长为n，那么经过k次比较后，区间长度约为n除以2的k次方。当区间长度缩小到1时查找结束，因此k约等于log₂n，这就是折半查找时间复杂度为O(log n)的严格由来。这个对数级别的时间复杂度意味着，即便表长达到一百万，折半查找也只需二十次左右的比较，而顺序查找平均需要五十万次，两者效率差距巨大。
查找算法在软考中通常以"三大基本查找"的面貌出现，分别是顺序查找、折半查找和分块查找。三者的对比是概念题的常客，必须把边界条件理清。
顺序查找，也叫线性查找，从头到尾逐个比较，不要求表有序，也不要求顺序存储，链表和数组都能用。它的平均查找长度是(n+1)/2，时间复杂度O(n)，胜在普适性强，代价是效率低。分块查找，也叫索引顺序查找，把表分成若干块，块间有序、块内可以无序，再建立一个索引表记录每块的最大关键字和起始位置。查找时先折半或顺序查找索引确定目标所在的块，再在块内顺序查找。分块查找的平均查找长度介于顺序查找和折半查找之间，适用于数据量较大、又希望插入删除比较灵活的场景。
折半查找则站在效率的另一端，时间复杂度O(log n)，平均查找长度约为log₂(n+1)-1，但代价是要求顺序存储且有序。三者的取舍，本质上是在"存储结构限制""是否有序""查找效率""插入删除灵活性"这几个维度之间的权衡，命题人往往就是围绕这几个维度出概念辨析题。
值得补充的是，折半查找虽然查找效率极高，但它的插入和删除操作代价很大，因为要保持表的有序性，每次插入或删除都可能需要移动大量元素。因此，折半查找最适合的是
本篇完！