C++STL中的二分查找函数
2021/8/21 20:06:19
本文主要是介绍C++STL中的二分查找函数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前传
以前遇到二分答案的题目时都是手写二分,但关于一些左右区间、返回值等,错误还是比较多的,最近我在网络上发现STL中的二分函数实属方便快捷,于是我便总结了STL库中的二分函数,供大家学习参考。
binary_search函数
功能:查找某个元素是否出现
函数模板:binary_search(a[ ],a[ ]+size,num)
参数说明:
a[ ]:数组首地址 size:数组长度 num:所要查找的数字
返回值 :若num存在返回true,反之,返回false
注意:要求序列有序
例题1
题目:给定一个长度为n的序列a,查找x是否在序列中 (要求用二分)####
输入描述:第一行 输入n,x
接下来一行 输入序列a
输出描述:x存在输出"true",反之输出"false"
#include<bits/stdc++.h>//万能头额文件 #include <algorithm>//该函数头文件 //两个皆可 using namespace std; const int N=1e7+7; int n,x; int a[N]; int main(){ cin>>n>>x; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n)//将序列a的元素从小到大排序 if(!binary_search(a+1,a+1+n,x)) cout<<"false"; else cout<<"true"; return 0; }
lower_bound函数
功能:查找第一个大于或等于某个元素的位置
函数模板:lower_bound(a[ ],a[ ]+size,num)
参数说明:
a[ ]:数组首地址 size:数组长度 num:所要查找的数字
返回值 :第一个大于或等于num的元素的位置
注意:是在前闭后开的区间进行二分查找,且要求序列有序,若该元素不存在,则返回值大于最后一个元素的位置
例题2
题目:给定一个长度为n从小到大排序的序列a,查找第一个大于或等于x的元素的位置
输入描述:第一行 输入n,x
接下来一行 输入序列a
输出描述:若该元素存在输出该元素的位置,反之输出-1
#include<bits/stdc++.h>//万能头额文件 #include <algorithm>//该函数头文件 //两个皆可 using namespace std; const int N=1e7+7; int n,x; int a[N]; int main(){ cin>>n>>x; for(int i=1;i<=n;i++) cin>>a[i]; int ans=lower_bound(a+1,a+1+n,x)-a; if(ans<=n)//若该元素存在 cout<<ans; else cout<<-1; return 0; }
upper_bound函数
功能:查找第一个大于某个元素的位置
函数模板:upper_bound(a[ ],a[ ]+size,num)
参数说明:
a[ ]:数组首地址 size:数组长度 num:所要查找的数字
返回值 :第一个大于num的元素的位置
注意:是在前闭后开的区间进行二分查找,且要求序列有序,若该元素不存在,则返回值大于最后一个元素的位置
例题3
题目:给定一个长度为n从小到大排序的序列a,查找第一个大于x的元素的位置
输入描述:第一行 输入n,x
接下来一行 输入序列a
输出描述:若该元素存在输出该元素的位置,反之输出-1
#include<bits/stdc++.h>//万能头额文件 #include <algorithm>//该函数头文件 //两个皆可 using namespace std; const int N=1e7+7; int n,x; int a[N]; int main(){ cin>>n>>x; for(int i=1;i<=n;i++) cin>>a[i]; int ans=upper_bound(a+1,a+1+n,x)-a; if(ans<=n)//若该元素存在 cout<<ans; else cout<<-1; return 0; }
后记
好了,关于C++STL中的二分查找函数我就讲到这里了,希望对大家有所帮助
如果有什么问题或需要改进的可以在下方评论区留言
另外,这是本蒟蒻第一篇真正的博客,要记得点赞+收藏+关注欧
也希望大家可以 赞助 一下 Thanks(°∀°)=3谢谢啦
赞助
微信
这篇关于C++STL中的二分查找函数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享