本讲定位：五级的第一思维武器。官方大纲把「二分算法」单列一个知识块，且明确点名了”二分查找”和”二分答案（也称二分枚举法）“两项。2026 年 3 月五级真题里出现了完整的
lowerBound模板代码。二分答案更是五级编程题的常客——很多看起来无从下手的最优化问题，二分一下就变成简单的判定问题。对应官方大纲：五级知识块 5「二分算法」——二分查找算法、二分答案算法（也称二分枚举法）；知识块 2「算法复杂度估算（含对数）」。
前置知识：排序、四级第 05 讲的复杂度估算。
代码说明：本讲所有二分模板均已用 g++ 11.5 编译，并与 STL 的
lower_bound/upper_bound随机对拍 1000 组验证通过。
我心里想一个 1~100 的数，你来猜，我只回答”大了”“小了”“对了”。最少几次一定能猜到？
最优策略：每次猜中间的数。 每猜一次，范围减半：
$$ 100 \to 50 \to 25 \to 13 \to 7 \to 4 \to 2 \to 1 $$
7 次必中。如果范围是 $n$，次数就是 $\lceil \log_2 n \rceil$。
$$ \boxed{\text{二分的本质：每次操作把搜索范围减半，} O(\log n)} $$
这个”减半”有多强？
| $n$ | 线性查找次数 | 二分查找次数 |
|---|---|---|
| $10^3$ | 1000 | 10 |
| $10^6$ | 1000000 | 20 |
| $10^9$ | 1000000000 | 30 |
📌 记住：$\log_2 10^9 \approx 30$。 $n$ 每翻十亿倍，二分只多 30 步。这就是对数复杂度的威力（呼应大纲”含对数的复杂度估算”）。
$$ \boxed{\textbf{二分查找的前提是数组【有序】}} $$
更本质地说，是需要”单调性”——必须能通过判断中间元素，确定地排除掉一半。
⚠️ 高频判断题：“二分查找可以用于无序数组” → ❌ 错。 ⚠️ 另一个考点：链表不能二分（无法 $O(1)$ 访问中间元素，见五级第 04 讲）。