算法模版：基础算法之二分法【沈七】

编程入门行业动态更新时间:2024-10-11 11:17:17

算法模版：基础算法之二分法【沈七】

算法模版：基础算法之二分法

前言
二分法
- 整数二分
- 小数二分
完结散花
参考文献

前言

唤我沈七就好啦。
有人戏言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;elsel=mid+1;}if(s[l]==x)cout<<l<<" ";elsecout<<"-1 ";r = n - 1 ;while(l< r){int mid = l + r + 1>>1;if(s[mid]<= x)l=mid;elser=mid-1;}if(s[l]==x)cout<<l<<"\n";elsecout<<"-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;elser=mid; }printf("%.2f",l);return 0;
}