C++ STL 界限函数
2018-06-17 23:01:34来源:未知 阅读 ()
c++提供一类STL函数来实现对数组中元素的检索,其中较为简单且应用较广的是binary_search,upper_bound和lower_bound,它们都被包含在头文件#include<algorithm>中,用法如下:
//STL
//lower_bound与upper_bound
#include<iostream>
#include<algorithm>//包含这两个界限函数的头文件
#include<cstdio>
using namespace std;
int a[]={0,4,4,11,30,69,70,96,100},n=8,m,x,y,z,w;
void find_lower_bound(int aim)
{
int x=1,y=n,m;
while(x<y)
{
int m=x+(y-x)/2;
if(a[m]>=aim) y=m;
else x=m+1;
}
printf("\nlower_bound:%d",x);//因为最后x=y,所以输出x和输出y是一样的
}
void find_upper_bound(int aim)
{
int x=1,y=n,m;
while(x<y)
{
int m=x+(y-x)/2;
if(a[m]<=aim) x=m+1;
else y=m;
}
printf("\nupper_bound:%d",x);//同上
}
int main()
{
// std::ios::sync_with_stdio(false);//这句话用来加快cin和cout的速度,但使用后cin,cout不能与scanf,printf混用,所以慎用
// cin>>n;
// for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// sort(a+1,a+n+1);
// cin>>m;
x=lower_bound(a,a+n,3)-a;//要注意写法
y=upper_bound(a,a+n,4)-a;
z=binary_search(a,a+n,11);//判断是否存在,是返回真值
w=binary_search(a,a+n,3);//不存在则返回假值
printf("%d %d %d %d ",x,y,z,w);
find_lower_bound(3);//函数原型
find_upper_bound(4);//函数原型
return 0;
}
这里的函数原型其实是二分算法,注意两个函数的区别在于当a[m]=aim时到底是向前缩短区间还是向后缩短区间,这关系到最后x的取值。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash