算法基础课-基础算法-二分查找-数的范围

l=mid 需要补上加一

r=mid 不需要补上加一

789. 数的范围

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定一个按照升序排列的长度为 n� 的整数数组，以及 q� 个查询。

对于每个查询，返回一个元素 k� 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n� 和 q�，表示数组长度和询问个数。

第二行包含 n� 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 q� 行，每行包含一个整数 k�，表示一个询问元素。

输出格式

共 q� 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤1000001≤�≤100000
1≤q≤100001≤�≤10000
1≤k≤100001≤�≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

难度：简单

时/空限制：1s / 64MB

总通过数：173961

总尝试数：288546

来源：模板题,AcWing

算法标签

---

挑战模式

代码

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int a[N];int main()
{ios::sync_with_stdio(0);	cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=0;i<n;i++)	cin>>a[i];while(m--){int x;cin>>x;int l=0,r=n-1;while(l<r){int mid=(l+r)/2;if(a[mid]>=x)	r=mid;else	l=mid+1;}if(a[l]!=x)	cout<<"-1 -1 "<<endl;else{cout<<l<<" ";l=0,r=n-1;while(l<r){int mid=(l+r+1)/2;if(a[mid]<=x)	l=mid;else	r=mid-1;}cout<<l<<endl;}}return 0;
}

总结

1.假设check之后是l=mid，就需要补上加一，也就是mid=(l+r+1)/2

2.是因为后面最长上升子序列的优化那个题需要用到二分，自己不记得了，所以回来复习一下

3.每一次更新左右端点，最需要注意的问题就是第一点

4.check是一个判断标准，比如这个题目，是一个升序的数列，我们就check中间的数字是不是比我们要查询的数字大，这是用来二分查找左边界，中间的数字是不是比要查询的数字小，这是用来二分右边界

5.第一点加一是为了防止死循环，比如说，,l=mid,l=r-1,mid=(l+r)/2=(2r-1)/2=r-1,l=mid=r-1,发生了死循环，程序出现错误

6.总结就是要多复习，不要怕麻烦，要多敲代码，多反思总结，多练习多思考

7.以上是整数二分