当前位置:首页 > 题解目录 > 正文内容

【题解】二分法查找左边界

亿万年的星光2年前 (2024-03-20)题解目录2104




参考代码:

# include <bits/stdc++.h>
using namespace std;
int a[100005]; 
int n,m,x; //数组大小,要查找的数大小,每次要查找的数 
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	while(m--){
		cin>>x;
		int index=lower_bound(a+1,a+n+1,x)-a; //查找第一个大于等于m的位置 
		if(index==n+1){
			//没找到输出-1 
			cout<<-1<<" ";
		}else if(a[index]==x){
			//找到了,输出位置 
			cout<<index<<" "; 
		}else{
			//第一个大于但是不等于的情况也输出-1 
			cout<<-1<<" ";
		}
	} 
	return 0;
}


    扫描二维码推送至手机访问。

    版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

    分享给朋友:

    相关文章

    【题解】车厢调度

    【题解】车厢调度

    【题目描述】有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n<=1000)。分别按照顺序编号为1,2,3,...n。假定在...

    【题解】校运会

    【题解】校运会

    【题目描述】校运会上,一共有N个参赛选手,已知N个选手的名字。然后老师告诉你M句话,话的内容是学生A与学生B在同一组里。如果学生A与学生B在同一组里,学生B与学生C也在同一组里,就说明学生A与学生C在...

    【题解】开关灯(1)

    【题目描述】假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。第一个人(1号)将灯全部关闭,第二个人(2号...

    【题解】大整数乘法

    【题目描述】求两个不超过200位的非负整数的积。【输入描述】有两行,每行是一个不超过200位的非负整数,没有多余的前导0。【输出描述】一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342...

    【题解】高精度除法

    【题目描述】高精除以高精,求它们的商和余数。【输入描述】输入两个低于300位的正整数。【输出描述】输出商和余数。【样例输入】12313123184575776878979876423245678643...

    【题解】发工资

    【题目描述】作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵但是对于公司财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小李最近就在考虑一个问题:如果每...