当前位置:首页 > C++知识 > 正文内容

【STL】二分查找函数(算法)—binary_search

亿万年的星光4年前 (2022-03-12)C++知识1957

【说明】

binary_search() 实现了一个二分查找算法。它会在前两个参数指定范围内搜索等同于第三个参数的元素。指定范围的迭代器必须是正向迭代器而且元素必须可以使用 < 运算符来比较。这个序列中的元素必须被排成升序序列或者至少相对于所查找元素是有序的。如果找到第三个参数,这个算法会返回布尔值 true,否则返回 false。

【头文件】

<algorithm>

【语法格式】

语法格式一共有两种

1.  

//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val)

2.

//根据 comp 指定的规则,查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

其中,first 和 last 都为正向迭代器,[first, last) 用于指定该函数的作用范围;val 用于指定要查找的目标值;comp 用于自定义查找规则,此参数可接收一个包含 2 个形参(第一个形参值为 val)且返回值为 bool 类型的函数,可以是普通函数,也可以是函数对象。

需要注意的是,由于 binary_search() 底层实现采用的是二分查找的方式,因此该函数仅适用于“已排好序”的序列。所谓“已排好序”,并不是要求 [first, last) 区域内的数据严格按照某个排序规则进行升序或降序排序,只要满足“所有令 element<val(或者 comp(val, element)成立的元素都位于不成立元素的前面(其中 element 为指定范围内的元素)”即可。


【第一种模板】

binary_search(arr[],arr[]+size , indx)

arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
# include <cstdio>
# include <iostream>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
const int NR = 100;
int n = 6;
int a[50] = {0, 1, 5, 7, 9, 23, 60};
int main()
{
	cout << "a数组从a[1]到a[n]这n个数中有7吗?" << binary_search(a + 1, a + n + 1, 7) << endl;
	cout << "a数组从a[1]到a[n]这n个数中有12吗?" << binary_search(a + 1, a + n + 1, 12) << endl;
	cout << "a数组从a[1]到a[n]这n个数中有0吗?" << binary_search(a + 1, a + n + 1, 0) << endl;
	return 0;
}

【第二种模板】

第二种模板只做参考,很少用。

#include <algorithm>//adjacent_find的使用
#include<iostream>

using namespace std;
void main() {
	 //前面有小于的值
	 int value1[20] = { 20,10,15,22,69,70,96,100 };
	 //前面有大于的值
	 int value2[20] = { 69,70,96,100,22,20,10,15 }; 
	 //比较方法
	 auto predicate = [](int a, int b) 
	 {
		 return a > b; 
};
	int wanted{ 22 };//比较元素
	int conp1 = binary_search(value1, value1+8, wanted);//查询元素
	int conp2 = binary_search(value1, value1+8, wanted,predicate);//查询比较元素
	int conp3 = binary_search(value2, value2 + 8, wanted, predicate);//查询比较元素
	cout << "查询是否有"<< wanted <<"的值:" <<conp1 << endl
		<< "查询元素之前是否无小于" << wanted << "的值:" << conp2<<endl
		<< "查询元素之前是否无小于" << wanted << "的值:" << conp3<<endl;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

NOIP2013年普及组初赛题目及答案分析

NOIP2013年普及组初赛题目及答案分析

一、单项选择题1. 一个 32 位整型变量占用( A )个字节。 A. 4    B. 8      C. 32     &nbs...

【STL】二分查找函数 lower_bound 和 upper_bound

一、 lower_bound【功能】在数组a中从a[begin]开始到a[end - 1]按照cmp函数来比较进行二分查找第一个大于等于k的数的地址,如果有第一个大于等于k的数则返回该数的地...

【数据结构】并查集2

【数据结构】并查集2

上一篇文章,简单介绍了并查集。这篇文章,介绍一下并查集的改进以及优化。find函数的优化(路径压缩)因为并查集的merge操作:void merge(int a, int...

2021CSP-J/S全国晋级二轮分数线公布

普及组CSP-J序号省市CSP-J人数CSP-J晋级晋级比例最高分晋级最低分1甘肃13413399.25%86152宁夏10310198.06%65243天津46345197.41%8615.54云南...

【C++图形化编程】小游戏——打砖块(1)

【C++图形化编程】小游戏——打砖块(1)

0.前言这篇文章我们尝试创建一个打砖块的小游戏。1.游戏框架根据我们前面做的一些游戏的框架,这个小游戏的框架也可以分为下面这样的框架。int main() { startup();&n...

CSP-J2021年普及组复赛T2——插入排序

CSP-J2021年普及组复赛T2——插入排序

【题目描述】插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生,今天 H 老 师刚刚在上课的时候讲了插入排序算法。 假设比较两个元素的时间为 O(1),则插入排序可以以 O(n 2...