算法分析
根据递增性质一定可以使用二分法,先确定一个左端点,而确定左端点的下标后判定该处的值是否为输入的值,这题的关键在于左右端点的判定,根据左右端点的正确判定,从而写出正确的 mid
变化,从而根据模板写出相应的值
- 左端点的判定:
a[mid]>=x
: true
:r = mid
;-
false
:l = mid +1
区间划分为
[l, mid], [mid+1, r]
根据二分法的模板,此时不需要 +1,只有出现 mid-1
时才会 +1
- 如果左端点和输入值不相等的话,一定得到
a[l]!=x
,即判定 x 不在数组内,从而输出 -1, -1 - 右端点的判定:
a[mid]<=x
true
:l = mid
false
:r = mid - 1
- 区间划分为:
[l, mid-1],[mid, r]
完整代码
#include<iostream>
using namespace std;
const int N = 1e5+5;
int a[N];
int n, m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--)
{
int x; // 待寻找的数
cin>>x;
// 先确立一个左端点
int l = 1, r = n, mid;
while(l<r){
mid = l+r>>1;
if(a[mid]>=x) r = mid;
else l = mid + 1;
}
if(a[l]!=x)
cout<<"-1 -1"<<endl;
// 输出的 l-1 是因为 我的数组是 从 1 开始
else
{
cout<<l-1<<" ";
// 继续确立右端点
l = 1, r = n;
while(l<r)
{
mid = l+r+1 >>1;
if(a[mid]<=x) l = mid;
else r = mid - 1;
}
cout<<l-1<<endl;
}
}
}
利用已有函数
lower_bound(val):
返回容器中第一个值【大于或等于】val
的元素的iterator位置。
upper_bound(val):
返回容器中第一个值【大于】val
的元素的iterator位置。
#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
while(m--)
{
int l,r,k;
cin>>k;
l=lower_bound(a,a+n,k)-a,r=upper_bound(a,a+n,k)-a;
if(l^r)printf("%d %d\n",l,r-1);
else puts("-1 -1");
}
}