首页 > 其他 > 详细

二分查找模板题及STL

时间:2020-02-09 19:37:31      阅读:121      评论:0      收藏:0      [点我收藏+]

题目来源:https://www.51nod.com/Challenge/Problem.html#problemId=2063

题目描述

输入一个整数n和n个整数,保证这n个整数已经按照从小到大进行排序。
然后输入一个整数q(q <= 100000)代表q次查询。接下来q行,每行含有一个整数m,代表一次查询。对于每次查询,使用二分查找判断m是否在之前输入的n个整数中出现过。如果出现,输出一行"Yes",否则输出"No"。

输入

第一行:一个整数n(n <= 100000)。
接下来n行,每行一个整数ai(1 <= ai <= 10^9)。
接下来一行,一个整数q。
接下来q行,每行输入一个整数x(1 <= x <= 10^9)。

输出

q行字符串,每行为"Yes"或"No"。

输入样例

5
1
3
4
5
7
3
4
5
0

输出样例

Yes
Yes
No

//方法一:手写bynary_seach
#include<bits/stdc++.h> using namespace std; const int max_n=1e5+10; int n, a[max_n], q, x; int main() { cin>>n; for(int i=0; i<n; i++) cin>>a[i]; cin>>q; for(int i=0; i<q; i++){ cin>>x; int low=0, high=n-1; bool f=0; while(low<=high){ int mid=high-(high-low)/2; if(a[mid]>x)high=mid-1; if(a[mid]<x)low=mid+1; if(a[mid]==x){ f=1; break; } } cout<<(f?"Yes":"No")<<endl; } return 0; }

 

//方法二:使用STL之bynary_seach()
#include<bits/stdc++.h>
using namespace std;
const int max_n=1e5+10;
int  n, a[max_n], q, x;
int main()
{
	cin>>n;
	for(int i=0; i<n; i++)
		cin>>a[i];
	cin>>q;
	for(int i=0; i<q; i++){
		cin>>x;
		int f=binary_search(a,a+n,x);
		cout<<(f?"Yes":"No")<<endl;
	}	
	return 0;
}

 

STL之二分查找:

https://blog.csdn.net/zwj1452267376/article/details/47150521

二分查找中的binary_search,lower_bound,upper_bound(手写详解):

https://blog.csdn.net/dl970220/article/details/80415798

C/C++-STL中lower_bound与upper_bound的用法:

https://blog.csdn.net/jadeyansir/article/details/77015626

二分查找模板题及STL

原文:https://www.cnblogs.com/tflsnoi/p/12288065.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!