折半查找，又称二分查找，是计算机科学中最经典、最基础的查找算法之一。在软考软件设计师、系统分析师以及数据库系统工程师等多个科目的综合知识考试中，折半查找几乎年年以选择题或填空的形式出现，命题人尤其偏爱考查查找过程中的比较序列、判定树结构以及平均查找长度三个维度。要准确掌握折半查找，首先必须把它的定义边界划清。
折半查找的标准定义可以表述为：在已经按关键字有序排列的顺序存储结构中，每次将待查找的记录区间一分为二，取区间中间位置的记录与目标关键字进行比较，根据比较结果确定下一步在左半区间还是右半区间继续查找，从而逐步缩小查找范围，直至查找成功或区间为空。这一定义里暗含三个不可忽略的前提条件。第一，被查找的表必须是有序的，即表中记录的关键字已经按照升序或降序排列。第二，存储结构必须是顺序存储，也就是用一段连续的地址空间存放记录，通常是数组，而不能是链表。第三，查找过程依赖随机访问能力，正是因为顺序存储带来了按下标直接定位中间元素的能力，折半查找才能以对数级的时间复杂度完成查找。
值得一提的是，折半查找的思想早在二十世纪四十年代就已成形，并被广泛应用于早期计算机的查找程序之中。如今几乎所有主流编程语言的标准库都内置了折半查找的实现，例如二分查找被封装为底层函数供上层调用，其内部实现无一例外地严格遵循"取中间位置、比较、收缩区间"这一套固定流程。这也从侧面印证了折半查找的通用性与稳定性，它是少数几个跨越数十年仍然保持教科书级地位的基础算法之一。
与顺序查找相比，折半查找的最大优势在于效率。顺序查找需要从头到尾逐个比较，最坏情况下要比较 n 次，平均情况也要比较大约 n 的一半，时间复杂度是线性的 O(n)。折半查找每次比较都能排除掉一半的候选区间，因此最坏情况下的比较次数不超过对数级别，时间复杂度为 O(log₂n)。正是这种指数级压缩查找空间的特性，使得折半查找在数据量较大的有序表场景下成为首选方案。理解这一层效率差异的根源，是后续推导平均查找长度和判定树结构的基础。
折半查找的本质是一种分治策略。分治的核心思想是把一个规模为 n 的问题，分解为若干个规模更小的子问题，分别求解后再合并结果。折半查找并不需要合并步骤，它属于分治策略中"减而治之"的一类，每次比较之后，问题规模直接从 n 缩减为大约 n 的一半，而不是像归并排序那样需要把子问题的结果再合并回来。
折半查找的具体执行过程可以拆解为以下步骤。首先设定三个指针或下标变量，low 指向查找区间的下界，初始为 1 或 0 取决于数组下标的起始约定，high 指向查找区间的上界，初始为表长 n。然后进入循环，在 low 小于等于 high 的条件下，计算中间位置 mid 等于 low 与 high 之和除以二的向下取整值，即 mid 等于 (low+high) 除以 2 的整数部分。接着比较中间位置元素与目标关键字的大小关系。如果中间元素恰好等于目标关键字，则查找成功，返回该位置；如果中间元素大于目标关键字，说明目标关键字只可能出现在左半区间，于是把 high 更新为 mid 减一；如果中间元素小于目标关键字，说明目标只可能出现在右半区间，于是把 low 更新为 mid 加一。循环结束后如果仍然没有找到，则查找失败。
这里有一个极其容易出错的细节，即 mid 的计算方式与取整方向。在向下取整的情况下，当区间长度为偶数时，中间位置会偏向左侧的那个元素。这一取整约定会直接影响判定树的形态，也会影响后续比较序列的书写。软考真题中多次出现"写出查找过程中参与比较的元素依次为哪些"这类题目，答案的正确与否完全取决于 mid 的取整规则是否贯彻始终。命题人正是抓住了考生在取整方向上含糊不清的弱点，反复设题。
折半查找的过程可以完美地映射为一棵二叉树，这棵树称为折半查找判定树。判定树的根结点是第一次比较的那个中间位置元素，左子树对应的是左半区间上继续进行折半查找的过程，右子树对应的是右半区间上继续进行折半查找的过程。判定树具有几个鲜明特征。其一，它是一棵平衡二叉树，任意结点的左右子树深度之差不超过一，这正是折半查找每次平均分割区间所带来的直接结果。其二，判定树是一棵二叉排序树，即对于任意结点，其左子树上所有结点的值都小于该结点，右子树上所有结点的值都大于该结点。其三，判定树中结点的层数恰好代表了查找该结点时所需要的比较次数，根结点在第一层，比较一次即可命中。
判定树的引入让平均查找长度的计算变得直观。一棵具有 n 个结点的判定树，其高度为 log₂n 向下取整再加一，也就是 ⌊log₂n⌋+1。这意味着查找成功的最大比较次数不超过判定树的高度，即不超过 ⌊log₂n⌋+1 次。对于查找失败的情况，失败结点对应的是判定树的外部结点，即空指针所在的位置，查找失败所需要的比较次数等于从根结点走到对应外部结点的路径长度。软考命题中关于"查找某关键字最多需要比较多少次"的题目，本质就是在问判定树的高度。
平均查找长度 ASL 是衡量查找算法效率的核心指标，分为查找成功时的平均查找长度 ASL成功 和查找失败时的平均查找长度 ASL失败 两种。对于折半查找，当查找成功时，假设每个关键字被查找的概率相等，则 ASL成功 等于判定树中所有内部结点所在层数之和除以结点总数，也就是从根到各内部结点的路径长度之和加一的总和再除以 n。当 n 足够大时，ASL成功 约等于 log₂(n+1) 减一，这个近似公式是软考选择题中高频出现的考点，考生只需记住当 n 很大时折半查找的 ASL 大约为 log₂(n+1)-1 即可。查找失败时的平均查找长度 ASL失败 也有对应公式，等于判定树外部结点所在层数之和除以外部结点总数，其量级同样与 log₂n 相当。
值得注意的是，ASL成功 的精确值并不等于简单套用近似公式。对于小规模的表，比如只有十一个元素的表，精确计算需要逐层统计各结点层数再求和平均。软考命题人常常给出一个具体的小表，要求计算精确的平均查找长度，此时考生必须老老实实画出判定树，逐层累加，而不能直接用近似公式凑答案。这也是区分死记公式与真正理解算法的一个试金石。
折半查找并不是孤立存在的算法，它与一系列基于"有序表加区间分割"思想的查找算法共同构成了一个家族。理解这些变体之间的关系，有助于在软考中应对各种辨析题。
插值查找是折半查找的一种改进，其核心差异在于中间位置的选取方式。折半查找始终固定地取区间正中间的元素，而插值查找则根据目标关键字在区间内的相对位置，用插值公式估算一个更接近目标的切分点。当表中记录的关键字在取值范围内分布比较均匀时，插值查找的平均性能优于折半查找，平均查找长度可以进一步压缩。但当关键字分布极不均匀时，插值查找可能退化为接近顺序查找的性能。软考命题中偶尔会出现插值查找的适用条件判断，考生需要抓住"关键字分布均匀"这一前提。
斐波那契查找利用斐波那契数列来构造查找区间的切分点，其思想是用斐波那契数代替折半查找中的二分之一切分，使得切分点遵循黄金分割比例。斐波那契查找同样要求表有序且顺序存储，在查找过程中只需要加减运算而无需除法，因此在某些硬件环境下具有实现优势。软考综合知识中，斐波那契查找一般作为概念辨析题出现，考查它与折半查找在切分策略上的区别，考生理解其"用黄金分割替代二分"这一核心即可。
分块查找，又称索引顺序查找，是顺序查找与折半查找思想的结合体。它先把整个表分成若干块，块内元素可以无序，但块与块之间必须有序，即前一块中任意元素的关键字都小于后一块中任意元素的关键字。查找时，先通过索引表确定目标关键字所在的块，索引表是有序的，因此确定块的过程可以用折半查找，也可以顺序扫描；找到块之后，再在块内进行顺序查找。分块查找的性能介于顺序查找与折半查找之间，平均查找长度等于块内查找与索引查找两部分之和。软考命题人常考分块查找的最优分块策略，即当块大小约等于块数，也就是每块元素个数约等于根号 n 时，分块查找的平均查找长度最小，这一结论源自对 ASL 表达式求极值。
折半查找在工程实践中应用广泛。数据库系统工程师考试中常考到，二叉排序树的查找在退化情况下性能劣化
本篇完！