企业官网建设流程全解析

• 文档
• 教程
• 知识库

二分搜索（Binary Search）是算法竞赛中最基础也最强大的工具之一：它把“有序数据上的查找”从线性复杂度 $O(n)$ 压缩到 $O(\log n)$，而“把答案二分、把判定问题化”这一思想更是几乎所有数值优化与组合问题的基础。本文以 cp-algorithms 仓库 的 src/num_methods/binary_search.md 为核心，系统讲解二分搜索在有序数组查找、lower/upper bound、任意单调谓词、二分答案、连续函数求根以及倍增式二分中的完整原理与可运行实现，帮助读者掌握一套在任何竞赛题中都能直接套用的二分框架。

核心思想：通过切分区间加速搜索

二分搜索（Binary search）是一种通过把搜索区间反复一分为二来加速查找的方法。它最常见的应用是在有序数组中查找某个值，但“分割区间”这一思路在大量典型任务中都扮演关键角色。

设给定有序数组 $A_0 \leq A_1 \leq \dots \leq A_{n-1}$，需要判断 $k$ 是否存在于序列中。最朴素的做法是逐一比较每个元素（线性搜索），复杂度为 $O(n)$，但完全没有利用数组有序这一信息。

二分搜索的基本观察是：如果我们知道两个下标 $L < R$ 满足 $A_L \leq k \leq A_R$，由于数组有序，可以断定 $k$ 要么出现在 $A_L, A_{L+1}, \dots, A_R$ 中，要么根本不出现在数组里。任取满足 $L < M < R$ 的下标 $M$，比较 $k$ 与 $A_M$ 的大小关系，只有两种可能：

1. $A_L \leq k \leq A_M$：问题从 $[L, R]$ 缩小为 $[L, M]$；
2. $A_M \leq k \leq A_R$：问题从 $[L, R]$ 缩小为 $[M, R]$。

当无法再取 $M$（即 $R = L+1$）时，直接比较 $k$ 与 $A_L$、$A_R$ 即可。否则我们希望 $M$ 的选取能让当前区间在最坏情况下尽快缩小为单个元素。

最优切分点的推导：为何总取中点

由于最坏情况下区间总是缩小到 $[L, M]$ 与 $[M, R]$ 中较大的那个，区间长度从 $R-L$ 变为 $\max(M-L, R-M)$。要最小化该值，应取 $M \approx \frac{L+R}{2}$，此时

$$ M-L \approx \frac{R-L}{2} \approx R-M. $$

也就是说，从最坏情况的角度看，最优策略永远是取 $[L, R]$ 的中点将其对半切分。这样活动区间每步减半，直到长度为 $1$。若整个过程需要 $h$ 步，最终把 $R-L$ 缩小到 $\frac{R-L}{2^h} \approx 1$，即 $2^h \approx R-L$。两边取 $\log_2$ 得到：

$$ h \approx \log_2(R-L) \in O(\log n). $$

对数级别的步数远优于线性搜索。例如当 $n \approx 2^{20} \approx 10^6$ 时，线性搜索约需一百万次操作，而二分搜索只需约 $20$ 次。

Lower bound 与 Upper bound

很多时候我们并不关心元素 $k$ 的精确位置，而是关心：

• lower bound（下界）：第一个大于等于 $k$ 的元素位置；
• upper bound（上界）：第一个大于 $k$ 的元素位置。

两者合起来恰好刻画了数组中所有等于 $k$ 的元素构成的（可能为空的）半开区间。要判断 $k$ 是否存在，只需找到其 lower bound，再检查该位置元素是否等于 $k$ 即可。

实现细节与边界处理

上面的推导是算法的粗略描述，实现时需要更精确的约定。我们维护一对满足 $A_L \leq k < A_R$ 的下标 $L < R$，即活动搜索区间为半开区间 $[L, R)$。采用半开区间而非闭区间 $[L, R]$，可以显著减少边界情况的处理。

当 $R = L+1$ 时，由上述定义可知 $R$ 正是 $k$ 的 upper bound。为了方便，将 $R$ 初始化为越过末尾的下标$n$，将 $L$ 初始化为越过开头的下标$-1$。只要算法从不直接求值 $A_L$ 与 $A_R$，就可以形式上把 $A_L$ 视为 $-\infty$、$A_R$ 视为 $+\infty$。中点取 $M = \lfloor \frac{L+R}{2} \rfloor$。完整实现如下：

... // a sorted array is stored as a[0], a[1], ..., a[n-1] int l = -1, r = n; while (r - l > 1) { int m = (l + r) / 2; if (k < a[m]) { r = m; // a[l] <= k < a[m] <= a[r] } else { l = m; // a[l] <= a[m] <= k < a[r] } }

算法执行期间从不求值 $A_L$ 与 $A_R$（因为恒有 $L < M < R$）。结束时，$L$ 是最后一个不大于 $k$ 的元素下标（若不存在则为 $-1$），$R$ 是第一个大于 $k$ 的元素下标（若不存在则为 $n$）。

中点计算的溢出陷阱

注意：计算m时写成m = (r + l) / 2在l、r均为正数时可能溢出。这个经典 bug 曾在 JDK 中存在约 9 年之久。更稳妥的写法是：

int m = l + (r - l) / 2; // 对正数 l、r 永远正确

但注意当l为负数时该写法仍可能溢出（这正是上述实现中 $L=-1$ 的边界场景）。如果使用 C++20，可以直接用std::midpoint(l, r)，它总是正确工作。

在任意单调谓词上做二分

设 $f : {0,1,\dots, n-1} \to {0, 1}$ 是定义在 $0,1,\dots,n-1$ 上、单调不减的布尔函数：

$$ f(0) \leq f(1) \leq \dots \leq f(n-1). $$

上文描述的二分的本质，其实就是用谓词 $f(M)$（即 $k < A_M$ 的布尔值）来划分数组。我们完全可以把比较式换成任意单调谓词——当计算 $f(k)$ 代价很高、无法对每个取值都求值时，这种形式尤为有用。

换句话说，二分搜索找到的是唯一满足 $f(L) = 0$ 且 $f(R) = f(L+1) = 1$ 的转折点$L$；若 $f(0) = \dots = f(n-1) = 0$ 则得到 $L = n-1$，若 $f(0) = \dots = f(n-1) = 1$ 则得到 $L = -1$。

正确性证明：假设转折点存在，即 $f(0)=0$ 且 $f(n-1)=1$。实现维护循环不变量$f(l)=0,\ f(r)=1$。当 $r-l > 1$ 时，$m$ 的取法保证 $r-l$ 严格递减；循环在 $r-l = 1$ 时终止，此时就找到了想要的转折点。代码如下：

... // f(i) is a boolean function such that f(0) <= ... <= f(n-1) int l = -1, r = n; while (r - l > 1) { int m = (l + r) / 2; if (f(m)) { r = m; // 0 = f(l) < f(m) = 1 } else { l = m; // 0 = f(m) < f(r) = 1 } }

二分答案（Binary search on the answer）

这种“只能判定、不能直接计算”的二分场景非常常见：题目要求计算某个值，但我们只具备“检查答案是否至少为 $i$”的能力。

一个经典例子：给定数组 $a_1,\dots,a_n$，求满足 $r-l \geq x$ 的任意区间中最大平均值的向下取整：

$$ \left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor $$

朴素的区间枚举不可行，但可以二分答案 $\lambda$，转而检查是否存在满足条件的 $l, r$ 使得：

$$ \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda. $$

等价变形为：

$$ (a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0, $$

于是问题转化为：检查新数组 $a_i - \lambda$ 中是否存在长度至少为 $x+1$、前缀和非负的子段，这可以用前缀和在线性时间内完成。判定函数单调（$\lambda$ 越大越难满足）正是二分答案可用的前提。

这一“最大平均子段 + 二分答案”技术链在仓库中还有独立专题：见 src/others/maximum_average_segment.md 的“Search for a subarray with a maximum/minimum average”一节，其给出了总复杂度 $O(T(n) \log W)$ 的结论（$W$ 为所需精度，$T(n)$ 为带约束的子问题求解时间）。另外，仓库的 src/dynamic_programming/longest_increasing_subsequence.md（LIS 的 $O(n \log n)$ 解法）也直接引用了本文的二分思想来在 $d[]$ 数组上查找位置。

连续函数上的二分搜索

设 $f : \mathbb R \to \mathbb R$ 是在区间 $[L, R]$ 上连续的实值函数。不失一般性假设 $f(L) \leq f(R)$。由[介值定理（intermediate value theorem）]可知，对任意 $y \in [f(L), f(R)]$，都存在 $x \in [L, R]$ 使 $f(x) = y$。注意与前面不同，这里不要求函数单调。

任意给定的精度 $\delta$ 下，$x$ 可以在 $O\left(\log \frac{R-L}{\delta}\right)$ 时间内逼近到 $\pm\delta$ 以内。思路与离散情形本质相同：取 $M \in (L, R)$，根据 $f(M)$ 与 $y$ 的大小关系，把搜索区间缩小到 $[L, M]$ 或 $[M, R]$。

最常见的应用是求奇数阶多项式的实根。例如 $f(x)=x^3 + ax^2 + bx + c$，当 $L \to -\infty$ 时 $f(L) \to -\infty$，当 $R \to +\infty$ 时 $f(R) \to +\infty$，因此总能取到足够小的 $L$ 与足够大的 $R$ 使 $f(L) < 0$、$f(R) > 0$，进而用二分把包含根的区间缩小到任意小。仓库的 src/num_methods/roots_newton.md 对求根问题提供了另一条基于牛顿法的路径，可与二分法互为补充。

基于 2 的幂的二分（倍增搜索）

另一种值得注意的二分形式是：不维护活动区间，而是维护当前指针 $i$ 与当前的幂 $k$。指针从 $i=L$ 出发，每次迭代在点 $i+2^k$ 上测试谓词：

• 若谓词仍为 $0$，指针前进至 $i+2^k$；
• 否则指针保持不变；
• 随后 $k$ 减 1。

这种倍增式搜索（binary lifting）广泛应用于树上任务，例如求两顶点的最近公共祖先（LCA）、或找高度满足条件的祖先节点；也可以改造用于在 Fenwick 树中查找第 $k$ 个非零元素。这类应用的完整实现可参考仓库的 src/graph/lca_binary_lifting.md 与 src/data_structures/fenwick.md。

二分思想在仓库中的广泛交叉引用

二分搜索在本仓库中并非孤立话题，而是被多个专题文档作为底层工具反复引用，从侧面印证了其基础地位：

• src/dynamic_programming/longest_increasing_subsequence.md：LIS 的 $O(n \log n)$ 动态规划解法用二分在 $d[]$ 数组中定位插入位置，并直接以相对链接引用本文；
• src/string/suffix-array.md：后缀数组排序完成后，可用二分在 $p$ 中查找模式串 $s$，复杂度 $O(|s| \log |t|)$，二次二分可统计出现次数；
• src/data_structures/sqrt-tree.md：提到用二分定位树节点，将单次查询优化到 $O(\log \log \log n)$；
• src/others/maximum_average_segment.md：最大平均子段问题的标准解法即“二分答案 + 判定子段和”，总复杂度 $O(T(n) \log W)$；
• src/data_structures/segment_tree.md、src/data_structures/treap.md、src/geometry/point-in-convex-polygon.md、src/algebra/discrete-log.md 等也都在各自算法中嵌入二分或二分答案。

这些引用表明：掌握“区间减半”与“谓词判定”两种二分形态，是阅读和运用本仓库大量进阶算法的前提。

复杂度总结与选用建议

选用时牢记三个要点：数组/谓词必须单调（连续函数情形则需函数连续且目标值落在值域内）；半开区间 $[L, R)$ 配合虚边界 $-1$ 与 $n$ 可避免绝大多数边界 bug；中点计算优先写l + (r - l) / 2或 C++20 的std::midpoint。

练习题目

仓库文档提供了丰富的实战训练题，覆盖本文学到的全部形态：

• LeetCode：Find First and Last Position of Element in Sorted Array、Search Insert Position、First Bad Version、Valid Perfect Square、Find Peak Element、Search in Rotated Sorted Array、Find Right Interval；
• Codeforces：Interesting Drink (706/B)、Magic Powder - 1 (670/D1)、Another Problem on Strings (165/C)、Frodo and pillows (760/B)、GukiZ hates Boxes (551/C)、Enduring Exodus (645/C)、Chip 'n Dale Rescue Rangers (590/B)、Points on Line (251/A)。

建议按“有序数组二分 → 谓词二分 → 二分答案 → 连续二分 → 倍增二分”的顺序逐题训练，直至能一眼识别出问题中的单调性，并熟练写出带l + (r - l) / 2的健壮实现。

小结

二分搜索的威力不在于“找中点”，而在于把难以直接求解的问题转化为可判定的单调问题：只要存在一个随变量单调变化的布尔/实数谓词，就可以用 $O(\log)$ 次判定换取精确结果。本文以 src/num_methods/binary_search.md 为骨架，给出了有序数组查找、lower/upper bound、任意谓词二分、二分答案、连续函数求根与倍增二分的完整理论与可运行实现，并借助仓库内的交叉引用（LIS、后缀数组、最大平均子段、sqrt-tree 等）展示了其实际应用广度。

• 文档
• 教程
• 知识库