返回题解分享
讨论 / 题解分享/ 帖子详情

数的范围 - 题解

一种全新的思路来解决二分问题



不需要仔细思考边界问题

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,q;

const int N=100010;
int nums[N];
int front_find(int target){
	int l=-1,r=n;
	while(l+1!=r){
		int mid=l+r>>1;
		if(nums[mid]<target) l=mid;
		else r=mid;
	}
	if(r==n || nums[r]!=target) return -1;
	else return r;
}
int end_fond(int target){
	int l=-1,r=n;
	while(l+1!=r){
		int mid=l+r>>1;
		if(nums[mid]>target) r=mid;
		else l=mid;
	}
	if(l==-1 || nums[l]!=target) return -1;
	else return l;
}
void slove(){
	int target;
	cin>>target;
	int l=front_find(target);
	if(l!=-1){
		int r=end_fond(target);
		cout<<l<<" "<<r<<endl;
	}
	else cout<<"-1 -1"<<endl;
	
}
int main(){
	cin>>n>>q;
	for(int i=0;i<n;i++) scanf("%d",&nums[i]);
	while(q--) slove();

	return 0;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!