二分查找¶

方法速览¶

任务	方法	口诀
前提	数据有序	无序不二分
最多比较次数	\(\lceil \log_2(n+1) \rceil\)	比一次砍一半
速算	\(n \le 2^k - 1\) 则至多 k 次	1023 内 10 次
找第一个 ≥x	边界收缩式：`l < r` 收半，答案在 l	答案记在 l
死循环防法	`r = m` 时配 `m = (l+r)/2`；`l = m` 时配 `(l+r+1)/2`	右移配下取整

次数推导¶

每比较一次，区间淘汰一半：n → n/2 → n/4 → …。设最坏 k 次后区间为空：

\[\frac{n}{2^k} < 1 \iff k > \log_2 n \Rightarrow k_{\max} = \lceil \log_2(n+1) \rceil\]

常用速算（判定树高度视角：k 层判定树最多 \(2^k - 1\) 个结点）：

n	最多比较次数	备注
\(7\)	\(3\)	\(2^3 - 1 = 7\) 恰满
\(8\)	\(4\)
\(100\)	\(7\)	\(2^6 - 1 = 63 < 100 \le 127 = 2^7-1\)
\(1000\)	\(10\)	\(2^{10} = 1024\)
\(10^6\)	\(20\)

例：有序表 \(\{1\dots15\}\) 查 11 的区间演化（每次取中点 \(\lfloor(l+r)/2\rfloor\)）：

步	区间 [l, r]	中点 m	比较
1	[1, 15]	8	\(11 > 8\)，去右半
2	[9, 15]	12	\(11 < 12\)，去左半
3	[9, 11]	10	\(11 > 10\)，去右半
4	[11, 11]	11	命中

查找失败（如查 0）：区间缩空也要 \(\lceil\log_2(n+1)\rceil\) 次——成功与失败的最坏次数同级。

三种模板¶

模板一（递归）：

int bsearch(int a[], int l, int r, int x) {
    if (l > r) return -1;
    int m = (l + r) / 2;
    if (a[m] == x) return m;
    return a[m] < x ? bsearch(a, m + 1, r, x) : bsearch(a, l, m - 1, x);
}

模板二（l ≤ r 循环）：直接版，找到即返回：

int l = 1, r = n;
while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] == x) { cout << m; break; }
    if (a[m] < x) l = m + 1; else r = m - 1;
}

模板三（边界收缩，求第一个 ≥x）：不找“等于”而找边界，l < r 收半、答案收敛在 l：

int l = 1, r = n + 1;          // 候选区间 [1, n+1)
while (l < r) {
    int m = (l + r) / 2;       // 下取整
    if (a[m] >= x) r = m;      // m 可能是答案，保留
    else l = m + 1;
}
// 循环结束 l == r == 第一个 ≥x 的位置

这正是 lower_bound 的行为。死循环警报：若收缩写 r = m（不越过 m），中点必须下取整；反过来若写 l = m，中点必须 (l + r + 1) / 2 上取整——否则区间长度为 1 时 m = l，l = m 永远不动。

二分答案：把“求最大的可行 x”转成“判定 x 可不可行”，判定函数单调时二分——考场上认准“单调 + 求最值”就上二分。

练习题目¶

练习 1 · 前提条件¶

题目

二分查找要正常工作，数据必须（）

A. 数值互不相同
B. 都是正数
C. 有序
D. 存在数组里

答案与解析

答案：C

每次靠“与中点比大小”决定去哪半——无序就无从判断方向。

练习 2 · 基本次数¶

题目

8 个有序元素二分查找，最坏比较（）次。

A. \(3\)
B. \(8\)
C. \(4\)
D. \(2\)

答案与解析

答案：C

\(\lceil\log_2 9\rceil = 4\)：3 次最多干掉 7 个（\(2^3-1\)），8 个元素必须 4 次。

练习 3 · 千级规模¶

题目

1000 个有序元素二分查找，最坏比较（）次。

A. \(500\)
B. \(9\)
C. \(11\)
D. \(10\)

答案与解析

答案：D

\(2^{10} = 1024 \ge 1000\) → 10 次；9 次最多覆盖 \(2^9 - 1 = 511\) 个。

练习 4 · 百级规模¶

题目

100 个有序元素二分查找，最坏比较（）次。

A. \(6\)
B. \(10\)
C. \(8\)
D. \(7\)

答案与解析

答案：D

\(2^6 - 1 = 63 < 100 \le 127 = 2^7 - 1\) → 7 次。

练习 5 · 恰好整幂¶

题目

1023 个有序元素二分查找，最坏比较（）次。

A. \(10\)
B. \(11\)
C. \(9\)
D. \(512\)

答案与解析

答案：A

\(1023 = 2^{10} - 1\) 恰是 10 层判定树满容——“减一”就是为了卡进整幂。

练习 6 · 2 的幂边界¶

题目

128 个有序元素与 127 个有序元素，最坏比较次数分别是（）

A. \(8\) 和 \(7\)
B. \(7\) 和 \(7\)
C. \(7\) 和 \(8\)
D. \(8\) 和 \(8\)

答案与解析

答案：A

127 = \(2^7-1\) → 7 次；128 超出一位 → \(\lceil\log_2 129\rceil = 8\) 次——跨过 \(2^k - 1\) 才加一。

练习 7 · 区间演化¶

题目

有序表 \(\{1\dots15\}\) 查 11，第一次比较后查找区间变为（）（中点取 \(\lfloor(l+r)/2\rfloor\)）

A. \([1, 7]\)
B. \([8, 15]\)
C. \([1, 8]\)
D. \([9, 15]\)

答案与解析

答案：D

中点 8，\(11 > 8\) 去右半 \([8+1, 15]\)——越过中点（m 已比较过，不再进区间）。

练习 8 · 第二次比较¶

题目

接上题，第二次比较的中点是（）

A. \(9\)
B. \(10\)
C. \(12\)
D. \(11\)

答案与解析

答案：C

区间 \([9,15]\) 的中点 \(\lfloor(9+15)/2\rfloor = 12\)；\(11 < 12\) 再去左半。

练习 9 · 失败查找¶

题目

有序表 \(\{1\dots15\}\) 查 0（不存在），比较次数是（）

A. \(3\)
B. \(15\)
C. \(4\)
D. \(1\)

答案与解析

答案：C

区间 \([1,15]\to[1,7]\to[1,3]\to[1,1]\to\) 空，4 次比较——失败的最坏次数与成功同级。

练习 10 · 中点计算¶

题目

区间 \([l, r] = [6, 9]\) 的二分中点是（）（下取整）

A. \(7.5\)
B. \(8\)
C. \(7\)
D. \(6\)

答案与解析

答案：C

\(\lfloor(6+9)/2\rfloor = 7\)——偶数个元素时中点偏左。

练习 11 · 比较次数的量级¶

题目

二分查找 n 个元素的时间复杂度是（）

A. \(O(1)\)
B. \(O(\log n)\)
C. \(O(n)\)
D. \(O(n\log n)\)

答案与解析

答案：B

区间指数级缩小，比较次数是对数级——对比线性扫 \(O(n)\)。

练习 12 · 线性对比¶

题目

100 万有序数据，顺序查找平均约 50 万次，二分查找最坏约（）次。

A. \(20\)
B. \(1000\)
C. \(100\)
D. \(50\) 万

答案与解析

答案：A

\(2^{20} = 1048576 > 10^6\) → 20 次。

练习 13 · 第一个 ≥x（lower_bound 语义）¶

题目

有序数组 \(\{2, 4, 4, 4, 7, 9\}\)，“第一个 \(\ge 5\)”的位置是（）

A. 下标 4（值 7）
B. 下标 3（值 4）
C. 下标 0（值 2）
D. 不存在

答案与解析

答案：A

第一个 \(\ge 5\) 的是 7——边界收缩式二分 / lower_bound 找的就是这条分界线。

练习 14 · 大量重复元素¶

题目

有序数组里有 100 个相同的值 x，二分找到的（）

A. 一定是第一个 x
B. 一定报错
C. 通常是中间某个 x（模板直接版不保证位置）
D. 一定找不到

答案与解析

答案：C

l<=r 直接版命中哪个 x 看路径；要第一个 x 必须用边界收缩式（模板三）。

练习 15 · 模板三的循环条件¶

题目

边界收缩式二分（求第一个 ≥x）的循环条件是（）

A. while (l <= r)
B. while (true) 无出口
C. while (l < r)
D. do-while

答案与解析

答案：C

l < r 收半到重合即停，答案就在 l；写 <= 会在长度 1 时多转一圈甚至死循环。

练习 16 · 收缩语句¶

题目

模板三中 a[m] >= x 时应执行（）

A. l = m + 1
B. r = m
C. r = m - 1
D. break

答案与解析

答案：B

m 可能正是答案，不能越过；r = m - 1 会把答案丢掉。

练习 17 · 死循环成因¶

题目

while (l < r) 循环里收缩写 l = m（中点下取整），当区间变成 \([5, 6]\) 时会（）

A. 正常结束
B. 死循环：m = 5 = l，区间永远不变
C. 越界
D. 提前退出

答案与解析

答案：B

下取整时 \(\lfloor(5+6)/2\rfloor = 5 = l\)，l = m 原地踏步——配套应是 m = (l + r + 1) / 2（上取整得 6）。

练习 18 · 递归版结构¶

题目

递归二分 a[m] < x 时应递归（）

A. (l, m - 1)
B. (m + 1, r)
C. (l, m)
D. (m, r)

答案与解析

答案：B

目标更大在右半，且 m 已比较过必须越过；C/D 保留 m 会无限递归。

练习 19 · 判定树视角¶

题目

n 个元素二分查找的判定树高度约为（）

A. \(n\)
B. \(\log_2 n\)
C. \(\sqrt{n}\)
D. \(n/2\)

答案与解析

答案：B

每个内部结点一次比较、每层砍半——树高就是比较次数。

练习 20 · 二分答案的适用信号¶

题目

“求最大的 x 使条件 P(x) 成立”能用二分答案的前提是（）

A. P(x) 关于 x 单调（x 可行则更小的也可行 / 反之）
B. P(x) 涉及字符串
C. 数据必须无序
D. x 必须是质数

答案与解析

答案：A

单调才能“砍半”判定：可行半区保留、不可行半区丢弃。

练习 21 · 二分答案实例¶

题目

一根长 20 的绳子切成长度相同的整数段、至少 7 段，每段最长是（）

A. \(2\)
B. \(3\)
C. \(4\)
D. \(5\)

答案与解析

答案：A

段长 k 可行 ⟺ \(\lfloor 20/k \rfloor \ge 7\)：\(k=3\) 时 \(\lfloor 20/3\rfloor = 6 < 7\) 不可行；\(k=2\) 时 \(\lfloor 20/2\rfloor = 10 \ge 7\) 可行 → 最大可行段长 2。

干扰项思路：B 是“6 段也凑合”的误算——“至少 7 段”是硬约束。

练习 22 · lower_bound 返回¶

题目

lower_bound(a, a+n, x) 返回（）

A. 最后一个 ≤ x 的位置
B. 第一个 > x 的位置
C. x 的下标（必须存在）
D. 第一个 ≥ x 的位置

答案与解析

答案：D

第一个 > x 的是 upper_bound；两个函数相差“等号归属”。

练习 23 · upper_bound¶

题目

upper_bound 找的是（）

A. 第一个 ≥ x 的位置
B. 第一个 > x 的位置
C. 最后一个 = x 的位置
D. 最接近 x 的位置

答案与解析

答案：B

两个“边界”函数：lower 管 ≥、upper 管 >；两者之差 = x 的个数。

练习 24 · 二分与顺序查找对比¶

题目

\(n = 10^8\) 的有序数据各查一次，顺序查找与二分查找的比较次数约为（）

A. \(5\times10^7\) 与 \(27\)
B. \(10^8\) 与 \(100\)
C. \(27\) 与 \(27\)
D. \(5\times10^7\) 与 \(10^4\)

答案与解析

答案：A

\(\lceil\log_2(10^8+1)\rceil = 27\)（\(2^{27} \approx 1.3\times10^8\)）；顺序平均扫一半。

练习 25 · 无序数组硬二分¶

题目

对无序数组使用二分查找（）

A. 一定找到目标
B. 可能漏掉目标（方向判断失去依据）
C. 更快
D. 自动先排序

答案与解析

答案：B

比较中点后无法断定目标在哪半——结果不可靠；先排序再二分通常不如直接线性扫。

练习 26 · 综合判断¶

题目

下列说法错误的是（）

A. 二分查找最坏 \(\lceil\log_2(n+1)\rceil\) 次比较
B. 查找失败也要对数级次数
C. 二分查找对有序数组是 \(O(\log n)\)
D. 二分查找最坏 \(O(n)\)

答案与解析

答案：D

最坏也是对数级；\(O(n)\) 是顺序查找。

历年真题¶

2019 年 · 第 5 题¶

题目

设有 \(100\) 个已排好序的数据元素，采用折半查找时，最大比较次数为（）。

A. \(10\)
B. \(6\)
C. \(8\)
D. \(7\)

答案与解析

答案：D

\(2^6 - 1 = 63 < 100 \le 127 = 2^7 - 1\) → 7 次。判定树 7 层足够容纳 100 个结点、6 层不够。

2024 年 · 第 9 题¶

题目

假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较（）次。

A. \(25\)
B. \(10\)
C. \(7\)
D. \(1\)

答案与解析

答案：B

\(2^{10} = 1024 \ge 1000\)（9 次最多覆盖 \(2^9 - 1 = 511\) 个）→ 10 次。

易错小结¶

二分必须有序；最坏 \(\lceil\log_2(n+1)\rceil\) 次（成功失败同级）；
速算锚点：\(2^7-1=127\)、\(2^{10}=1024\)、\(2^{20}\approx10^6\)——跨过 \(2^k-1\) 才加一（127→7 次、128→8 次）；
中点越过才进区间：去右半是 [m+1, r] 不是 [m, r]；
求边界（第一个 ≥x）用 l < r 收半式；r = m 配下取整、l = m 配上取整，配错必死循环；
lower_bound 第一个 ≥、upper_bound 第一个 >；
“单调 + 求最值”→ 二分答案。