STL二分查找算法
2024-10-21 12:41:58
二分法检索又称折半检索,二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组(array)中,首先将给定值key与字典中间位置上元素的关键码(key)比较,如果相等,则检索成功;否则,若key小,则在字典前半部分中继续进行二分法检索;若key大,则在字典后半部分中继续进行二分法检索。 这样,经过一次比较就缩小一半的检索区间,如此进行下去,直到检索成功或检索失败。偶数个取中间2个其中任何一个作为中间元素。二分法检索是一种效率较高的检索方法,要求字典在顺序表中按关键码排序。
二分查找函数:binary_search()
头文件:
#include<algorithm>
或
#include<bits/stdc++.h>
binary_search:查找某个元素是否出现。
函数模板:binary_search(arr[],arr[]+size , indx)
参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
lower_bound:查找第一个大于或等于某个元素的位置。
函数模板:lower_bound(arr[],arr[]+size , indx):
参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
upper_bound:查找第一个大于某个元素的位置。
函数模板:upper_bound(arr[],arr[]+size , indx):
参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
废话不多说,直接上代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[]={12,45,3,98,21,7};
sort(a,a+6);//先进行排序
cout<<"result:"<<binary_search(a,a+6,12)<<endl;
cout<<"result:"<<binary_search(a,a+6,77)<<endl;
}
它的输出结果是:
result:1
result:0
接着是全部包含的代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[100]= {4,10,11,30,69,70,96,100};
int b=binary_search(a,a+9,4);//查找成功,返回值为1
cout<<"在数组中查找4,result"<<b<<endl;
int c=binary_search(a,a+9,40);//查找失败,返回值为0
cout<<"在数组中查找40,result:"<<b<<endl;
int d=lower_bound(a,a+9,10)-a;
cout<<"在数组中查找第一个大于等于10的位置,result:"<<d<<endl;
int e=lower_bound(a,a+9,101)-a;
cout<<"在数组中查找第一个大于等于101的位置,result:"<<e<<endl;
int f=upper_bound(a,a+9,10)-a;
cout<<"在数组中查找第一个大于10的位置,result:"<<f<<endl;
int g=upper_bound(a,a+9,101)-a;
cout<<"在数组中查找第一个大于101的位置,result:"<<g<<endl;
}
输出为:
在数组中查找4,result1
在数组中查找40,result:1
在数组中查找第一个大于等于10的位置,result:1
在数组中查找第一个大于等于101的位置,result:9
在数组中查找第一个大于10的位置,result:2
在数组中查找第一个大于101的位置,result:9
视频网址:https://www.bilibili.com/video/av26938209?p=58
最新文章
- [Fluent NHibernate]第一个程序
- MVC之前的那点事儿系列(7):WebActivator的实现原理详解
- PAT1075. PAT Judge
- sping配置文件中引入properties文件方式
- 生成静态页面的PHP类
- O(1)调度器的时间计算公式与CFS调度器
- css盒子模型,定位,浮动
- JSON 数字排序 多字段排序
- SQL每个月份的发生额都比101科目多的科目
- vs 插件
- 使用iptraf,ifstat查看网络流量
- css渲染(一) 字体和文本
- VC++开发AutoCAD 2018/objectARX 用向导新建项目无法新建的问题
- ElasticSearch Index操作源码分析
- MonkeyRunner测试工具小结
- ubantu服务器配置ss
- NPOI打印设置
- 外部点击链接,登陆后,直接跳转到该链接(过滤器 + Cookie实现)
- python基础学习6----字符串操作
- Android MediaScanner 总纲