首页 > 编程语言 >二分查找相关题目(c++)

二分查找相关题目(c++)

时间:2024-06-08 13:59:22浏览次数:31  
标签:二分 数字 109 int bound 整数 a1 查找 c++

1.元素编号

输入 n 个单调不减的(就是后面的数字不小于前面的数字)非负整数a1​,a2​,…,an​​,然后进行 m 次询问。对于每次询问,给出一个整数 q,要求输出数列中第一个大于等于q的数字的编号。(若未找到则默认输出-1)

输入共 3 行:
第 1 行,2 个整数 n 和 m,表示数字个数和询问次数;
第 2 行,n 个整数,表示这些待查询的数字;
第 3 行,m 个整数,表示询问这些数字的编号,从 1 开始编号。

输出共 1 行:
m 个空格隔开的整数表示答案。

1≤n≤106;0≤a1​≤a2​≤⋅⋅⋅≤an​≤109;0≤q≤109;0≤m≤105。

AC代码如下:

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
	int n,m;
	cin >> n  >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int q;
		cin >> q;
		int l=1,r=n,ans=-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(a[mid]>=q)
			{
				ans=mid;
				r=mid-1;
			}
			else
			{
				l=mid+1;
			}
		}
		cout << ans << " ";
	}
	return 0;
}

1.1元素编号(lower_bound)

题目同上一题,解法不同用了STL库里的lower_bound函数

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
	int n,m;
	cin >> n  >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int q;
		cin >> q;
		int x=lower_bound(a+1,a+n+1,q)-a;
		cout << x << " ";
	}
	return 0;
}

2.值查找

输入 n 个单调不减的(就是后面的数字不小于前面的数字)非负整数a1​,a2​,…,an​,然后进行 m 次询问。对于每次询问,给出一个整数 q,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 -1 。

输入共 3 行:
第 1 行,2 个整数 n 和 m,表示数字个数和询问次数;
第 2 行,n 个整数,表示这些待查询的数字;
第 3 行,m 个整数,表示询问这些数字的编号,从 1 开始编号。

输出共 1 行:
m 个空格隔开的整数表示答案。

1≤n≤106;0≤a1​≤a2​≤⋅⋅⋅≤an​≤109;0≤q≤109;0≤m≤105 。

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
	int n,m;
	cin >> n  >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int q;
		cin >> q;
		int x=lower_bound(a+1,a+n+1,q)-a;
		if(a[x]==q)
		{
			cout << x << " ";
		}
		else cout << -1 << " ";
	}
	return 0;
}

3.查找元素

给定一个有 n 个元素按照升序排列的整数数组 a1​,⋅⋅⋅,an​,和一个目标值 target。找出给定目标值在数组中的开始位置(第一个),结束位置(最后一个)以及与目标值相同的元素个数。
如果数组中不存在目标值 target,输出 -1 -1 0。

输入共 2 行:
第 1 行,两个正整数 n,target;
第 2 行,n 个空格隔开的正整数a1​,a2​,⋅⋅⋅,an​。

输出共 1 行:
两个空格隔开的数据,给定目标值在数组中的开始位置和结束位置;
如果不存在,输出 -1 -1 0。

1≤n≤105;−109≤target,ai​≤109。

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main() 
{
	int n,t;
	cin >> n >> t;
	for(int i=1;i<=n;i++) cin >> a[i];
	int p1=lower_bound(a+1,a+n+1,t)-a;
	int p2=upper_bound(a+1,a+n+1,t)-a;
	if(p1!=p2)cout << p1  << " " << p2-1 << " " << p2-p1;
	else cout << "-1 -1 0";
	return 0;
}

这是我找到的关于二分查找的相关题目,希望能帮到你~~~

点个关注吧!!!

标签:二分,数字,109,int,bound,整数,a1,查找,c++
From: https://blog.csdn.net/2301_80279915/article/details/139545716

相关文章

  • 【C/C++】——小白初步了解——内存管理
    目录1.C/C++内存分布代码区(CodeSegment):数据区(DataSegment):堆区(Heap):栈区(Stack):常量区(ConstantSegment):2.C语言中动态内存管理方式1.malloc(size_tsize):2.calloc(size_tnmemb,size_tsize):3.*realloc(voidptr,size_tsize):4.*free(voidptr):3.C++中动态内......
  • C++:Traits编程技法在STL迭代器中的应用
    文章目录迭代器相应型别Traits(特性)编程技法——STL源代码门钥迭代器相应型别一:value_type迭代器相应型别二:difference_type迭代器相应型别三:reference_type迭代器相应型别四:pointer_type迭代器相应型别五:iterator_category以`advanced()`为例取消单纯传递调用的函数以`......
  • P10466 邻值查找 题解
    题目传送门前置知识二叉搜索树&平衡树解法笔者写这篇题解的时候题面应该是出锅了,建议去看Acwing的题面。第一问同luoguP2234[HNOI2002]营业额统计,平衡树维护前驱、后继(非严格意义上的)求出差值后取\(\min\)即可;第二问用map实现一个映射即可维护位置。代码#incl......
  • 【第四节】C/C++数据结构之树与二叉树
    目录一、基本概念与术语二、树的ADT三、二叉树的定义和术语四、平衡二叉树4.1解释4.2相关经典操作4.3代码展示一、基本概念与术语树(Tree)是由一个或多个结点组成的有限集合T。其中:1有一个特定的结点,称为该树的根(root)结点;2每个树都有且仅有一个特定的,称为......
  • c++各种字符串互转(char*、wchar_t*、CString、string、wstring、LPCWSTR)
    1//字符串转换宏2//简写意思:C:const,T:Cstring,W:wstring,A:string34//Cstring转wchar_t*:5wchar_t*p=cstr.AllocSysString()67//Cstring转string:str=CT2A(cstr)8#defineCSTR2STR(cstr)CT2A(cstr)910//Cstring转wstr......
  • C++全栈聊天项目(20) 聊天列表动态加载
    聊天列表动态加载如果要动态加载聊天列表内容,我们可以在列表的滚动区域捕获鼠标滑轮事件,并且在滚动到底部的时候我们发送一个加载聊天用户的信号boolChatUserList::eventFilter(QObject*watched,QEvent*event){//检查事件是否是鼠标悬浮进入或离开if(wat......
  • C++全栈聊天项目(21) 滚动聊天布局设计
    滚动聊天布局设计我们的聊天布局如下图最外层的是一个chatview(黑色),chatview内部在添加一个MainLayout(蓝色),MainLayout内部添加一个scrollarea(红色),scrollarea内部包含一个widget(绿色),同时也包含一个HLayout(紫色)用来浮动显示滚动条。widget内部包含一个垂直布局Vlayout(黄......
  • C++入门 初始化列表 & 隐式类型转换
    目录初始化列表构造函数体赋值初始化列表格式初始化列表特性每个成员变量在初始化列表中只能出现一次类中以下成员必须初始化尽量使用初始化列表初始化数组初始化 声明次序就是初始化顺序多参数初始化列表再谈隐式类型转换拷贝引用explicit关键字定义用法缺......
  • 【C++练级之路】【Lv.23】C++11——可变参数模板、lambda表达式和函数包装器
    快乐的流畅:个人主页个人专栏:《算法神殿》《数据结构世界》《进击的C++》远方有一堆篝火,在为久候之人燃烧!文章目录一、可变参数模板1.1参数包的概念1.2参数包的展开1.3emplace系列二、lambda表达式2.1lambda的格式2.2捕捉列表2.3lambda的原理2.4......
  • 类和对象(二)(C++)
    初始化列表classDate{public:Date(intyear,intmonth,intday){_year=year;_month=month;_day=day;}private:int_year;int_month;int_day;};虽然上述构造函数调用之后,对象中已经有了一个初......