专题：二分查找与二分答案

二分只有五行代码，但它是唯一一个”人人都会写、人人都写错”的算法。本讲的组织方式因此和别的讲不同：不是先讲原理再讲应用，而是先把”为什么会写错”讲透，再讲它真正值钱的那一半——二分答案。

一句话主线：

二分查找回答”这个值在哪”；二分答案回答”当我不知道答案是多少、但给我一个答案我能验证它对不对”。后者才是竞赛里的主力。

1. 从一道题说起

P2440 木材加工：有 $n$ 根木头，长度分别为 $L_1,\dots,L_n$。要把它们切成 $K$ 段等长的小段（可以有剩料），求这个长度最大能是多少。$n\le10^5$，$L_i\le10^8$。

正着想很难：长度取多少？没有公式。

但反着想很容易：给你一个长度 $L$，你能不能判断”切得出 $K$ 段吗”？ 能——每根木头能切出 $\lfloor L_i/L\rfloor$ 段，加起来和 $K$ 比一下就行，$O(n)$。

而且这个判定有个关键性质：$L$ 越小越容易切够。于是”能不能切出 $K$ 段”这件事，随着 $L$ 从 1 增大到 $\max L_i$，是真真真……假假假——它单调。

单调的判定 + 有界的答案 = 二分。 这就是本讲下半部分的全部内容。

那为什么不直接从大到小一个个试？ 实测（$n=10^5$、答案范围 $10^8$）：

快约 250 万倍。 而 26 次这个数字不是巧合——$\log_2(10^8)=26.6$。二分的全部收益就是把”试 $N$ 次”压成”试 $\log_2 N$ 次”。

但在讲二分答案之前，得先把二分本身写对。 这是下一节的事，而它比想象中难。

2. 二分查找：三套模板与它们的边界

2.1 为什么人人都会写错

二分的逻辑只有一句：“看中间，扔掉一半”。写错的原因全部集中在一件事上：

“扔掉一半”到底扔掉了哪些？中间那个元素被扔了没有？

这件事由三个约定共同决定，三者必须成套，换一个就得全换：