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

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

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




参考代码:

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


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

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

分享给朋友:

相关文章

绝对素数

【题目描述】如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数。【输入描述】无【输出描述】所有二位绝对素数(由小到大,一个数一行)。【输入样例】无...

【题解】演讲大赛评分

【题目描述】最近"老王"很开心.他在大一的时候参加过数计学院的“软件小组”。告诉你个秘密,这个小组是个好地方,不但活动精彩而且有MM。 这不,这个小组举办了一个叫做“计算...

【题解】宴会

【题目描述】今人不见古时月,今月曾经照古人。梦回长安,大唐风华,十里长安花,一日看尽。 唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建 制度规划布局的特点是规...

【题解】均分蛋糕

【题目描述】小明今天生日,他有n块蛋糕要分给朋友们吃,这n块蛋糕(编号为1到n)的重量分别为a1, a2, …, an。小明想分给每个朋友至少重量为k的蛋糕。小明的朋友们已经排好队准备领蛋糕,对于每个...

【题解】切割绳子

【题目描述】有N条绳子,它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子,这K条绳子每条最长能有多长?答案保留到小数点后2位(直接舍掉2位后的小数)。【输入描述】第一行两个整数N和K(0&l...

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

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

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