前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第三讲：二分【例题】
二分【习题】详见博客：蓝桥杯第三讲–二分【习题】
本篇博客所包含习题有：
👊数的范围
👊数的三次方根
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
二分
关于二分的模板，详细见博客：二分算法模板
二分的解题步骤如下：
- 找一个区间 [L, R]，使得答案一定在该区间中
- 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点
- 分析终点 M 在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间；
- 【本点只对整数二分有关，浮点数的二分只需前三点】如果更新方式写的是 R = Mid，则不用做任何处理；如果更新方式写的是 L = Mid，则需要在计算 Mid 时加上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
思路分析
模板题，不做解释，强调一点，当输入数据的范围 大于 1e5 的时候，建议使用 scanf printf，不要使用 cin cout，因为蓝桥杯是 OI 赛制，不要因为这种错误扣分。
代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 100010; int q[N]; int n, m; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); while (m -- ) { int k; scanf("%d", &k); int l = 0, r = n - 1; while (l < r) //先找左端点,左端点是第一个等于k的点 { int mid = l + r >> 1; if (q[mid] < k) l = mid + 1; else r = mid; } if (q[l] != k) puts("-1 -1"); else { printf("%d ", l); // 接下来找右端点 r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] > k) r = mid - 1; else l = mid; } printf("%d\n", r); } } return 0; }
数的三次方根
题目要求
题目描述：
给定一个浮点数 n，求它的三次方根。
输入格式：
共一行，包含一个浮点数 n。
输出格式：
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围：
−10000 ≤ n ≤ 10000
输入样例：
1000.00
输出样例：
10.000000
思路分析
模板题，不做解释，强调一点，本题要求保留 6 位小数，所以我们在二分的时候设置精度设置为 1e-8，即往后取2位精度，这个小细节很重要。
代码
#include <cstdio> #include <algorithm> #include <algorithm> using namespace std; int main() { double n; scanf("%lf", &n); double l = -10000, r = 10000; while (r - l > 1e-8) //保留6位小数,精度往后取2位 { double mid = (l + r) / 2; if (mid * mid * mid >= n) r = mid; else l = mid; } printf("%lf", l); return 0; }
