信息奥赛｜二分
知识点概览 🚀
- 二分查找（基础）
- 整数二分
- 浮点数二分
- 二分答案
知识点详解 🎥
二分查找（基础）
学习素材 ☘️
| 编号 | 视频内容 | 视频链接 | 平台 | UP主 | 推荐指数 |
|---|---|---|---|---|---|
| 1 | 区间判断法 分析二分查找边界细节 | 链接1 | bilibili | 代码随想录 | 🌟🌟🌟🌟🌟 |
推荐学习路线 🚀
二分查找 的算法思想很容易理解，但是在书写具体代码时，有很多细节需要注意，如
- 初始值
right = n还是right = n-1 - 循环条件是
i<=j还是i<j - 在改变区间时，是
left = mid还是left=mid + 1…
视频 1 从 「区间合法性判断」 的角度，对上述细节问题做出了探讨，还是值得一看的。
二分查找模版 🧑🏻💻
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
Leetcode 704 - 二分查找：https://leetcode.cn/problems/binary-search/
int search(int* nums, int numsSize, int target){
int l = 0, r = numsSize - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}整数二分
学习素材 ☘️
| 编号 | 视频内容 | 视频链接 | 平台 | UP主 | 推荐指数 |
|---|---|---|---|---|---|
| 1 | 算法基础课——整数二分 | 链接1 | B站 | 大雪菜 | 🌟🌟🌟🌟🌟 |
推荐学习路线 🚀
整数二分 有两个具体的模版，观看 视频1 听 y总 讲解即可。
整数二分模版 🧑🏻💻
AcWing 整数二分模版：https://www.acwing.com/blog/content/31/
- 模版1：区间 $[l, r]$ 被二分成 $[l, mid]$ 和 $[mid + 1, r]$，且需要以区间 $[l, mid]$ 继续二分时使用
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 模版1：区间[l, r]被二分成[l, mid]和[mid + 1, r]，且需要以区间[l, mid]继续二分时使用
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
// 当mid满足时，若要继续往左找，答案区间从[l, r] -> [l, mid]
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}- 模版2：区间 $[l, r]$ 被二分成 $[l, mid+1]$ 和 $[mid, r]$，且需要以区间 $[mid, r]$ 继续二分时使用
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 模版2：区间[l, r]被二分成[l, mid+1]和[mid, r]，且需要以区间[mid, r]继续二分时使用
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
// 当mid满足时，若要继续往右找，答案区间从[l, r] -> [mid, r]
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}整数二分 OI案例 ✍️
【题目名称】查找
【题目描述】
输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。
【输入】
第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。
第二行 $n$ 个整数，表示这些待查询的数字。
第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。
【输出】
输出一行，$m$ 个整数，以空格隔开，表示答案。
【数据范围】
$1≤N≤300$
【输入样例】
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6【输出样例】
1 2 -1【数据范围】
数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$
本题输入输出量较大，请使用较快的 IO 方式。
【原题链接】
https://www.luogu.com.cn/problem/P2249
【题目分析】
本题是整数二分一个非常经典的问题，查找第一个 x 出现的下标，需要自己按照 y总 讲解的方法推导理解一下。
当然，本题也可以使用 STL 中的 lower_bound。 它的返回值是第一个大于等于 x 的迭代器，若要转化成下标，需要减去 v.begin()；若要转化成 第几个，则还要在下标的基础上 + 1。
比如对于 1 2 3 3 4 5
lower_bound(v.begin(),v.end(),3)会返回第一个 3 的迭代器lower_bound(v.begin(),v.end(),3) - v.begin()会返回第一个 3 的下标lower_bound(v.begin(),v.end(),3) - v.begin() + 1会返回第一个 3 在数组中是第几个数
【C++ 代码】
代码1：整数二分
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, m, x;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
while (m--) {
cin >> x;
int l = 1, r = n; //确定边界
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x) r = mid; //r = mid，模版1
else l = mid + 1;
}
//退出循环，l=r
if (a[l] != x) cout << "-1 ";
else cout << l << " ";
}
return 0;
}代码2：STL 中的 lower_bound
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, x, tmp;
vector<int> v;
vector<int>::iterator it;
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n >> m;
//将数据读入 vector中
for (int i = 1; i <= n; ++i) {
cin >> tmp;
v.push_back(tmp);
}
while (m--) {
cin >> x;
//lower_bound 返回指针，由于要求的下标是数值，故减去 v.begin()
//只有vector支持这样的减法
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
if (v[idx] != x) cout << "-1 ";
else cout << idx + 1 << " ";
}
return 0;
}浮点数二分
学习素材 ☘️
| 编号 | 视频内容 | 视频链接 | 平台 | UP主 | 推荐指数 |
|---|---|---|---|---|---|
| 1 | 算法基础课——浮点数二分 | 链接1 | B站 | 大雪菜 | 🌟🌟🌟🌟🌟 |
推荐学习路线 🚀
浮点数二分 相比 整数二分 更加简单一些，在理解 整数二分 的基础上，再去观看 视频1，基本就没问题了。
浮点数二分模版 🧑🏻💻
AcWing 浮点数二分模版：https://www.acwing.com/blog/content/277/
- 浮点数二分模版
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;
}浮点数二分 OI案例 ✍️
【题目名称】查找
【题目描述】
有函数：$f(x)=x^5−15x^4+85x^3−225x^2+274x−121$
已知 $f(1.5) \gt 0,f(2.4) \lt 0$ 且方程 $f(x)=0$ 在区间 $[1.5,2.4]$ 有且只有一个根，请用二分法求出该根。
【输入】
无
【输出】
该方程在区间 $[1.5,2.4]$中的根。要求四舍五入到小数点后 $6$ 位。
【数据范围】
无
【输入样例】
无
【输出样例】
无
【原题链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1241
【题目分析】
求 函数零点、数的平方根 等问题是 浮点数二分 一些非常经典的问题，在 观看视频1 后，只需要在理解模版的基础上使用模版即可。
🍉 PS：一般题目要求输出 6 位小数，则 l 与 r 的误差取 const double eps=1e-8，一般再往后两位。
🍉 PS2：慎用 C/C++ 的 pow 函数，有时候会有坑，详见其他博客。
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8; //定义误差
double f(double x); //定义函数
int main() {
double l = 1.5, r = 2.4;
while (r - l > eps) {
double mid = (l + r) / 2;
if (f(mid) <= 0) r = mid; //原函数在 [1.5,2.4] 递减
else l = mid;
}
cout << fixed << setprecision(6) << l << endl;
return 0;
}
double f(double x) {
return x * x * x * x * x - 15 * x * x * x * x + 85 * x * x * x - 225 * x * x + 274 * x - 121;
}二分答案
二分答案 是通过对答案的二分，来降低时间复杂度的算法，其前提是「二段性」。
二分答案这类题目在初学阶段会比较困难，初学者往往很难理解二分答案的过程。
但是这类题目存在一个「质变」过程，常常发生在做题或者思考的某个瞬间。在那个瞬间，会有种 拨云见日 的感觉，仿佛一下子理解了二分的本质，此后做这类题就会顺畅许多。
所以笔者的建议是照着题单多刷题（见文末「刷题题单」）、多理解（尤其是 check 函数怎么写，二分模版怎么选取等）让自己早日达到这个质变的瞬间。
刷题题单 🧑🏻💻
更多题目详见刷题题单
二分查找与整数二分：信息奥赛题单｜整数二分🔗 / （备用）信息奥赛题单｜整数二分🔗
浮点数二分：信息奥赛题单｜浮点数二分🔗 / （备用）信息奥赛题单｜浮点数二分🔗
二分答案：信息奥赛题单｜二分答案🔗 / （备用）信息奥赛题单｜二分答案🔗
如链接失效，可以在文章末尾选择上一篇博客 或 在搜索界面搜索关键词「二分」即可。
参考资料 📚
- 代码随想录 - 手把手带你撕出正确的二分法 - https://www.bilibili.com/video/BV1fA4y1o715/?share_source=copy_web&vd_source=33934722b558a5cefa750c1a9be72249
- AcWing算法基础课 - https://www.acwing.com/activity/content/11/
- AcWing代码模版 - https://www.acwing.com/blog/content/277/
- LeetCode - https://leetcode.cn/problemset/all/
