二分法及相关题
二分法及例题
- 1，整数二分法模板
- 对应例题：数的范围
- 2，浮点数二分法模板
- 对应例题：数的三次方根
1，整数二分法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
//适合情况：满足该性质的范围在右边
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[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;
}作者：yxc
链接：/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
注： 有单调性的序列一定可以二分，但是二分不一定要求单调性，二分的本质不是单调性。
二分的本质是，如果可以找到一个性质，使得全部范围的一部分满足这个性质，另一部分不满足，那么二分法就可以用来寻找这个性质的边界~
二分法一定可以找到解，无解的情况都与题目限制有关。
对应例题：数的范围
题目链接: 数的范围.
参考题解链接: 一个较详细的清晰题解.
题目：
给定一个按照升序排列的长度为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
分析：
利用上面的模板，求出查询数的左右两个边界
代码：
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 100010;int n, q;
int p[N];int main()
{cin >> n >> q;for(int i =0; i < n; i ++) scanf("%d",&p[i]);while(q--){int k;scanf("%d", &k);int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if(p[mid] >= k) r = mid;else l = mid + 1;}if(p[l] != k) cout << "-1 -1" << endl;else{cout << l << " ";int l = 0, r = n - 1;while(l < r){int mid = l + r + 1 >> 1; //l = mid 时这里加一，是为了避免取到边界值陷入死循环if(p[mid] <= k) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}
2，浮点数二分法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l;
}
作者：yxc
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
对应例题：数的三次方根
题目链接: 数的三次方根.
浮点数二分比整数二分简单一些，没什么边界值，套模板做就 OK
题目：
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
代码如下：
#include <iostream>using namespace std;int main()
{double n;cin >> n;double l = -1000, r = 1000;//这里直接取一个大的范围，保证三次方根可以落在这个区间内。//假如说 n = 0.001，我们取左右边界的范围不能是 0-n，因为 0.1 不在这个范围内。可以取右边界为 max(n, 1)while(r - l > 1e-8)//这里是一个经验值，题目要求保留六位小数，一般取10^-8次方就可以保证达到精度{double mid = (l + r) / 2;if(mid * mid * mid >= n) r = mid;else l = mid;}printf("%lf",l);return 0;
}
二分法及相关题
二分法及例题
- 1，整数二分法模板
- 对应例题：数的范围
- 2，浮点数二分法模板
- 对应例题：数的三次方根
1，整数二分法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
//适合情况：满足该性质的范围在右边
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[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;
}作者：yxc
链接：/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
注： 有单调性的序列一定可以二分，但是二分不一定要求单调性，二分的本质不是单调性。
二分的本质是，如果可以找到一个性质，使得全部范围的一部分满足这个性质，另一部分不满足，那么二分法就可以用来寻找这个性质的边界~
二分法一定可以找到解，无解的情况都与题目限制有关。
对应例题：数的范围
题目链接: 数的范围.
参考题解链接: 一个较详细的清晰题解.
题目：
给定一个按照升序排列的长度为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
分析：
利用上面的模板，求出查询数的左右两个边界
代码：
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 100010;int n, q;
int p[N];int main()
{cin >> n >> q;for(int i =0; i < n; i ++) scanf("%d",&p[i]);while(q--){int k;scanf("%d", &k);int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if(p[mid] >= k) r = mid;else l = mid + 1;}if(p[l] != k) cout << "-1 -1" << endl;else{cout << l << " ";int l = 0, r = n - 1;while(l < r){int mid = l + r + 1 >> 1; //l = mid 时这里加一，是为了避免取到边界值陷入死循环if(p[mid] <= k) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}
2，浮点数二分法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r)
{const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l;
}
作者：yxc
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
对应例题：数的三次方根
题目链接: 数的三次方根.
浮点数二分比整数二分简单一些，没什么边界值，套模板做就 OK
题目：
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
代码如下：
#include <iostream>using namespace std;int main()
{double n;cin >> n;double l = -1000, r = 1000;//这里直接取一个大的范围，保证三次方根可以落在这个区间内。//假如说 n = 0.001，我们取左右边界的范围不能是 0-n，因为 0.1 不在这个范围内。可以取右边界为 max(n, 1)while(r - l > 1e-8)//这里是一个经验值，题目要求保留六位小数，一般取10^-8次方就可以保证达到精度{double mid = (l + r) / 2;if(mid * mid * mid >= n) r = mid;else l = mid;}printf("%lf",l);return 0;
}
发布评论