【C++算法】二分算法、二分模板详解，四道例题带详细注释

本文主要是介绍【C++算法】二分算法、二分模板详解，四道例题带详细注释，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

@[toc]
1）整数二分
2）解二分题步骤
AcWing 789.数的范围
洛谷 P1873.EKO/砍树
洛谷 P1678.烦恼的高考志愿

2）浮点二分
AcWing 790. 数的三次方根

1）整数二分

有单调性的题目一定可以二分，但是用二分做的题目不一定拥有单调性。
二分的本质不是单调性，二分的本质是边界，两套模板如下：
套模板时经常容易出现边界问题，那么什么时候选择哪套模板？听了y总的思路后，结合我自己的想法，接下来解析两套模板：
首先想 $c h ec k$ 函数，再想如何更新区间，如果是 $l = mi d$ ，那么补上 $+ 1$ ，如果是 $r = mi d$ ，那么不需要补上 $+ 1$
① 如果答案在右边，比如：找最大值，或者最后一个出现的位置；那么 $l = mi d$ ，那么对立面就是 $r = mi d - 1$ ； $mi d = l + r + 1 >> 1$
② 如果答案在左边，比如：找最小值，或者第一个出现的位置；那么$ r=mid$，那么对立面就是 $l = mi d + 1$ ； $mi d = l + r >> 1$
对于第一种情况①，为什么要+1？可以想象一下，如果已经找到答案， $mi d = l = r$ ，那么 $mi d = l + r >> 1$ 就还是 $[l, r]$ ，又因为包含答案，所以再次更新结果还是 $[l, r]$ ，就会陷入死循环，也就是我们说的边界问题
注意：二分一定是有解的，不可能无解，无解永远是题目的无解而不是二分的无解。

// 答案在左边，能取到答案
int bsearch_1(int l,int r) {while(l<r) {int mid=l+r>>1;if(check(mid))r=mid; // [l,mid]elsel=mid+1; // [mid+1,r]}return l;
}// 答案在右边，能取到答案
int bsearch_2(int l,int r) {while(l<r) {// 如何理解这个+1,见上述解析int mid=l+r+1>>1;if(check(mid))l=mid; // [mid,r]elser=mid-1; // [l,mid-1]}return l;
}

2）解二分题步骤

题目中出现求最值，首先想到二分/贪心/动态规划等算法
题目具有单调性，则可以考虑用二分求解
分析使用哪个模板
1. 第一次出现，求第一个大于等于/大于/小于/小于等于某个数的数，求解最小值，说明答案在左边，用第一个模板
2. 最后一次出现，最后一个大于等于/大于/小于/小于等某个数的数，求解最大值，说明答案在右边，用第二个模板
写check函数

AcWing 789.数的范围

题目链接：789. 数的范围 - AcWing题库

在这里插入图片描述

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;// 题目描述: 
// 找数字的左端点:大于等于x的第一个位置,q[mid]>=x,更新:R=mid,L=mid+1,当l=r时,若q[r]!=x,说明第一个大于等于x的位置不是x,则找不到
// 找数字的右端点:大于等于x的最后一个位置,q[mid]<=x,更新:L=mid,R=mid-1,当l=r时,若q[r]!=x,说明最后一个大于等于xconst int N=1e5+10;
int n,m;
int q[N];int main() {cin>>n>>m;for(int i=0;i<n;i++) cin>>q[i];// m次询问while(m--) {int x;cin>>x;// 二分x的左端点int l=0,r=n-1; // 区间范围while(l<r) {int mid=l+r>>1;if(q[mid]>=x) r=mid;else l=mid+1;}if(q[r]==x) {// 存在左端点,输出cout<<r<<' ';// 继续找右端点,左端点继续从上一次搜索的终点开始找r=n-1;while(l<r) {int mid=l+r+1>>1;if(q[mid]<=x) l=mid;else r=mid-1;}cout<<r<<endl; // 输出一组解} else {cout<<"-1 -1"<<endl;	}}return 0;
}

洛谷 P1873.EKO/砍树

题目链接：[P1873 COCI 2011/2012 #5] EKO / 砍树 - 洛谷

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;// 解题思路: const ll N=1e6+10;
ll n,m; // n:树的数量,m:要的木材总长度
ll a[N]; // 存储树的高度// 如果有木头有这么多,就返回true
bool check(ll mid) {ll cnt=0;for(ll i=1;i<=n;i++) {if(a[i]-mid>0) {cnt+=a[i]-mid;}	}if(cnt>=m) return true;else return false;
}int main() {ll mmax=INT_MIN;cin>>n>>m;for(ll i=1;i<=n;i++) {scanf("%d",&a[i]);mmax=max(mmax,a[i]);}ll l=0; // 锯子最小高度为0,全切ll r=mmax; // 最高切完最大的这棵树,一棵都不切// 要找最大值,那么答案在右边,所以压缩左边界while(l<r) {ll mid=l+r+1>>1;if(check(mid)) {l=mid;} else {r=mid-1;}}cout<<l<<endl;return 0;
}

洛谷 P1678.烦恼的高考志愿

题目链接：P1678 烦恼的高考志愿 - 洛谷

#include<bits/stdc++.h>
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pair<int,int> PII;// 解题思路: 开ll不然过不了const ll N=1e5+5;
ll n,m;
ll a[N]; // 存储学校的分数线
ll b[N]; // 存储每个同学的估分int main() {cin>>n>>m;// n个学校,m个同学for(ll i=1;i<=n;i++) {scanf("%lld",&a[i]);	}for(ll i=1;i<=m;i++) {scanf("%lld",&b[i]);}sort(a+1,a+1+n);ll cnt=0;// 遍历所有同学for(ll i=1;i<=m;i++) {// 卫语言风格// 比最小值还小,跳过if(b[i]<=a[1]) {cnt+=abs(b[i]-a[1]);continue;}else if(b[i]>=a[n]) {cnt+=abs(b[i]-a[n]);continue;}ll l=1,r=n; // 边界是[1,n]while(l<r) {ll mid=l+r>>1;// 注意找第一个是答案在左边的问题,所以要压缩右边界// 找第一个大于等于b[i]的第一个学校的分数线a[l]// 那么最后一个小于b[i]的元素的下标就应该是a[l-1]if(a[mid]>=b[i])r=mid;elsel=mid+1;}// 取二者之中的最小值cnt+=min(abs(a[l]-b[i]),abs(a[l-1]-b[i]));}cout<<cnt;return 0;
}

2）浮点二分

AcWing 790. 数的三次方根

题目链接：790. 数的三次方根 - AcWing题库

对于开二次方根，因为开出来一定是正数，所以可以设置 $l = 0$ ， $r = x$ ，但是三次方根可能有负数，不能单纯的取 $l = - x$ ， $r = x$ ，这样的话输入的 $x$ 是正数，范围是 $[- x, x]$ ，输入的数是负数，范围是 $[x, - x]$ 就会出大问题。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int main() {double x;cin>>x;// 因为是开三次方根,所以要考虑负数的情况// 注意double l=-100000,r=100000;// 保留6位小数就1e-8(基于经验),同理保留4位就1e-6while(r-l>1e-8) {double mid=(l+r)/2;if(mid*mid*mid>=x)r=mid;elsel=mid;}cout<<setprecision(6)<<fixed<<l<<endl;return 0;
}