第六章:二分与倍增

当候选答案能按顺序排列,且一次判断可以排除连续的一半候选时,就可以使用二分。本章先从有序数组查找建立区间不变量,再把查找对象换成答案;最后用倍增预存较长的连续跳跃,减少重复移动。
阅读前需要掌握有序数组、循环和整数范围;综合题还会调用第四章的前缀和与差分。本章各个 C++ 程序均可独立编译,不能把多个 拼成一份源文件。倍增使用固定后继关系,步数的二进制拆分在本节说明。
1. 查找指定值
例题:查找。
简易题面:给定单调不减序列和若干询问,输出每个询问值第一次出现的下标,不存在则输出 。
数据范围:,;。
顺序查找每次最多访问全部元素。有序数组允许从中点比较:若中点偏小,左半不可能包含目标;若偏大,右半不可能包含目标。先手算返回任意匹配位置的基础过程,再改成例题要求的首次出现位置。全局数组 至 已非降序排列, 为当前询问值, 表示尚未找到。
前提是数组已经有序。使用 可以避免 溢出。
循环中的 表示尚未被排除的候选位置。若中点太小,有序性保证 全部太小;若中点太大, 全部太大。把中点一并排除,区间才能严格缩短。
可以把候选区间想成一排按数值排好序、尚未划掉的卡片。检查中间一张后,划掉的是一整段,而不是只划掉这一张。例如在 中查找 :
| 轮次 | 检查前的下标范围 | 中点与比较 | 排除的位置 | 剩余位置 |
|---|---|---|---|---|
| , | :值都不超过 | |||
| , | :值都不超过 | |||
| , | 不再排除,直接返回 | 答案下标为 |

灰色卡片表示已经排除的位置,蓝色范围表示待查区间。每次未找到目标时,候选数至多减为原来的一半,因此最多进行 轮检查。
下面的完整演示程序读入 、有序数组和 个查询值,每行输出一个匹配位置或 。它用于观察基本查找过程;题目要求的首次位置由下一节实现。
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N];
int get(int x){
int l=1,r=n,ans=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(a[mid]==x){
ans=mid;
break;
}
if(a[mid]<x)l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
int m,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
while(m--){
scanf("%d",&x);
printf("%d\n",get(x));
}
return 0;
}
这个程序遇到相等值就结束,所以有重复元素时不保证返回第一次出现的位置。例题 查找 要求首次出现,应继续寻找左边界。若根本不存在,循环结束后仍为 ,不要把最终中点当成答案。
当边界允许跨越很大的正负范围时, 本身也可能超出 ,仍需要让边界变量使用足够宽的类型;中点写法不能替代范围分析。
2. 查找第一个满足条件的位置
假设条件随位置变化为:
false false false true true true
把 初值设为 ,表示还没有见过真值。找到可行位置后先保存,再继续向左寻找第一个。对于首次出现问题,令 等价于 ;搜索结束后,还需检查 ,否则应输出无解。每次查询使用新的 ,时间为 。
查找最后一个满足条件的位置时,方向相反。
把“第一个真”看成一个尚待定位的分界线。检查到真时,中点先作为备选答案保存,之后只在左半继续找更早的真;检查到假时,中点及其左侧都可以排除。结束时, 要么是最早的真,要么保留哨兵 表示一个都没有。
例如真假序列为 假,假,真,真,真,初始 :检查 3 为真,记住 3,改查 ;再检查 1、2 均为假,最终答案仍是 3。候选位置被排除后,已记录的答案不会丢失。
重复值能展示“找到一个”与“找到第一个”的区别。在 中查询 ,第一次检查下标 就已经相等;但它左侧还有一个 ,所以不能立即结束。把条件写成 ,得到的真假排列为“假、真、真、真、真”:
| 轮次 | 检查前的范围 | 判断结果 | 保存的答案 | 下一轮范围 |
|---|---|---|---|---|
| ,条件为真 | ||||
| ,条件为假 | ||||
| ,条件为真 | ,区间为空 |

第一次保存答案后,下标 已在待查范围之外,但答案标记仍然保留。这里 的前提是已经执行了 ;若只排除中点而不保存,就可能丢失答案。
“最后一个真”常对应 真...真,假...假:真时保存并向右找,假时向左找。应先画出真假排列,再决定移动方向,而不是只改一个比较符号。
循环开始时,真正的左边界若存在,要么是已保存的 ,要么仍在待查闭区间 中。真时保存中点再删去右半,假时删去左半,都不会丢掉这两处之外的新答案;区间清空后,只需检查保存的位置。下面的程序与《查找》的输入输出一致。
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N];
int get(int x){
int l=1,r=n,ans=n+1;
while(l<=r){
int mid=l+(r-l)/2;
if(a[mid]>=x){
ans=mid;
r=mid-1;
}else l=mid+1;
}
if(ans<=n&&a[ans]==x)return ans;
return -1;
}
int main(){
int m,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=m;++i){
scanf("%d",&x);
printf("%d%c",get(x),i==m?'\n':' ');
}
return 0;
}
若要找最后一个不大于 的位置,条件应是 ,真假排列为“真到假”。取 ,真时保存 并令 ,假时令 。例如 查询 :先检查位置 ,保存 ;再检查 ,保存 ;最后检查 为假,答案为 。全为假时保留哨兵 。这不是寻找首次出现时直接换掉一个比较符号,而是重新确认目标分界与移动方向。
3. STL 边界函数
以下仍查询同一个有序全局数组。返回位置减去数组起始地址 后得到一号下标(不是减去搜索起点 ); 是尾后位置,只能比较,不能作为有效元素读取。
- :第一个大于等于 ;
- :第一个大于 ;
- : 的出现次数。
返回位置可能是 ,使用前必须判断。
数组 中查询 ,、,出现次数为 。查询不存在的 ,两个位置都为 ,差为零;查询 ,两个位置都为 。

目标同为 时,三个值为 的位置在 下都为真,在 下都为假。因此两个分界点分别落在下标 和 ,相等元素恰好占据半开区间 。这两幅动图使用手写二分展示边界的含义,不表示 STL 函数必须按相同顺序访问元素。
要判断值是否存在,应先检查 ,再检查 。 返回的是“不小于目标”的边界,目标缺失时也会正常返回一个位置。调用前必须保证数组按相容的比较规则有序。
下面是边界函数的独立演示:输入与上一节相同,每次查询输出下界位置、上界位置、出现次数。输出的 表示尾后位置,不读取该处元素。
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int a[N];
int main(){
int n,m,x;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
while(m--){
scanf("%d",&x);
int p1=lower_bound(a+1,a+n+1,x)-a;
int p2=upper_bound(a+1,a+n+1,x)-a;
printf("%d %d %d\n",p1,p2,p2-p1);
}
return 0;
}
4. 二分答案
例题:数列分段 Section II。
简易题面:将长度为 的非负整数序列分成恰好 个非空连续段,使各段元素和的最大值最小。输出这个最小值。
数据范围:;,答案不超过 。
直接选择 个切分位置,会产生大量方案。逐个构造最优划分较难,但给定一个段和上限后,只需判断能否在规定段数内装下全部元素。于是可以把求最优值改成判定,再寻找最小可行上限。
把非负序列切成 个非空连续段,最小化最大段和。最小候选至少是单个元素最大值,最大候选可以取全体总和;上界的类型要容纳总和,不能只看最后输出答案的范围。
给定段和上限 ,从左到右尽量把元素放入当前段,只有再放一个就超限时才开新段。
为什么这会使段数最少?记贪心完成第 段后的右端为 ,任意合法划分对应的右端为 。第一段尽量向右延伸,所以 。贪心若已经覆盖全部元素,就不需要再开新段。
在尚未完成覆盖时,假定 :若 ,贪心用前 段已经覆盖到对方第 段的末尾;否则,区间 是对方第 段的一部分。元素非负,这一部分的和不会超过整段的上限 ,贪心第 段至少能覆盖到 。
因此同样多的段数下,贪心总能覆盖得至少一样远;任意划分覆盖全数组时,贪心也已覆盖全数组,所需段数不会更多。
例如 切两段:上限 时,贪心得到 、、 三段,不可行;上限 时得到 、 两段,可行。上限增加只会放宽限制,因此可以找第一个可行值。
这个模型可以想成沿着传送带装箱:元素必须按原顺序装入,每箱容量都是待检查的上限 ,当前箱再放一个就超限时才换箱。容量增大后,原来能装下的方案仍然能装下,因此可行性只会从假变真。

上方数轴表示候选上限 至 ,下方按顺序放入 。每次取中点后,重新分段,再用所需段数判断上限是否可行。搜索的是容量,不是元素下标。
判定只需检查段数不超过 :元素非负,拆开任意已有段不会增大段和,而且 时总能继续拆到恰好 个非空段。若允许负数,贪心和这个拆分论证都需要重新检查。每次 都从空段状态开始,不能继承上次候选的计数。
程序用全局 保存输入。元素和可能接近 ,因此二分边界、候选值及段内累计和都使用 ,即使题面保证最终答案不超过 。
取 为最大元素、 为元素总和,便得到包含答案且右端可行的闭区间。下面每轮都保留最小可行值所在的一侧,结束时两端相等。
当所有元素都为零时,初始 ,无需进入循环,答案就是零。总时间为 ,其中 是搜索范围宽度;输入数组占 空间。
对上面的五个数,要求恰好分成两段时,完整的区间变化如下:
| 检查前的候选上限范围 | 试用上限 | 贪心分段 | 判定结果 | 更新后的范围 |
|---|---|---|---|---|
| 、 | 两段,可行 | |||
| 、、 | 三段,不可行 | |||
| 、 | 两段,可行 | |||
| 、、 | 三段,不可行 |
这里判定为真时使用 ,与前面的 并不矛盾:前一种写法把中点存入 后继续搜索,本节写法则让答案始终留在 内,没有另存答案。若把本节的更新直接改成 ,第三轮就会丢掉正确答案 。
若要求的段数改为 或 :只有一段时,答案为总和 ;每个元素单独一段时,答案为最大元素 。这两个边界例子也说明了初始范围的两个端点分别来自哪里。
把手算的两层工作对应到程序: 负责一个容量下的完整分段, 只负责缩小容量范围。输入第一行为 ,第二行为数组,输出最小的最大段和。
#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m,a[N];
bool check(long long x){
int cnt=1;
long long sum=0;
for(int i=1;i<=n;++i){
if(a[i]>x)return 0;
if(sum+a[i]>x){
++cnt;
sum=0;
}
sum+=a[i];
}
return cnt<=m;
}
int main(){
scanf("%d%d",&n,&m);
long long l=0,r=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
l=max(l,1LL*a[i]);
r+=a[i];
}
while(l<r){
long long mid=l+(r-l)/2;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",l);
return 0;
}
5. 实数二分
简单问题:给定 ,求非负平方根,绝对误差不超过 。
按很小的步长枚举答案,会使次数随精度要求急剧增加。非负数平方随数值增大而增大,因此可以比较中点的平方与 ,每次排除一半范围。答案位于 ,程序中的 均为 。
先手算 :初始 ;中点 的平方偏小,留下 ;中点 的平方偏大,留下 ;中点 的平方偏小,留下 。每次都保留平方根所在的一半。
理想实数运算中,迭代 次后区间宽度缩小为原来的 。本例迭代次数足够,答案也不超过 , 能满足所需绝对精度。输出仍要保留足够小数位。实数更新不使用整数二分中的加一、减一;固定次数也能避免端点因浮点舍入不再变化时陷入死循环。
连续函数求根还有另一种二分依据:两端异号时,保留仍然异号的一半。它依赖连续性,不要求整个函数单调;但多根区间只能保证夹住某个根。三次方程等问题必须先分析根的范围与分离条件,不能直接套一个全局单调判定。
下面程序的输入是一个非负实数,输出它的平方根:
#include <bits/stdc++.h>
using namespace std;
int main(){
double n;
cin>>n;
double l=0,r=max(1.0,n);
for(int t=1;t<=100;++t){
double mid=l+(r-l)/2;
if(mid*mid>=n)r=mid;
else l=mid;
}
printf("%.10f\n",(l+r)/2);
return 0;
}
即使理想区间宽度能达到 ,实际精度仍受 舍入限制,不能承诺任意位数。这里根至多为 ,该量级相邻浮点数的距离远小于 ,十位小数也足以控制输出舍入。本程序没有使用“函数值差足够小”作为停止条件,因为函数值误差与横坐标误差不是同一件事。
6. 倍增
简单问题:远程跳转。
简易题面:有 个传送点,编号为 到 。从传送点 进行一次传送后,会到达 。
给定 次询问。每次询问给出起点 和非负整数 ,请输出从 出发恰好传送 次后所在的传送点。
数据范围:;;。
逐次模拟每条询问,步数可能达到十亿以上。一步规则固定时,可以预先保存大步跳转,查询时再拼接。程序用 保存从位置 连续走 步后的位置。连续两段 步正好拼成一段 步,因此可以逐层建表。全局 保存跳转表,约需 MB;第 层保存每个位置的一步后继。
查询时 为非负 ,且 时预留 层即可。 初始为查询起点。每轮用整除 和取余 提取二进制位:余数为一,就走当前层对应的步数。
零步查询直接保留起点,不进入循环。
把走 步写成 步,只需完成三次已经预处理好的跳转。 的计算先走前半段 步,再从中途位置继续走同样多的步,因此右侧两个表项都来自较低层。预处理必须先枚举层数,再枚举全部位置。
若最大步数为 ,表的时间、空间均为 ,单次查询为 ;层数取决于步数,而不只是位置个数。 时需要覆盖第 至 位,步数使用 。若允许走到不存在的位置,可用 作哨兵,并令它在所有层仍跳到 。
下面手算一个有环的例子:。从 出发,走 步分别到 。例如四步跳转先查 ,再查 ,得到 。查询 步时,按低位到高位先从 跳一步到 ,再从 跳四步到 ,最后从 跳八步到 。每次查表必须使用上一次跳转后的起点。
代码第一行输入 ,第二行输入各点一步后继,随后每行输入起点和步数。
#include <bits/stdc++.h>
using namespace std;
const int N=200000+10;
int nxt[N][60];
int main(){
int n,q,x;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)scanf("%d",&nxt[i][0]);
for(int k=1;k<60;++k){
for(int i=1;i<=n;++i)nxt[i][k]=nxt[nxt[i][k-1]][k-1];
}
while(q--){
long long s;
scanf("%d%lld",&x,&s);
for(int k=0;s>0;++k,s/=2){
if(s%2==1)x=nxt[x][k];
}
printf("%d\n",x);
}
return 0;
}
建表的正确性可以逐层说明:第 层来自输入;若第 层正确,先后两次这样的跳转就恰好走了 步。查询始终保证当前位置已完成所有处理过的二进制位对应的总步数,最终所有位处理完毕,走过的步数正好等于原询问值。图中虽然有环,仍不影响“恰好走若干步”的含义。
第七章的快速幂也按二进制拆分次数,但它反复平方一个数值、把选中的幂乘入答案;这里预先合成的是所有起点的后继函数。共同点是把长过程拆成二的幂次长度,维护的对象不同。
7. 二分综合模型
7.1 二分操作前缀
简易题面:按顺序处理 次教室申请,每次在闭区间 的每天占用 间。给出每天容量,求第一个无法满足的申请;全部成功则输出 。
数据范围:,,。
若执行前 个操作后的状态可以快速检查,而且一旦失败,执行更多操作也一定失败,就可以二分第一个失败的操作。
前 次资源申请可以用差分批量累计,再检查任一天是否超额。申请量非负,因此一旦前 次已经失败,增加后续申请不可能重新成功,失败条件具有单调性。
每次检查都要清空本次累计数组并只加入前 次申请。二分尝试的 不按大小顺序出现,不能默认下一次检查只是给上一次状态追加操作。还应先区分“全部成功”和“存在首次失败”两种输出。
先手算三天容量 ,按顺序申请“第 至 天各借 间”“第 至 天各借 间”“第 天借 间”。检查前一份时,用量为 ,可满足;检查前两份时,用量为 ,第二天超额。第三份不会减少第二天用量,因此首次失败是第 份。这里二分下标是申请编号,差分下标却是日期,二者不能混用。
先检查全部 份。如果可行,直接输出 ;否则已知首次失败存在,保持它在 内。中点可行说明首次失败在它右侧;中点失败则保留中点及左侧。这正是前面“答案保留在区间中”的版本。每次差分还原得到的是真实用量,判定遍历全部日期,所以既不会漏掉超额日期,也不会凭空制造冲突。
输入格式与原题一致,失败时输出两行 和编号。一次检查耗时 ,总时间 ,空间 。同一天累计申请最多为 ,差分与还原和使用 ;只用 保存单份申请量并不能保证累计值安全。
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int n,a[N],d[N],s[N],t[N];
long long b[N];
bool check(int k){
fill(b,b+n+2,0);
for(int i=1;i<=k;++i){
b[s[i]]+=d[i];
b[t[i]+1]-=d[i];
}
long long sum=0;
for(int i=1;i<=n;++i){
sum+=b[i];
if(sum>a[i])return 0;
}
return 1;
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=m;++i)scanf("%d%d%d",&d[i],&s[i],&t[i]);
if(check(m)){puts("0");return 0;}
int l=1,r=m;
while(l<r){
int mid=l+(r-l)/2;
if(check(mid))l=mid+1;
else r=mid;
}
printf("-1\n%d\n",l);
return 0;
}
7.2 隐式序列第 小
简单问题:乘法表第 K 小。
简易题面:有一个 行 列的乘法表,第 行第 列的数为 。
把表中的 个数按非递减顺序排列,相同的数按出现次数重复保留。求排列后的第 个数。
数据范围:;。
有些有序序列太大,不能完整生成。可以二分候选值 ,计算“小于等于 的元素个数”,再寻找第一个计数达到 的值。
乘法表第 行为 ,其中不超过 的个数是 。对全部行求和,就能知道整个表中不超过 的元素数,无须生成 个元素。
重复值按出现次数计数。寻找第一个“计数至少为 ”的 ,才能正确处理多个位置拥有同一个值的情况;不能要求计数恰好等于 ,因为计数可能一次跳过 。
例如 表为 、、。排序后是 ,第 小是 。候选 的三行计数为 ,合计 ;候选 的计数为 ,合计 。计数从 跳到 ,没有“恰好四个”的候选值。
把候选值增加时,每行满足上限的列只会增多,所以总计数不减。若第 小值为 ,所有 都不足 个,所有 都至少有 个,最早为真的整数恰好是 。初始范围为 ,必含答案。行列可以交换,枚举较短维能减少判定次数。
输入一行 ,输出第 小值。 可达 ,范围、排名和累计数量都使用 ;数组没有实际建立。总时间为 ,额外空间 。
#include <bits/stdc++.h>
using namespace std;
long long n,m,k;
bool check(long long x){
long long sum=0;
for(long long i=1;i<=n;++i){
sum+=min(m,x/i);
if(sum>=k)return 1;
}
return 0;
}
int main(){
cin>>n>>m>>k;
if(n>m)swap(n,m);
long long l=1,r=n*m;
while(l<r){
long long mid=l+(r-l)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<'\n';
return 0;
}
7.3 平均值参数化
简单问题:最大平均数。
简易题面:给定一个长度为 的非负整数序列 。请选择一个长度不少于 的连续子段,使这个子段的平均数尽可能大。
输出最大平均数乘以 后向下取整的结果。
数据范围:;。
直接枚举两个端点并求平均数,即使有前缀和也要枚举 个区间。若先给定平均数门槛 ,长度为 、元素和为 的区间满足 ,等价于 。因此把每个元素减去 ,便只需寻找长度至少为 、和非负的区间。
本题要求输出向下取整后的千倍平均数,可以直接搜索整数 ,并把每个数变为 。某个区间变换后的和非负,当且仅当它的千倍平均数至少为 。最大的可行整数就是所求的向下取整结果,不需要在二分结束后猜测怎样修正浮点误差。
设变换后的前缀和为 ,并令 。以 为右端时,左端可以写成 ,长度限制成为 。于是只需判断
扫描 ,每轮新加入的合法前缀位置只有 。维护这些合法位置的最小值 ,不需要重新枚举全部左端点。
例如 ,要求长度至少为 。试 ,变换值为 ,前缀和为 :
| 右端 | 新加入的前缀位置 | 合法前缀最小值 | 判断 | |
|---|---|---|---|---|
| 不可行 | ||||
| 区间 可行 |
右端为 时,程序先把 加入候选,再计算差,才能找到 。如果把 也加入候选,就可能拿到长度为零的伪区间;如果只计算最近 个元素,则会漏掉更长区间。例如 、 的两个长度为 的平均数都是 ,整个长度为 的区间平均数却为 。
门槛越大,变换后每个元素越小,可行性只能从真变假。保持最大可行整数位于闭区间 ,初始 。中点可行时保留中点并向右找,否则删去中点及右边。这里用上取整中点:若 ,取下取整中点会使可行分支反复执行 ;上取整保证区间严格缩短。
输入第一行 ,第二行数组。前缀和绝对值最多 ,使用 。每次检查 ,二分约 次,总时间 ,空间 。下面的程序完全使用整数计算。
#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m,a[N];
long long s[N];
bool check(int x){
s[0]=0;
for(int i=1;i<=n;++i)s[i]=s[i-1]+1000LL*a[i]-x;
long long mn=0;
for(int r=m;r<=n;++r){
mn=min(mn,s[r-m]);
if(s[r]-mn>=0)return 1;
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
int l=0,r=2000000;
while(l<r){
int mid=l+(r-l+1)/2;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…