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

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

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




参考代码:

# 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;
}


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

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

分享给朋友:

相关文章

【算法】滑动窗口2—窗口大小可变

【算法】滑动窗口2—窗口大小可变

对于滑动窗口第二类:窗口大小可变类型 图解如下,类似双指针算法。【解题思想】1、字符串 S 中使用双指针的左右指针技巧,初始化 left = right = 0,把索引的...

【题解】感应门

【题目描述】感应门会在有人经过的时候自动打开,冷却d 秒后自动关闭。如果有人在感应门打开的状态下通过,那么冷却时间会重置,重新冷却d秒后再关闭。在一段时间内,有 n个人陆续通过了感应门,他们...

【题解】运动员和训练师的最大匹配数

【题目描述】给你一个下标从 0 开始的整数数组 players ,其中 players[i] 表示第 i 名运动员的&n...

【题解】前缀最大值

【题目描述】求一个数列的所有前缀最大值之和。即:给出长度为n的数列a[i],求出对于所有1<=i<=n,max(a[1],a[2],...,a[i])的和。比如,有数列:666 304 6...

【题解】最大平方因子

【题目描述】给定一个整数 n,请找出 n 的最大平方因子。所谓平方因子,就是一个 n 的因子,且是一个完全平方数。最大平方因子就是 n&nb...

【题解】01串

【题目描述】Fans是个ACM程序设计迷。有时侯,他表现出很强烈的逆反心理,你往东,他往西,你往南,他偏往北。这一次,不知道又是谁惹着他了,好端端的一个个01串,到了他的手里,都变成10串了。请你编个...