折半查找，英文名称为二分查找，又称对半查找或二分搜索，是一种建立在有序顺序表之上的高效查找算法。它在计算机科学教材中的标准定义可以表述为：折半查找是在顺序存储且元素按关键字有序排列的线性表中，每次将待查关键字与查找区间中间位置的元素进行比较，根据比较结果将查找区间缩小一半，反复进行直至查找成功或区间为空的一种查找方法。这个定义虽然只有短短一句话，却包含了折半查找得以成立的三个刚性前提，缺一不可：第一，被查找的线性表必须采用顺序存储结构，也就是元素在物理存储空间上连续存放，能够凭借下标在常数时间内随机访问任意位置元素；第二，表中的元素必须按照关键字有序排列，通常是升序排列，也可以是降序排列，但绝不允许无序；第三，查找过程中需要能够直接比较关键字的大小关系，这要求关键字的类型具备可比较性，能够进行等于、大于、小于的判断。
在算法设计与分析的知识体系中，折半查找的时间复杂度为对数级别，精确地说是 O(log₂n)，其中 n 是表中元素的个数。这个对数时间复杂度的含义是，当表中有 n 个元素时，折半查找在最坏情况下需要的比较次数不超过 log₂n 的向上取整值。举例而言，一个含有一百万个元素的顺序表，顺序查找最坏需要比较一百万次，而折半查找最多只需要比较二十次左右，因为二的二十次方约等于一百万。这种从线性到对数的巨大跨越，正是折半查找被视为经典高效算法的根本原因。与此同时，折半查找的空间复杂度为 O(1)，因为它只需要维护若干个游标变量，并不需要额外的辅助存储空间，是一种典型的原地算法。
从算法思想的角度看，折半查找是分治策略在查找问题上的直接体现。分治策略的核心思想是把一个规模较大的问题，分解为若干个规模较小的、结构相同的子问题，分别求解后再综合结果。折半查找的每一轮比较，实际上都是把"在 n 个元素中查找"这个规模为 n 的问题，缩减为"在 n/2 个元素中查找"这个规模减半的子问题，而且子问题与原问题的结构完全一致，只是在更小的区间上重复相同的比较逻辑。这种"每步减半"的特性，决定了折半查找天然具备对数级别的效率。值得强调的是，折半查找虽然采用了分治思想，但它与归并排序、快速排序这类典型的分治算法有一个显著区别：折半查找在每一层递归中只进入一个子区间，而排序类算法通常需要同时处理两个子区间。因此折半查找的分治是"单向收敛"的，其递归深度就是查找的判定树深度。
在软考软件设计师的考纲中，折半查找归属于"数据结构和算法"这一模块下的查找算法专题，与顺序查找、分块查找、哈希查找共同构成查找这一章的四大经典算法。考试对折半查找的考查往往不以复杂代码写作为主，而是聚焦于三个层面：一是折半查找的适用前提，即"顺序存储加有序"这两个条件缺一不可；二是折半查找的判定树结构以及由此推导出的平均查找长度 ASL 计算；三是折半查找过程中的比较次数、中间位置取整方向等细节陷阱。这三个层面恰好对应了历年真题反复出现的命题角度，考生只要把概念定义吃透，就能在这类送分题上稳稳拿分。
折半查找的运行过程，可以用一棵二叉判定树来精确刻画。所谓判定树，是指把查找过程中每一次比较操作都抽象为一个树结点，把比较结果引出的两种走向抽象为左右子树，从而得到的一棵二叉树。这棵判定树忠实地记录了折半查找的所有可能执行路径，是理解折半查找效率、计算平均查找长度的核心工具。对于一个含有 n 个元素的升序有序表，判定树的根结点对应第一次比较的中间位置元素，其左子树对应表的前半部分，右子树对应表的后半部分，如此递归展开，直到每个子区间只含有一个元素为止。判定树中每一个内部结点都对应一个实际存在的表元素，而每一个空指针位置则对应一个"查找失败"的外部结点。
判定树中的失败结点，也称外部结点，并不对应表中的真实元素，而是对应"查找失败"这一结果，在图中通常以空结点或方框表示。一棵含有 n 个内部结点的判定树，其失败结点总数恒为 n 加一，这一性质为失败查找平均比较次数的计算提供了确定的分母。判定树的形态取决于中间位置的计算规则。在标准的向下取整规则下，中间位置取值为 mid 等于区间下界与上界之和除以二再向下取整，也就是 mid 等于下界加上上界之差的一半向下取整。采用向下取整规则时，判定树的左子树结点数总是不少于右子树，或者说左子树至多比右子树多一个结点。正是这个看似微小的取整方向差异，决定了一棵判定树的具体形状，进而影响到成功查找和失败查找的平均比较次数。软考真题中凡是涉及判定树结构或 ASL 计算的题目，其正确答案都是基于向下取整这一默认规则推导出来的，考生切不可擅自改用向上取整。
判定树还有一个重要性质，那就是对于含有 n 个元素的有序表，其判定树的高度等于 log₂n 向上取整加一。这个性质直接给出了折半查找最坏情况下比较次数的上界。例如一个含十个元素的有序表，判定树的高度为四层，最坏情况下查找失败需要比较四次。判定树本质上是一棵接近完全二叉树的结构，它尽量保持平衡，这正是折半查找能够达到对数时间复杂度的结构保证。理解判定树的构建规则，是后面推导平均查找长度的必要铺垫，也是应对"判定树有几层""第几层有几个结点"这类题目的一把钥匙。
折半查找的代码实现虽然简洁，但其中蕴含的循环不变式与边界条件却是极易出错的地方。循环不变式是指在每一轮循环开始之前都保持成立的一个逻辑断言。对于折半查找而言，这个断言可以表述为：如果目标关键字存在于表中，那么它必然位于当前的查找区间之内。初始时，查找区间是整个表，断言显然成立；每一轮比较之后，根据目标值与中间元素的大小关系，把查找区间收缩到必然包含目标的那一半，断言在下一轮仍然成立；当查找区间为空时，断言就意味着目标不存在，此时查找以失败告终。这个循环不变式为折半查找的正确性提供了严格的逻辑支撑。
边界条件的具体表现，集中在循环终止条件的写法和中间位置的取整方向上。循环终止条件通常写作 low 小于等于 high，其中 low 和 high 分别是查找区间的左右端点下标。当 low 大于 high 时，区间为空，表示查找失败。如果在实现中误写为 low 小于 high，就会在区间只剩一个元素时提前退出循环，导致漏查最后一个元素，这是初学者最常见的错误之一。中间位置的取整方向同样关键，若采用向下取整，则中间位置偏向左端点；若采用向上取整，则偏向右端点。两种取整方向都正确，但必须在同一个算法的所有环节保持一致的取整约定，否则会破坏判定树的结构对称性，进而导致漏查或死循环。
从底层机制看，折半查找每一轮只进行一次关键字比较，这与判定树"每个内部结点一次比较"的结构一一对应。比较结果只有三种可能：等于、小于、大于。等于则立即返回命中；小于则把查找区间调整为中间位置的左半部分；大于则调整为右半部分。这个"三分走两路"的机制，正是折半查找得以每轮减半的根本原因。值得一提的是，在实际工程实现中，计算中间位置时应优先使用下界加区间长度一半的写法，而不是下界加上界之和除以二，因为后者在上下界数值都很大时可能发生整数溢出，这是一个笔试之外但同样重要的工程细节。
折半查找的适用边界，全部体现在它那两个刚性前提上。第一个前提是顺序存储结构，也就是要求表元素在物理上连续存放，支持通过下标直接定位。这个前提排除了链表。链表虽然逻辑上也是线性表，但链表的元素在物理上离散分布，只能通过指针依次遍历，无法在常数时间内定位中间位置的元素，因此链表即便元素有序，也无法进行折半查找。这是一个高频考点，命题人常在选项中把"链表存储且有序"伪装成折半查找的适用对象，诱使考生误选。第二个前提是元素有序。如果表采用顺序存储但元素无序，折半查找的"每次减半"逻辑就失去了正确性保证，比较结果无法可靠地排除一半元素，查找可能错过目标。
从效率对比的角度看，当表规模 n 较小时，折半查找相对顺序查找的优势并不明显，甚至因为取中间位置的额外运算开销而显得繁琐；只有当 n 足够大时，对数时间复杂度的优势才会充分显现，这也是算法分析中"渐进复杂度"思想的一个直观印证。两个前提组合起来，可以得出一个清晰的
本篇完！