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

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.以上是整数二分