折半查找，又称二分查找，是计算机领域最经典、最基础的高效查找算法之一。在软考软件设计师、系统分析师、数据库系统工程师等多个科目的选择题中，折半查找几乎年年出现，其考查形式往往不是让考生背诵算法本身，而是围绕折半查找的适用条件、查找判定树的结构、平均查找长度ASL的计算以及边界条件的陷阱设置来命题。许多考生自认为对二分查找烂熟于心，却在考试中屡屡失分，根源在于对折半查找的理解停留在"取中间、比大小、缩一半"的口诀层面，而没有真正吃透它的数据结构前提、区间收缩机制和复杂度推导过程。
折半查找的标准定义可以表述为：在按关键字有序排列的顺序存储结构中，每次将待查找区间划分为两半，取出位于区间中间位置的元素与目标关键字进行比较，若相等则查找成功并返回该位置；若目标关键字小于中间元素，则说明目标只可能落在左半区间，于是将查找范围收缩到左半部分继续执行同样的操作；若目标关键字大于中间元素，则将查找范围收缩到右半部分继续执行；如此反复，直到查找成功或者待查找区间为空，此时判定查找失败。
从这一定义出发，可以提炼出折半查找得以成立的三个严格前提。第一个前提是"有序"，即线性表中的元素必须按照关键字值从小到大（升序）或从大到小（降序）排列。有序性是折半查找赖以生存的根本条件，因为只有在有序表中，"目标比中间元素小"这个比较结果才能确定性地排除掉整个右半区间；如果表是无序的，比较结果无法提供任何关于目标位置的确定性信息，折半查找也就失去了意义。第二个前提是"顺序存储"，即线性表必须采用数组这类支持按下标随机访问的连续存储结构来实现。折半查找的关键操作是"定位到中间元素"，这一步要求能够以常数时间O(1)直接访问任意下标位置。如果线性表采用链表实现，即使链表元素本身是有序的，也无法在O(1)时间内访问到中间结点，必须先从头遍历计数才能到达中间位置，这就把折半查找退化成了一次低效的遍历，因此链表上的"二分查找"在算法意义上并不成立。第三个前提是"静态或近似静态"，折半查找适合元素基本不变、以查找为主的场景，因为一旦表发生频繁的插入或删除，维护有序性本身需要移动大量元素，代价高昂。
需要特别澄清的是，折半查找的"有序"并不等同于"升序"。教材中的标准表述多以升序为例，但降序表同样可以进行折半查找，只是比较后收缩方向与升序表相反。命题人在出题时偶尔会利用这一点制造陷阱，例如给出一个降序排列的表，却让考生按照升序的惯性思维去判断查找路径，考生稍不留意就会出错。因此，理解折半查找的核心应当是"比较结果决定搜索空间收缩的方向"，而不是死记"小的往左、大的往右"这一针对升序表的特定规则。
折半查找之所以高效，其底层机制可以归结为一句话：每一次比较都至少把搜索空间砍掉一半。假设当前查找区间为下标范围[low, high]，折半查找首先计算出区间的中间位置mid，随后将中间元素A[mid]与目标关键字key进行比较。比较结果只有三种可能：相等、小于、大于。相等则直接命中；key小于A[mid]时，目标若存在必然位于下标区间[low, mid-1]；key大于A[mid]时，目标若存在必然位于下标区间[mid+1, high]。无论哪种不相等的情况，搜索空间都从原来的high-low+1个元素缩减为最多约一半的元素，这正是"折半"二字的由来。
折半查找的正确性高度依赖于区间边界的处理方式，这也是考试中最重要的细节之一。mid的取值通常采用向下取整，即mid = (low + high) / 2，等价于(low + high) >> 1。采用向下取整意味着当区间长度为偶数时，mid指向两个中间位置中靠左的那个。循环的终止条件一般写作low <= high，即只要区间中还存在至少一个元素就继续查找；当low大于high时，说明区间已经收缩为空，查找失败。这样一个约定下，每一轮循环结束后，新的区间[low, mid-1]或[mid+1, high]严格不包含已经比较过的mid位置，保证区间长度每轮都严格递减，从而必然在有限步内收敛，不存在死循环的风险。
这里有一个常见的变体，即mid采用向上取整mid = (low + high + 1) / 2。向上取整本身在数学上同样合法，但它会改变比较路径和查找判定树的具体形态。更重要的是，在某些"查找边界"的变体算法中，mid取整方向与循环终止条件的搭配若不一致，会直接导致死循环。例如在求"第一个大于等于key的位置"这类二分查找变体中，若循环体写成mid = (low + high) / 2且更新方式为low = mid（而非mid + 1），当区间只剩两个元素且mid恰好等于low时，low不再前进，区间无法缩小，程序就会陷入无限循环。这类陷阱虽然属于算法竞赛的常见考点，但软考命题人也开始将其思想引入选择题，考生需要理解mid取整与边界更新的内在关联，而不能孤立地记忆。
折半查找的整个过程可以用一棵二叉树来精确刻画，这棵树称为折半查找的判定树。构建规则是：以第一次比较的中间元素作为判定树的根结点，中间元素左侧的区间对应根结点的左子树，右侧区间对应右子树，然后对左右子区间递归地应用同样的规则，直到子区间为空。这棵判定树的形态与有序表的长度n直接相关，而且是一棵结构相对平衡的二叉树，因为每次划分都是"尽量对半"，左右子树的高度差至多为一。
判定树的含义非常直观：树中的每一个内部结点代表一次"与表中元素比较"的操作，结点所在的层次（根为第一层）就是该元素在折半查找中被比较到时所需要的比较次数。例如，一个长度为11的升序有序表，其折半查找判定树的根结点是第6个元素（下标从1计），第一层只有根结点一个元素，它比较1次即可命中；第二层有两个元素，分别是左半区间与右半区间的中间元素，它们比较2次可以命中；第三层有四个元素，比较3次命中；第四层有四个元素，比较4次命中。由此可见，判定树把"查找某元素需要比较多少次"这个看似复杂的问题，转化为了"该元素在判定树中处于第几层"这个直观的计数问题。
判定树还有一个重要性质：它本质上是一棵二叉排序树，即树中任意结点的左子树元素都小于该结点，右子树元素都大于该结点。同时，由于折半查找总是取中间元素作为划分点，判定树还是一棵平衡二叉树，这一点保证了折半查找在最坏情况下（查找失败或查找最深层的元素）的比较次数仍然保持在对数级别，不会退化为线性级。理解判定树是理解折半查找复杂度与ASL计算的关键桥梁，考试中的许多题目正是要求考生先画出或想象出判定树，再据此计算平均查找长度。
平均查找长度（Average Search Length，简称ASL）是衡量查找算法效率的核心指标，其定义为：在查找过程中，为确定目标元素在表中的位置所需进行的关键字比较次数的期望值。对于查找成功的情形，成功平均查找长度记作ASL成功，它等于所有元素被比较到的次数之和除以元素总数。设判定树共有n个结点（即表中有n个元素），第i层有结点ci个，每个第i层结点的比较次数为i，则ASL成功 = (1×c1 + 2×c2 + 3×c3 + … + k×ck) / n，其中k为判定树的最大层数。
以长度为11的有序表为例，判定树各层结点数为：第一层1个、第二层2个、第三层4个、第四层4个，因此ASL成功 = (1×1 + 2×2 + 3×4 + 4×4) / 11 = (1 + 4 + 12 + 16) / 11 = 33 / 11 = 3。这个结果的含义是，平均而言，在这张长度为11的有序表中成功查找到一个元素需要进行3次比较。
当n足够大时，折半查找的成功平均查找长度可以近似表示为log2(n+1) - 1。这个结论可以从判定树的平衡性质推导出来：折半查找的判定树是一棵接近满二叉树的平衡树，其深度约为log2(n+1)，而成功查找的平均比较次数大致等于判定树的平均深度。相较于顺序查找的ASL成功 = (n+1)/2，折半查找在对数级与线性级之间的差距是巨大的。当n为100万时，顺序查找平均要比较约50万次，而折半查找最坏也不过约20次，这正是折半查找被广泛用于有序数据检索的根本原因。
除了成功查找，失败查找的平均查找长度ASL失败也是命题人爱考的冷门角度。失败查找对应判定树中的外部结点（也称失败结点、空结点），即那些落在叶子结点下方空指针位置上的结点。对于含n个内部结点的判定树，失败结点共有n+1个。以长度为11的有序表为例，其判定树的失败结点分布在不同层次，ASL失败需要通过把这些失败结点各自所在的层次加权求和后除以n+1来计算。命题人偶尔会让考生区分"成功ASL"与"失败ASL"的计算对象不同，二者的分母分别是n与n+1，这是极其容易混淆的细节。
查找算法在软考中是一个完整的知识家族，折半查找并非孤立存在，它与顺序查找、分块查找共同构成了线性表查找的三大基本方法。只有把三者放在一起对比，考生才能真正理解折半查找的定位、优势与边界条件。
顺序查找是最朴素、最通用的查找方法，其思想是从表的一端开始，逐个将表中的元素与目标关键字进行比较，直到找到目标或者扫描完整个表。顺序查找对表的结构没有任何要求：无论表是有序还是无序，无论是顺序存储还是链式存储，顺序查找都能正常工作，这是它最大的优点，也是它适用范围最广的根本原因。顺序查找的成功平均查找长度为(n+1)/2，失败查找则需要比较n次（或n+1次，取决于
本篇完！