尧图网页设计 
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载二分搜索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_{L1}, \dots, A_R$ 中要么根本不出现在数组里。任取满足 $L M R$ 的下标 $M$比较 $k$ 与 $A_M$ 的大小关系只有两种可能$A_L \leq k \leq A_M$问题从 $[L, R]$ 缩小为 $[L, M]$$A_M \leq k \leq A_R$问题从 $[L, R]$ 缩小为 $[M, R]$。当无法再取 $M$即 $R L1$时直接比较 $k$ 与 $A_L$、$A_R$ 即可。否则我们希望 $M$ 的选取能让当前区间在最坏情况下尽快缩小为单个元素。最优切分点的推导为何总取中点由于最坏情况下区间总是缩小到 $[L, M]$ 与 $[M, R]$ 中较大的那个区间长度从 $R-L$ 变为 $\max(M-L, R-M)$。要最小化该值应取 $M \approx \frac{LR}{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 L1$ 时由上述定义可知 $R$ 正是 $k$ 的 upper bound。为了方便将 $R$ 初始化为越过末尾的下标$n$将 $L$ 初始化为越过开头的下标$-1$。只要算法从不直接求值 $A_L$ 与 $A_R$就可以形式上把 $A_L$ 视为 $-\infty$、$A_R$ 视为 $\infty$。中点取 $M \lfloor \frac{LR}{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$ 的边界场景。如果使用 C20可以直接用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(L1) 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_{l1} \dots a_r}{r-l1} \right\rfloor $$朴素的区间枚举不可行但可以二分答案 $\lambda$转而检查是否存在满足条件的 $l, r$ 使得$$ \frac{a_l a_{l1} \dots a_r}{r-l1} \geq \lambda. $$等价变形为$$ (a_l - \lambda) (a_{l1} - \lambda) \dots (a_r - \lambda) \geq 0, $$于是问题转化为检查新数组 $a_i - \lambda$ 中是否存在长度至少为 $x1$、前缀和非负的子段这可以用前缀和在线性时间内完成。判定函数单调$\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.mdLIS 的 $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$。指针从 $iL$ 出发每次迭代在点 $i2^k$ 上测试谓词若谓词仍为 $0$指针前进至 $i2^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.mdLIS 的 $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 等也都在各自算法中嵌入二分或二分答案。这些引用表明掌握“区间减半”与“谓词判定”两种二分形态是阅读和运用本仓库大量进阶算法的前提。复杂度总结与选用建议场景谓词每次判定代价总复杂度有序数组查找 / lower / upper bound$k A_M$$O(1)$$O(\log n)$任意单调谓词二分$f(M)$任意$O(T)$$O(T \log n)$二分答案数值优化检查答案是否 $\geq \lambda$$O(T(n))$$O(T(n) \log W)$连续函数二分求根$f(M)$ 与目标值比较$O(1)$$O\left(\log \frac{R-L}{\delta}\right)$倍增式二分binary lifting点 $i2^k$ 处谓词$O(T)$$O(T \log n)$选用时牢记三个要点数组/谓词必须单调连续函数情形则需函数连续且目标值落在值域内半开区间 $[L, R)$ 配合虚边界 $-1$ 与 $n$ 可避免绝大多数边界 bug中点计算优先写l (r - l) / 2或 C20 的std::midpoint。练习题目仓库文档提供了丰富的实战训练题覆盖本文学到的全部形态LeetCodeFind 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 IntervalCodeforcesInteresting 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 等展示了其实际应用广度。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Swift Algorithm Club 二分查找Binary Search完全指南在有序数组中快速定位元素Swift Algorithm Club 二分查找Binary Search完全指南在有序数组中快速定位元素 导读 本篇技术指南以 Swift Algor示例工程教程LeetCode 35. Search Insert Position 题解Go 实现有序数组的二分搜索插入位置LeetCode 35. Search Insert Position 题解Go 实现有序数组的二分搜索插入位置 导读 本文以 LeetCode 35. Se示例工程二叉搜索树Binary Search Tree原理与 Java 实现从增删查到中序遍历与平衡化演进二叉搜索树Binary Search Tree原理与 Java 实现从增删查到中序遍历与平衡化演进 本篇技术指南以仓库 Computer Science/教程知识库上一篇终极指南使用OpenCore Legacy Patcher让老款Mac焕发新生下一篇OpenCore Legacy Patcher终极指南让老旧Mac免费升级最新macOS的完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 cp-algorithms 二分搜索（Binary Search）完全指南：从有序数组到二分答案与倍增技巧
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载二分搜索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_{L1}, \dots, A_R$ 中要么根本不出现在数组里。任取满足 $L M R$ 的下标 $M$比较 $k$ 与 $A_M$ 的大小关系只有两种可能$A_L \leq k \leq A_M$问题从 $[L, R]$ 缩小为 $[L, M]$$A_M \leq k \leq A_R$问题从 $[L, R]$ 缩小为 $[M, R]$。当无法再取 $M$即 $R L1$时直接比较 $k$ 与 $A_L$、$A_R$ 即可。否则我们希望 $M$ 的选取能让当前区间在最坏情况下尽快缩小为单个元素。最优切分点的推导为何总取中点由于最坏情况下区间总是缩小到 $[L, M]$ 与 $[M, R]$ 中较大的那个区间长度从 $R-L$ 变为 $\max(M-L, R-M)$。要最小化该值应取 $M \approx \frac{LR}{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 L1$ 时由上述定义可知 $R$ 正是 $k$ 的 upper bound。为了方便将 $R$ 初始化为越过末尾的下标$n$将 $L$ 初始化为越过开头的下标$-1$。只要算法从不直接求值 $A_L$ 与 $A_R$就可以形式上把 $A_L$ 视为 $-\infty$、$A_R$ 视为 $\infty$。中点取 $M \lfloor \frac{LR}{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$ 的边界场景。如果使用 C20可以直接用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(L1) 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_{l1} \dots a_r}{r-l1} \right\rfloor $$朴素的区间枚举不可行但可以二分答案 $\lambda$转而检查是否存在满足条件的 $l, r$ 使得$$ \frac{a_l a_{l1} \dots a_r}{r-l1} \geq \lambda. $$等价变形为$$ (a_l - \lambda) (a_{l1} - \lambda) \dots (a_r - \lambda) \geq 0, $$于是问题转化为检查新数组 $a_i - \lambda$ 中是否存在长度至少为 $x1$、前缀和非负的子段这可以用前缀和在线性时间内完成。判定函数单调$\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.mdLIS 的 $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$。指针从 $iL$ 出发每次迭代在点 $i2^k$ 上测试谓词若谓词仍为 $0$指针前进至 $i2^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.mdLIS 的 $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 等也都在各自算法中嵌入二分或二分答案。这些引用表明掌握“区间减半”与“谓词判定”两种二分形态是阅读和运用本仓库大量进阶算法的前提。复杂度总结与选用建议场景谓词每次判定代价总复杂度有序数组查找 / lower / upper bound$k A_M$$O(1)$$O(\log n)$任意单调谓词二分$f(M)$任意$O(T)$$O(T \log n)$二分答案数值优化检查答案是否 $\geq \lambda$$O(T(n))$$O(T(n) \log W)$连续函数二分求根$f(M)$ 与目标值比较$O(1)$$O\left(\log \frac{R-L}{\delta}\right)$倍增式二分binary lifting点 $i2^k$ 处谓词$O(T)$$O(T \log n)$选用时牢记三个要点数组/谓词必须单调连续函数情形则需函数连续且目标值落在值域内半开区间 $[L, R)$ 配合虚边界 $-1$ 与 $n$ 可避免绝大多数边界 bug中点计算优先写l (r - l) / 2或 C20 的std::midpoint。练习题目仓库文档提供了丰富的实战训练题覆盖本文学到的全部形态LeetCodeFind 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 IntervalCodeforcesInteresting 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 等展示了其实际应用广度。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Swift Algorithm Club 二分查找Binary Search完全指南在有序数组中快速定位元素Swift Algorithm Club 二分查找Binary Search完全指南在有序数组中快速定位元素 导读 本篇技术指南以 Swift Algor示例工程教程LeetCode 35. Search Insert Position 题解Go 实现有序数组的二分搜索插入位置LeetCode 35. Search Insert Position 题解Go 实现有序数组的二分搜索插入位置 导读 本文以 LeetCode 35. Se示例工程二叉搜索树Binary Search Tree原理与 Java 实现从增删查到中序遍历与平衡化演进二叉搜索树Binary Search Tree原理与 Java 实现从增删查到中序遍历与平衡化演进 本篇技术指南以仓库 Computer Science/教程知识库上一篇终极指南使用OpenCore Legacy Patcher让老款Mac焕发新生下一篇OpenCore Legacy Patcher终极指南让老旧Mac免费升级最新macOS的完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考