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

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

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

【说明】

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;
}


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

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

分享给朋友:

相关文章

C++中的逻辑与运算

样例#include<iostream> using namespace std; int main(){ cout<<(1&1)...

编写第一个C++程序

编写第一个C++程序

前面的文章介绍了Dev-C++的下载安装:【入门篇】>>> DEVC++下载、安装、简单使用 - 青少年编程知识记录 (codecoming.com)今天讲一下如何使用Dev-C++...

求阶乘的方法

1.普通求法#include<iostream> using namespace std; int main(){ int sum=1;...

C++整型的数据范围

数据类型标识符占字节数数值范围数值范围短整型short [int]2(16位)-32768~32767-2^15 到2^15  -1整型[long] int4(32位)-...

【数据结构】并查集1

【数据结构】并查集1

1.引入    对于一个集合S={a1, a2, …, an-1, an},我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm,我们希望能够快速确定...

【初级篇】函数(一)

【初级篇】函数(一)

0.函数的引入为什么要用函数呢?比较官方的说法是,过程的复用,你的一段逻辑,你有一段逻辑不断的在复用,就封装成函数去调用它。通俗的说法就是,把重复的过程集中到一块。例如,大家都学过如何求正方形的面积,...