整数二分
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| 洛谷 - P2249 | 查找 | 链接🔗 | 整数二分模版题 | 🟢 |
| AcWing - 789 | 数的范围 | 链接🔗 | 前缀和与差分 | 🟢 |
题解 🚀
查找
题目信息 📚
【题目名称】洛谷 P2249 - 查找
【题目描述】
输入 $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.end()）。
比如对于 1 2 3 3 4 5，查找 $x$
- 若 $x$ 存在，
lower_bound(v.begin(),v.end(),3)会返回第一个 $3(a[2])$ 的迭代器- 若要将其转化成下标，则需要减去
v.begin()lower_bound(v.begin(),v.end(),3) - v.begin()会返回第一个 $3(a[2])$ 的下标 2
- 若要转化成「第几个」，则还要在下标的基础上 $+1$。
lower_bound(v.begin(),v.end(),3) - v.begin() + 1会返回第一个 $3(a[2])$ 在数组中是第几个数
- 若要将其转化成下标，则需要减去
- 若 $x$ 不存在，
lower_bound(v.begin(),v.end(),3)返回v.end()
【C++ 代码】
#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;
}数的范围
题目信息 📚
【题目名称】数的范围
【题目描述】
给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询。
对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
【输入】
第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。
第二行包含 $n$ 个整数（均在 $1∼10000$ 范围内），表示完整数组。
接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。
【输出】
共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
【输入样例】
6 3
1 2 2 3 3 4
3
4
5【输出样例】
3 4
5 5
-1 -1【数据范围】
$1 \le n \le 100000$
$1 \le q \le 10000$
$1 \le k \le 10000$
【原题链接】
https://www.acwing.com/problem/content/791/
题目解析 🍉
【题目分析】
本题是整数二分一个非常经典的问题，理解并应用 y总 在算法基础课上讲解的二分模版即可（本题既要用到二分模版1，也要用到二分模版2，是个很不错的锻炼机会）
【C++ 代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N];
//整数二分
void bs(int x) {
int l = 1, r = n; //定义边界
//寻找第一个大于等于x的数
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= x) //需要寻找x，a[mid]要满足这一个性质，此时需要x在a[mid]左边，a[mid]要向左边的x靠近
r = mid; //模版1
else
l = mid + 1;
}
if (a[l] != x)
cout << "-1 ";
else
cout << l - 1 << " "; //原题下标从0开始
//寻找最后一个小于等于x的数
l = 1, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= x)
l = mid; //模版2，mid = l + r + 1 >> 1
else
r = mid - 1;
}
if (a[l] != x)
cout << "-1" << endl;
else
cout << l - 1 << endl; //原题下标从0开始
}
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;
bs(x); //二分
}
return 0;
}
