一次搞懂二分到底怎么写
二分知识点
二段性: 可以找到一个性质,使得可以将答案分为一部分满足这个性质,一部分不满足这个性质. 使用场景 : 所以二分在不满足单调性的情况也可能可以使用. 只要可以找到一个性质将答案分为两部分.
一般来说,题目中经常包含最大值最小,最小值最大等关键词,我们就可以考虑是不是需要使用二分
时间复杂度: O(logn), n是整个区间大小
模版的重要性
因为不管笔试还是平时使用(平时根本不会使用到,笑死), 都不可能会有时间再去推导一次边界条件. 就像我们学习数学一样, 不可能在考试的时候再推倒一遍公式. 模版是一个道理, 理解,记住, 解题的时候直接使用就好.
下面给出二分模版和记忆方法
// 记忆方法有两点
// 1. 右加必右减
// 2. 以及SR找右边界,如果当前满足,则需要继续向右找,即给更改做边界即可
// 二分右边界模版
const SR = (l: number, r: number) =>{
while(l < r ){
const mid = l + r + 1 >> 1; // 右加
if(check(mid)) l = mid; // 查找右边界,当前满足继续向右查找
else r = mid - 1; // 必右减
}
return r;
}
// 和SR相对应即可
const SL = (l: number, r: number) =>{
while(l < r ){
const mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return r;
}
// 浮点数二分
// 没有+1,-1的边界情况
const SF = (l: number, r: number) =>{
const eps = 1e-6 // 二分精度,一般比题目精度高2位即可
while(r - l > eps){
const mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
}
练习题
看到这里还是不明白模版怎么使用? 没关系,我们接下来看几道例题理解下模版如何使用,以及加深下对模版的记忆
为了方便大家理解,这里给出的答案都是核心代码模式,即不用处理输入输出
题目1: 数的范围
给定一个按照升序排列的长度为n的整数数组，以及一个需要查找的元素num
返回一个元素 num的起始位置和终止位置（位置从0开始计数）
如果数组中不存在该元素,则返回 [-1,-1],否则返回 [起始位置,终止位置]
样例#1
n = [1 2 2 3 3 4], num = 3
样例输出#1
[3,4]
样例#2
n = [1,2,2,3,3,4], num = 4
样例输出#2
[5,5]
样例#3
n = [1,2,2,3,3,4], num = 5
样例输出#3
[-1,-1]
题目解析
这里要查询指定数字的两边,所以使用一次SR查找右边界,使用SL查找左边界即可.对于查不到的提前处理输出.
// 给出升序数组n和要查找的值num的范围
// 所以这里我们使用模版,分别查找左右边界即
const numberRange(n:number[], num: number){
const l = 0, r = n.length - 1;
let res = []
// 二分右边界模版
while(l < r){
const mid = l + r + 1 >> 1;
if(q[mid] >= num) l = mid;
else r = mid - 1;
}
// 处理答案, 这里没找到返回undefined
if(q[l] !== num) return [-1,-1];
res[0] = l;
// 二分左边界模版
while(l < r ){
const mid = l + r >> 1;
if(q[mid] <= num) r = mid
else l = mid + 1;
}
res[1] = l;
return res;
}
题目2: 数的三次方根
给定一个浮点数,求它的三次方根
输入样例 1000.00
输出样例 10.000000
数据范围 -10000 <= n <= 10000
题目解析
题目范围给定了n的区间在[-10000,10000]之内, 所以我们可以二分这个区间,这个区间区间满足二段性.即我们可以找到一个点mid,使得 mid * mid * mid = 给定的浮点数, 如果mid * mid * mid 比给浮点数大,我们向左查找,否则向右查找.
因为是浮点数,不涉及边界问题,使用浮点数模版即可
const cubeRoot = (num: number) => {
let l = -10000, r = 10000;
while(r - l > 1e-8){ // 一般比题目要求精度多2为
let mid = (l + r ) / 2;
if(mid * mid * mid < num) l = mid; // 向右查找
else r = mid;
}
return r.toFixed(6)
}
题目3: 跳石头
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
L = 起点到终点的距离 N = 起点到终点的岩石数量 M = 组委会至多移走的岩石的数量 数据保证 L >= 1 且 N >= M >= 0,
nums[] = 表示第i块岩石距离起点的距离D[i]. 这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
数据范围
0 <= M <= N <= 50000, 1 <= L <= 10^9
样例输入 #1
L = 25, N = 5, M = 2
nums = [0,2,11,14,17,21,25], nums中包含起点0和终点L
样例输出 #1
4
题目解析
题目中说使得选手们在比赛过程中的最短跳跃距离尽可能长,说明这个跳跃距离可以进行二分.
我们可以以二分的方式枚举这个跳跃距离,判断当前的这个条约距离是否符合题意,即如果要达到这个最短跳跃距离需要移走的岩石数量是否小于组委会可以移走的岩石数.
如果当前的跳跃距离满足, 则我们继续查找更大的跳跃距离(向右搜索的模版). 如果找不到我们应该向左找.
const jump = (L:number,N:number,M:number, nums:numer[]) => {
let l = 1, r = 1e9;
// 向右搜索模版
while(l < r){
const mid = (l + r + 1) / 2; // 右加
if(check(mid,nums)) l = mid;
else r = mid - 1; //必右减
}
}
// 检查达到当前最短跳跃距离,组委会需要移动岩石的数量是否小于 M
const check = (mid: number,nums: number[]) =>{
let cnt = 0, lastVal = 0;
// 从第一块岩石开始遍历,到终点
for(let i = 1; i <= nums.length; i++){
// 计算每块石头距离上一块的距离,如果小于mid,则需要移除(因为mid已经是最跳跃距离了,再小就不合适了)
if(d[i] - lastVal < mid) cnt ++;
else lastVal = d[i]; //大于就记录上一块的位置,方便下次计算
}
// 判断是否满足条件
return cnt <= m;
}
题目4: 刺杀大使
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 times个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 n行的m 个房间里有m个机关，这些机关必须全部打开才可以进入大使馆。而第1行的m个房间有m扇向外打开的门，是迷阵的入口。除了第1 行和第n行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第i行第j列 造成的伤害值为p[i,j]（第1 行和第n行的p值全部为0)
现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第n行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式
第一行有两个整数 n,m，表示迷阵的大小。
接下来n行，每行m个数，第i行第j列的数表示p[i,j]
输出格式
输出一个数，表示最小伤害代价。
样例输入 #1
4 2
0 0
3 5
2 4
0 0
样例输出 #1
3
数据范围
n,m <= 1000, p[i,j] <= 1000
题目解析
题意中表示士兵受到的伤害值为路径上所有房间伤害值的最大值,又要求整个部队的伤害值最少. 意思就是求出某条路径上最大伤害值最小,我们可以使用二分模版去查找这个伤害值,并判断士兵在当前二分出来的伤害值下是否可以走到最后一层即可. 此题是二分与其他算法的结合(BFS 或DFS).
const assassination = (n:number,m:number,p: number[][])=>{
// 数组的长度
const n = p.length, m = p[0].length;
let ans = 0;
// 遍历确定二分区间,最小伤害值和最大伤害值
let l = 1e9, r = 0;
for(let i = 1; i <= n; i++)
for(let j = 1; j <= m; j++){
r = Math.max(r,p[i][j]);
l = Math.min(l,p[i][j]);
}
// 要查找整个部队的最小值,即我们二分出来的mid满足条件,也需要继续向左查找,使用SL模版
while(l < r){
let mid = (l + r) / 2;
if(check(1,1,mid,n,m){
r = mid;
ans = mid; // 记录答案
}else{
l = mid + 1;
}
}
}
// 检查当前二分出的值是否满足从第一行到最后一行的条件
const check = (x: number, y: number, maxn:number)=>{
// 状态数组,遍历过程中剪枝使用
let st: boolean[][] = Array(3).fill(Array(2).fill(false));
// 方便后续遍历每个节点的4个不同方向
let dx[4] = [-1,0,-1,0], dy[4] = [0,1,0,-1];
let q = []; // 数组模拟队列,先进先出
q.push(x,y); // q中存放的是[x,y]坐标
st[x][y] = true;
while(q.length != 0){
const t = q.shift(); // 取头元素
// 遍历t元素得4个相邻元素
for(let i = 0; i < 4; i++){
let x = t[0] + dx[i], y = t[1] + dy[i];
// 如果说遍历到得元素超过了范围,或者已经遍历过,或受到得伤害超过了maxn,则剪枝
if(x < 1 || x > n || y < 1 || y > m || st[x][y] || p[x][y] > maxn) continue;
st[x][y] = true;
if(x == n) return true; // 如果到了第n行,则返回true
else q.push({x,y}); // 否则加入队列
}
}
// 如果遍历结束都到达不了,则不满足条件
return false;
}
题目5: 借教室
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来 n天的借教室信息，其中第i 天学校有 r[i] 个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为d[j],s[j],t[j]，表示某租借者需要从第 s[j] 天到第 t[j] 天租借教室（包括第 s[j]天和第t[j]天），每天需要租借 d[j] 个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 d[j] 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 s[j]天到第 t[j] 天中有至少一天剩余的教室数量不足 d[j] 个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
输入格式
输入n,m表示天数和订单的数量
数组r[i],长度为n,表示第i天可用于租借教室的数量
数组d[i],长度为m,表示订单[i]租借得数量
数组s[i],t[i],长度为m,分别表示订单[i]租借开始、结束分别在第几天
天数与订单均用从下标1开始存放。
输出格式
如果所有订单均可满足,包含一个整数 [0]数组。 否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。即 [-1,需要修改订单得申请人编号]
样例输入 #1
r = [0,2,5,4,3]
d = [0,2,3,4]
s = [0,1,2,2]
t = [0,3,4,4]
样例输出 #1
[-1,2],即订单无法完全满足,2号订单需要修改
数据范围
1<= n, m <= 10^6, 0<= r[i],d[j] <= 10^9, 1 <= s[j] <= t[j] <= n
题目解析
题目中说订单按照先后顺序分配, 若不足则停止分配. 所以我们可以二分订单, 如果当前的订单可以满足,则前面的订单一定都满足. 如果当前订单不满足,则后面的订单一定也都不满足. 即满足二分的二段性.
接下来我们要判断是二分出来的当前订单是否满足条件,即从第一个订单到当前订单需要房间数量是否小于学校可提供得数量.如果当前房间不满足条件,则我们需要继续向左查找,找到第一个不满足的订单,所以在这里我们使用SL模版
由于每一个订单处理都是对区间进行减法的操作,这个区间维护的是n天,每天有多少房间可以实用. 区间减法我们可以转换成差分数组来做,这样我们只用改变两个值,即可完成对一段区间的修改. 差分在这里只是给区间一定范围减去相同数,不影响理解二分算法
const scheduleRoom = (r:number[], d: number[], s: number[], t: numebr[]) =>{
const n = r.length, m = d.length;
let l = 1, r = m;
// 如果都满足
if(check(m,n,r,d,s,t)) return [0];
// SL模版
while( l < r){
let mid = (l + r) / 2;
if(check(mid,n,r,d,s,t)) l = mid + 1 ;
else r = mid;
}
}
return[-1,l];
const check = (mid: number,n:number,r:number[],d:number[], s: number[], t:number[]) =>{
// 构造差分数组
let diff = Array(n).fill(0);
// 用来统计每天一共需要的房间数量
let need = Array(n).fill(0);
// 对从1到mid天的订单做累计
for(let i = 1; i <= mid; i++){
diff[s[i] += d[i];
diff(t[i] + 1) -= d[i];
}
// 计算出从1到mid天每天需要得房间的数量,如果比提供的多,则返回false, 否则返回true
for(let i = 1; i <= n; i++){
need[i] = need[i - 1] + d[i];
if(need[i] > r[i]) return false;
}
return true;
}
最后
看完这几个例提后是不是觉得二分其实也就这样,边界条件也没那么难处理. 好好背模版,好好背模版,好好背模版,重要的事情说三遍,希望以后碰到二分的题目可以直接秒杀!
题目均来自各大算法网站,acwing,洛谷,leetcode,侵权必删