789. 数的范围
题意
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回
-1 -1
。
思路
- 分别找右边界和左边界
坑点
找右边界 —— 找大于目标值和大于等于目标值的情况
mid=(l+r)/2
cpp while(1) { int mid=(l+r)/2; if(l==r) { break; } if(num[mid]<k) { l=mid+1; }else{ r=mid; } }
- 假设
ans
在 $[l..r]$上- 有
mid = (l + r) / 2
向下取整r = mid
则r
始终向下取整l = mid +1
则 l 始终+ 1
- 两者一上一下直到相遇
- 找左边界 —— 找小于目标值和小于等于目标值的情况
mid=(l+r+1)/2
cpp while(1) { int mid=(l+r+1)/2; if(l==r) { break; } if(num[mid]>=k+1) { r=mid-1; }else{ l=mid; } }
- 假设
ans
在 $[l..r]$上- 有
mid = (l + r) / 2
向下取整r = mid -1
则r
始终- 1
l = mid
则l
始终向下取整- 两者都是向下 则无法相遇(死循环)
- 所以
l
需要向上- 则
mid
需要向上取整- 则有
mid = (l + r + 1) / 2
算法一:二分
时间复杂度
$O(qlogn)$
实现步骤
- 写两个二分
- 第一找大于等于 k 的第一个数
- 第二个找小于 k+1 的第一个数
- 并判断找到的两个数 是否都等于 k
代码
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int num[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++)
{
cin>>num[i];
}
while(q--)
{
int k;
cin>>k;
int l=0,r=n;
int x=0,y=0;
while(1)
{
int mid=(l+r)/2;
if(l==r)
{
break;
}
if(num[mid]<k)
{
l=mid+1;
}else{
r=mid;
}
}
x=l;
l=0;
r=n-1;
while(1)
{
int mid=(l+r+1)/2;
if(l==r)
{
break;
}
if(num[mid]>=k+1)
{
r=mid-1;
}else{
l=mid;
}
}
y=l;
if(num[x]!=num[y])
{
cout<<"-1 -1"<<endl;
}else{
cout<<x<<" "<<y<<endl;
}
}
return 0;
}
算法二:STL 二分函数
时间复杂度
$O(qlogn)$
实现步骤
- 同上
- 二分调用二分函数 lower_bound 和 upper_bound
代码
#include<bits/stdc++.h>
using namespace std;
int num[100005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
for (int i = 0; i < n; i ++ )
{
cin>>num[i];
}
while(q--)
{
//返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
int k;
cin>>k;
int l=lower_bound(num,num+n,k)-num;
if(l==n||num[l]!=k)
{
cout<<"-1 ";
}else{
cout<<l<<" ";
}
int r=upper_bound(num,num+n,k)-num;
if(r-1==n||num[r-1]!=k)
{
cout<<"-1"<<endl;
}else{
cout<<r-1<<endl;
}
}
return 0;
}
总结
二分模板题 适用于学习二分查找的两种区别