前言
唤我沈七就好啦。
有人戏言90%的程序员都不能一次写对二分的程序。
这句话在学习二分的近一个月里，我真的是深有体会。
下面就来分享一下我这一个月的血泪经验。
还是那句话。
蒟蒻因为实在是太弱了，肯定免不了错误百出。
欢迎批评指正，期待共同成长！
二分法
整数二分
二分的本质是边界。
假设在一个区间上定义了某种性质，整个区间可以被一分为二，
使得这个性质在右半段区间满足而在左半段不满足。
二分可以寻找边界，既可以找到左半段的右边界a，也可以找到右半段的左边界b
l ab r
xxxxxxxxxoooooooooooooooooooo
找a
情况一：即寻找符合性质的第一个点
区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1;// >> 右移操作符，相等于 （l+r）/2 但>>的速度比 / 效率高的多 if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; }
找b
情况二：寻找符合性质的最后一个点
区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
问：这里 为什么是 mid = l + r + 1 >>1？
答：在这种情况中，如果mid = l + r>> 1 , 会陷入死循环。
所以只要牢记：
当 l = mid 时 ，mid = l + r + 1 >>1
当 r = mid 时 ，mid = l + r >>1
数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3 1 2 2 3 3 4 3 4 5
输出样例：
3 4 5 5 -1 -1
l a b r
1 2 2 3 3 3 4
求a
1.找一个判断条件，使得该判断条件使区间具有二段性，且答案一定是在该二段性的边界.
a是区间内大于等于x的分界，a是大于等于x的第一个数。
（a之前的数值均小于x）
2.分析中点mid在该判断条件下是否成立.
check(mid)>=x?r=mid:l=mid+1;
3.更新方式是r=mid,不做任何处理。mid=l=r>>1;
求b
1.找一个判断条件，使得该判断条件使区间具有二段性，且答案一定是在该二段性的边界.
b是区间内小于等于x的分界
（b之后的数值均大于x）
2.分析中点mid在该判断条件下是否成立.
check(mid)<=x?l=mid:r=mid-1;
3.更新方式是l=mid,mid需要加1,mid=l+r+1>>1.
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int s[N]; int main() { int n,m; cin>>n>>m; for(int i = 0 ; i < n ; i ++) cin>>s[i]; while(m--) { int x;cin>>x; int l = 0, r = n -1 ; while(l<r) { int mid = l+r>>1; if(s[mid]>=x) r=mid; else l=mid+1; } if(s[l]==x) cout<<l<<" "; else cout<<"-1 "; r = n - 1 ; while(l< r) { int mid = l + r + 1>>1; if(s[mid]<= x) l=mid; else r=mid-1; } if(s[l]==x) cout<<l<<"\n"; else cout<<"-1\n"; } return 0; }
小数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-8; // eps 表示精度，取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
问：为什么 i=mid 而不是 mid+1 的原因 ？
答：精度原因，答案有可能是 mid + 0.1
剪绳子
有 N 根绳子，第 i 根绳子长度为 L i，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。
题解部分
枚举 长度 x，判断是否能剪出 m 条 长度为 x 。
然后结合 二分的思想，优化枚举。
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; double a[N]; int n,m; bool check(double x) { int sum=0; for(int i =1 ; i <= n ; i ++) sum+=a[i]/x; return sum>=m; } int main() { cin>>n>>m; for(int i = 1 ; i <= n ; i ++) cin>>a[i]; double l=1,r=1e9; while(r-l>1e-3) { double mid = (l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2f",l); return 0; }
完结散花
ok以上就是对 基础算法之二分法 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
参考文献
https://www.acwing.com/activity/content/19/
