折半查找（二分查找）

2026 大纲 六（四）折半查找法。

两个前提，各封杀了一类结构

折半查找每比较一次就断言"目标只可能在左半边"或"只可能在右半边"，一刀砍掉一半候选。能这么断言，靠的是两个前提，缺一不可：

前提一：表必须有序。 唯一依据是"左半边全部小于 $a[mid]$、右半边全部大于 $a[mid]$"。表无序时这条断言不成立，被丢掉的那一半里可能就藏着目标。所以无序数组不能折半查找——哪怕它支持随机访问。

前提二：必须顺序存储。 折半要在 $O(1)$ 时间内取到 $a[mid]$。链表不支持随机访问，定位第 $mid$ 个结点要从头走 $mid$ 步。把这个代价算进去，一次查找的总代价变成

$$\underset{\text{比较次数}}{\underbrace{O(\log n)}}\times \underset{\text{每次定位 mid}}{\underbrace{O(n)}}=O(n\log n)$$

比直接顺序扫一遍的 $O(n)$ 还慢。所以有序链表不能折半查找——不是"不允许"，是这么做没有意义。

🔴 静态链表也不行，这一条最容易漏。 静态链表是用数组模拟的链表，结点确实住在数组里，但邻接关系靠 next 字段维护，物理下标连续 ≠ 逻辑顺序连续。有序静态链表里逻辑上的第 1 个元素可能在下标 7、第 2 个在下标 2，要取"逻辑上的中间元素"必须从首结点沿 next 走 $\lfloor n/2\rfloor$ 步，不能直接 arr[mid]。"数组实现的"不等于"能随机存取的"。

由这两条还顺带得到一个结论：折半查找不适用于动态查找表。顺序有序表插一个元素平均要移动一半元素，$O(n)$ 的维护代价会吃掉 $O(\log n)$ 的查找收益。要既快又能动态增删，就得把判定树的分支结构显式存下来——那就是二叉排序树和平衡二叉树。

先动手看一眼

加载可视化中...

代码与三处边界

// a[0..n-1] 为升序有序数组，返回下标；返回 -1 表示查找失败
int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {              // <= ：low == high 时区间里还剩一个元素，必须查
        mid = low + (high - low) / 2;  // 等价于 (low+high)/2，但避免 low+high 溢出
        if (a[mid] == key)
            return mid;
        else if (a[mid] > key)
            high = mid - 1;            // a[mid] 已被排除，所以是 mid-1 而不是 mid
        else
            low = mid + 1;             // 同理，保证区间严格缩小，循环必然终止
    }
    return -1;                         // 区间为空，查找失败
}

写法	写错会怎样
while (low <= high)	写成 < 时区间收缩到只剩一个元素（low == high）就退出，最后一个候选没被检查。a = {5}、key = 5：0 < 0 为假直接返回 -1，漏判
high = mid - 1 / low = mid + 1	写成 high = mid 或 low = mid，区间只剩两个元素时 mid 恒等于 low，区间不再缩小，死循环
mid = low + (high-low)/2	直接写 (low+high)/2 在两端都接近 INT_MAX 时加法溢出成负数，a[mid] 越界。408 的表长不会这么大，写 (low+high)/2 不算错

空表：n = 0 时 low = 0、high = -1，循环条件为假直接返回 -1，正确。

判定树与最坏比较次数

构造方法就是把算法递归展开：对区间 $[low,high]$ 取 $mid$ 作根，再对 $[low,mid-1]$ 与 $[mid+1,high]$ 递归。内部结点（圆）$n$ 个，外部结点（方框）$n+1$ 个。

$n=11$、mid 向下取整时得到的树：

                    [29]                ← 第 1 层
                  /       \
              [13]          [37]        ← 第 2 层
             /    \        /    \
           [7]   [16]   [32]   [41]     ← 第 3 层
             \      \      \      \
            [10]   [19]   [33]   [43]   ← 第 4 层

第 3 层的四个结点都来自只剩 2 个元素的区间，所以都只有右孩子——这不是画错，是向下取整的必然结果。

逐层统计得 $AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 1+2\times 2+3\times 4+4\times 4}{11}=3$；12 个外部结点中 4 个比较 3 次、8 个比较 4 次，得 $AS{L}_{\mathrm{失}\mathrm{败}}=\frac{44}{12}=\frac{11}{3}\approx 3.67$。

树高就是最坏比较次数，而这个数被真题直接问过两次：

$$h=\lceil {\log }_2(n+1)\rceil =\lfloor {\log }_{2}n\rfloor +1$$

两式对一切 $n\ge 1$ 恒等（$n=1$ 都是 1，$n=7$ 都是 3，$n=8$ 都是 4），不是两个不同的结论——严蔚敏教材写后一种，多数题目写前一种。

上手就用：$n=16$ 时 $\lceil {\log }_{2}17\rceil =5$，$n=600$ 时 $\lceil {\log }_{2}601\rceil =10$。

⚠️ 问"查找一个不存在的元素最多比较几次"，答案同样是 $h$，不是 $h+1$。失败查找走到某个外部结点，路径上的内部结点最多也就 $h$ 个。

判一个序列是不是合法的比较序列

题目给四个数列，问哪个不能构成折半查找的比较序列。最快的方法不是去画树，而是维护一个可行区间：

初始区间 $(L,R)=(-\mathrm{\infty },+\mathrm{\infty })$。比较过 $v_i$ 之后：若下一个 $v_{i+1}<v_i$（往左走），区间收成 $(L,v_i)$；若 $v_{i+1}>v_i$（往右走），区间收成 $(v_i,R)$。 任何时刻，下一个被比较的数都必须落在当前区间内，否则这个序列非法。

道理很直白：比较序列就是判定树里从根往下走的一条路径，而判定树是一棵二叉排序树——一旦你往某个结点的右子树走了，后面遇到的每一个数都必须比它大，反之亦然。

拿 500, 200, 450, 180 走一遍：

步	比较	走向	新区间
1	500	—	$(-\mathrm{\infty },+\mathrm{\infty })$
2	200 < 500	左	$(-\mathrm{\infty },500)$
3	450 > 200	右	$(200,500)$
4	180 < 450	左 → 须落在 $(200,450)$	❌ $180<200$

第 3 步走了 200 的右子树，此后所有数都必须大于 200，可第 4 步冒出个 180——非法。

对照一个合法的 180, 500, 200, 450：区间依次是 $(-\mathrm{\infty },+\mathrm{\infty })\to (180,+\mathrm{\infty })\to (180,500)\to (200,500)$，450 落在里面，全程合法。

判一棵树是不是合法的判定树

另一种问法给四棵二叉树，问哪棵可能是折半查找的判定树。判断条件有四条，前三条好想，第四条最容易漏：

1. 中序遍历有序（它是一棵 BST）。题目画空结点时这条自动满足。
2. 每个内部结点，左右子树的结点数之差不超过 1。
3. 每个内部结点，左右子树的高度差不超过 1（它是平衡的）。
4. 🔴 整棵树的 mid 取法必须前后一致。 向下取整就全程向下取整，向上取整就全程向上取整——不能这棵子树用一种、那棵子树用另一种。

第 4 条落到图上就是一句可直接目测的话：最底层那些"只有一个孩子"的结点，它们的孩子要么全挂在左边，要么全挂在右边。出现"左半边的叶子挂左孩、右半边的叶子挂右孩"这种镜像混搭，就是混用了两种取法，不合法。

真题里被排除的三个选项，全都栽在第 4 条上——前三条它们都满足。

取整方向：改比较次数，不改 ASL

$mid=\lfloor (low+high)/2\rfloor$ 是默认取法。换成向上取整，同一个 $n=11$ 的表得到的是上面那棵树的镜像：

	向下取整	向上取整
每层的结点个数	1, 2, 4, 4	1, 2, 4, 4（相同）
$AS{L}_{\mathrm{成}\mathrm{功}}$	3	3（相同）
$AS{L}_{\mathrm{失}\mathrm{败}}$	$\frac{11}{3}$	$\frac{11}{3}$（相同）
查 10 需要几次	4 次（29→13→7→10）	3 次（29→13→10）
查 7 需要几次	3 次	4 次

为什么必然相同（不是这个例子的巧合）：设当前区间有 $m$ 个元素。向下取整时 $mid$ 距左端 $\lfloor \frac{m-1}{2}\rfloor$ 格，于是左子树 $\lfloor \frac{m-1}{2}\rfloor$ 个结点、右子树 $\lceil \frac{m-1}{2}\rceil$ 个；向上取整恰好反过来。也就是说每一步只是把左右两棵子树的规模互换，递归下去整棵树就是镜像。镜像不改变任何结点的层数分布，所以两个 ASL 一定相等。

⚠️ 所以取整方向的真正影响是改变了某个具体元素的比较次数。题目问"查找 $X$ 需要比较几次"时必须先确认取整方式；问"ASL 是多少"时两种取整同一个答案。

还有一条常被忽略的性质：判定树的形态只由元素个数 $n$ 与取整方式决定，与关键字的取值完全无关（取 $mid$ 只用下标）。所以"长度 11 的有序表求 ASL"这种题，不管表里装的是什么数，答案都一样。

逐区间展开画树、逐层与逐外部结点求和的全过程（第一次学、或想手动模拟时展开）

以有序表 $\{7,10,13,16,19,29,32,33,37,41,43\}$ 为例，下标 $0\sim 10$，mid 向下取整。

区间	$mid$	取到的元素	左子区间	右子区间
$[0,10]$	5	29	$[0,4]$	$[6,10]$
$[0,4]$	2	13	$[0,1]$	$[3,4]$
$[6,10]$	8	37	$[6,7]$	$[9,10]$
$[0,1]$	0	7	空	$[1,1]$ → 10
$[3,4]$	3	16	空	$[4,4]$ → 19
$[6,7]$	6	32	空	$[7,7]$ → 33
$[9,10]$	9	41	空	$[10,10]$ → 43

以 $[0,1]$ 为例：$mid=\lfloor (0+1)/2\rfloor =0$ 取到 7，左区间 $[0,-1]$ 为空、右区间 $[1,1]$ 只剩 10。

成功 ASL——逐层统计：

层数	结点	结点数
1	29	1
2	13, 37	2
3	7, 16, 32, 41	4
4	10, 19, 33, 43	4

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 1+2\times 2+3\times 4+4\times 4}{11}=\frac{33}{11}=3$$

失败 ASL——逐个外部结点，比较次数等于父结点层数：

失败区间	探测路径	比较次数
$key<7$	29→13→7→左空	3
$7<key<10$	29→13→7→10→左空	4
$10<key<13$	29→13→7→10→右空	4
$13<key<16$	29→13→16→左空	3
$16<key<19$	29→13→16→19→左空	4
$19<key<29$	29→13→16→19→右空	4
$29<key<32$	29→37→32→左空	3
$32<key<33$	29→37→32→33→左空	4
$33<key<37$	29→37→32→33→右空	4
$37<key<41$	29→37→41→左空	3
$41<key<43$	29→37→41→43→左空	4
$key>43$	29→37→41→43→右空	4

第 3 层的 7、16、32、41 各只有右孩子，各贡献 1 个空左子树 → 4 个"比较 3 次"；其余 8 个来自第 4 层四个叶结点各自的两个空子树。4 + 8 = 12 = n+1 ✓

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{3\times 4+4\times 8}{12}=\frac{44}{12}=\frac{11}{3}\approx 3.67$$

树高与两个 ASL 公式的完整推导（不想只背结论就展开）

树高：判定树是平衡的，除最后一层外每层都填满。高度为 $h$ 的二叉树最多容纳 $2^h-1$ 个结点、最少 $2^{h-1}$ 个（前 $h-1$ 层填满再加一个），于是

$$2^{h-1}\le n\le 2^h-1$$

由右半边得 $h\ge {\log }_2(n+1)$，由左半边得 $h\le {\log }_{2}n+1$。$h$ 是整数，故

$$h=\lceil {\log }_2(n+1)\rceil =\lfloor {\log }_{2}n\rfloor +1$$

成功 ASL：取最整齐的情形 $n=2^h-1$，判定树是满二叉树，第 $j$ 层恰有 $2^{j-1}$ 个结点：

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1}{n}\sum _{j=1}^{h}j\cdot 2^{j-1}$$

利用恒等式 $\sum _{j=1}^{h}j\cdot 2^{j-1}=(h-1)2^h+1$（对 $h$ 归纳可验证：$h=1$ 时两边都是 1，$h=2$ 时都是 5，$h=3$ 时都是 17），代入 $2^h=n+1$、$h={\log }_2(n+1)$：

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{(h-1)(n+1)+1}{n}=\frac{n+1}{n}{\log }_2(n+1)-1\approx {\log }_2(n+1)-1$$

代入 $n=7$ 验证：$\frac{8}{7}\times 3-1=\frac{17}{7}\approx 2.43$，与逐层统计 $\frac{1+2\times 2+3\times 4}{7}=\frac{17}{7}$ 一致 ✓

失败 ASL：满二叉树情形下所有 $n+1=2^h$ 个外部结点都在同一层、父结点层数都是 $h$，故 $AS{L}_{\mathrm{失}\mathrm{败}}=h={\log }_2(n+1)$；一般情形介于 $h-1$ 与 $h$ 之间，故常写作 $\approx {\log }_2(n+1)$。

⚠️ 失败 ASL 的分母是 $n+1$ 不是 $n$，画判定树数方框最保险。

判定树的形态规律与复杂度逐项来历（手画判定树、或要核对量级时展开）

性质	说明	怎么用
判定树是一棵平衡二叉排序树	中序遍历得到原有序表；任意结点左右子树高度差不超过 1	可以直接套用平衡二叉树的高度分析
向下取整时，若区间元素数为偶数，左子树结点数比右子树少 1	区间大小 $m$ 时，左子树 $\lfloor \frac{m-1}{2}\rfloor$ 个、右子树 $\lceil \frac{m-1}{2}\rceil$ 个	手画时先算左右子树各几个结点，比一格一格数快
成功查找的比较次数 = 该元素所在的层数	从根走到它经过几个内部结点	逐层统计即可求成功 ASL
失败查找的比较次数 = 该外部结点父结点的层数	外部结点不含关键字，不参与比较	逐个外部结点统计即可求失败 ASL

指标	复杂度	怎么来的
最好时间	$O(1)$	第一次取的 mid 恰好命中
最坏时间	$O({\log }_{2}n)$	比较次数等于判定树高度 $\lceil {\log }_2(n+1)\rceil$
平均时间	$O({\log }_{2}n)$	$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{n+1}{n}{\log }_2(n+1)-1\approx {\log }_2(n+1)-1$
空间	$O(1)$	只用 low、high、mid 三个变量；递归写法是 $O(\log n)$，递归栈深度等于树高

⚠️ 空间那一行的括号是常被忽略的一处：非递归实现 $O(1)$、递归实现 $O({\log }_{2}n)$。

变体：在两个等长升序序列里找中位数（大题走法）

真题考过一道设计题：两个等长的升序序列 $A$、$B$（各 $n$ 个），求合并后的中位数，要求时间和空间都尽可能高效。直接归并是 $O(n)$，但有 $O(\log n)$ 的解法——双数组同时折半。

设 $A$ 的当前段是 $[s_1,e_1]$、$B$ 的当前段是 $[s_2,e_2]$，两段始终等长（这是循环不变量）。各取自己的中位数 $a=A[m_1]$、$b=B[m_2]$：

• $a=b$：它就是答案，返回。
• $a<b$：中位数不可能落在 $A$ 的左半段，也不可能落在 $B$ 的右半段——丢掉 $A$ 的左半、$B$ 的右半。
• $a>b$：对称地，丢掉 $A$ 的右半、$B$ 的左半。

每轮把两段同时减半，直到各剩 1 个元素，返回两者中较小的那个。

⚠️ 两处细节：① 丢弃时要保证两段仍然等长，段长为偶数和奇数时舍去的边界不一样，写代码时要分开处理；② 题面对"中位数"的定义是合并后第 $\lceil 2n/2\rceil =$ 第 $n$ 个（从 1 起数），别默认成第 $n+1$ 个。

时间 $O(\log n)$、空间 $O(1)$。

易混淆知识点

易混对象	区别	判别依据
判定树 vs 二叉排序树	判定树由 $n$ 唯一确定；BST 的形态由插入顺序决定	问"树形唯一吗"：判定树唯一，BST 不唯一
折半查找 vs 折半插入排序	后者是用折半定位插入位置的排序方法，仍要移动元素	见折半插入排序：比较降到 $O(n\log n)$，移动仍是 $O(n^2)$

考点速记

三条结论：

1. 最坏比较次数 = 判定树高度 $\lceil {\log }_2(n+1)\rceil$，查不存在的元素也是这个数。
2. 判定树的形态只由 $n$ 与取整方式决定，与表里装什么数无关；取整方向只改变个别元素的比较次数，不改变 ASL。
3. 两个前提分别封杀了无序数组与一切链式结构（含静态链表）。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求最多比较次数：给表长（16、600 这类数）问关键字比较次数最多是几。直接算 $\lceil {\log }_2(n+1)\rceil$——16 个元素是 5，600 个元素是 10。题面说"查找一个不存在的元素"也不改变答案。
• 判某序列不能构成比较序列：四个数列选一个非法的。维护可行区间 $(L,R)$ 往下走，出现落在区间外的数即非法。
• 判某二叉树可能是判定树：四棵树选一个合法的。前三条条件（BST、左右子树结点数差 ≤1、高度差 ≤1）多数选项都满足，真正起作用的是第四条——整棵树的 mid 取法必须一致，看底层叶子是不是全挂同一侧。
• 哪些结构不适合直接折半查找：有序链表 ✗、无序数组 ✗、有序静态链表 ✗、无序静态链表 ✗——四个全不行。静态链表那一项最容易误判成"可以"。
• 与其他查找策略比较次数的对比：给一段"每次跳 3 格往后扫"的伪代码，问它在什么情形下可能比折半更少比较——答案是目标接近数组开头时（跳查从头走，前几步就能命中；折半永远先比中间）。
• 双数组折半求中位数（大题）：两个等长升序序列求合并后的中位数，$O(\log n)$ 时间、$O(1)$ 空间。

易错：有序静态链表不能折半查找。 它虽然存在数组里，但逻辑顺序由 next 串起，物理下标不是逻辑序号，取不到"中间那个"。

易错：失败 ASL 的分母是 $n+1$。 用 $n$ 去除会把 $\frac{44}{12}$ 算成 $\frac{44}{11}$。

易错：判定树合法性的关键在"取整方式全树一致"。 只查结点数差和高度差，三个错误选项都会被放过。

易错：递归实现的空间是 $O(\log n)$，不是 $O(1)$。 问"空间复杂度"时要先看题目给的是迭代还是递归。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）7.2.2 节「折半查找」，p193： "折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列"。
• 同书 p195：折半查找判定树，并给出与本篇完全相同的算例——长度为 11 的有序表， "比较 1 次的只有一个根结点，比较 2 次的有两个结点，比较 3 次和 4 次的各有四个结点"， $ASL=\frac{1}{11}(1+2\times 2+3\times 4+4\times 4)=3$。
• 同书 p196：判定树深度为 $\lfloor {\log }_{2}n\rfloor +1$；外部结点与内部结点的定义； 满二叉树情形下的求和推导得 $ASL=\frac{n+1}{n}{\log }_2(n+1)-1$， $n$ 较大时近似为 ${\log }_2(n+1)-1$；以及"折半查找不适用于数据元素经常变动的线性表"。

相关知识

查找基本概念（判定树与"失败情况共 $n+1$ 种"的通用证明）｜ 顺序查找（判定树退化成单支链，与折半的平衡形态是两极）｜ 分块查找（索引表可用折半，块内只能顺序）｜ 二叉排序树、平衡二叉树 AVL、红黑树（把判定树做成可动态维护的版本，原理在树那一章）｜ B 树（把二路判定推广成 $m$ 路，用于外存）｜ 折半插入排序（用折半定位插入位置）｜ 查找算法分析与对比

相关文章

• 查找基本概念
• 顺序查找
• 分块查找
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B 树
• B+ 树
• 哈希表：拉链法
• 哈希表：开放定址法
• 查找算法对比

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2024Q52分2023Q82分2017Q82分2016Q92分2015Q72分2011Q4215分2010Q92分