STL二分算法

木杉乀

发布于 2021-12-08 13:55:50

6840

发布于 2021-12-08 13:55:50

文章目录
1.头文件
2.使用方法
1.binary_search：查找某个元素是否出现。(范围包括前, 不包括尾)
2.lower_bound：查找第一个大于或等于某个元素的位置。
3.upper_bound：查找第一个大于某个元素的位置。

1.头文件

#include <algorithm>

2.使用方法

1.binary_search：查找某个元素是否出现。(范围包括前, 不包括尾)

函数模板：普通数组: binary_search(arr[], arr[] + size, val)

vector: binary_search(arr.begin(), arr.end(), val)

binary_search(arr.begin(), arr.begin() + cnt, val)

函数功能：在数组中以二分法检索的方式查找，若在数组(要求数组元素升序)中查找到val元素则返回true，若查找不到则返回false。

如果数组是降序怎么办?

bool cmp(int a, int b) return a > b;

binary_search(arr.begin(), arr.end(), val, cmp);

重新定义二分规则

#include<bits/stdc++.h>
using namespace std;
vector<int>x = { 0, 2, 3, 3, 4, 5, 6, 9, 10, 11 };
vector<int>y = { 11, 10, 9, 6, 5, 4, 3, 3, 2, 0 };
vector<int>z = { 0, 2, 3, 3, 4, 5, 9, 7, 6, 11 };
bool cmp(int a, int b) { //从左往右找数组第一个小于等于val的
	return a > b;		 //规则是传入的val大于数组中的值, 但是函数要找第一个违反规则的
}
int main()
{
	for(int i = 0;i <= 11; i++)cout << binary_search(x.begin(), x.end(), i); 
	puts("      升序结果");
	for (int i = 0; i <= 11; i++)cout << binary_search(y.begin(), y.end(), i, cmp);
	puts("      降序+规则结果");
	for (int i = 0; i <= 11; i++)cout << binary_search(z.begin(), z.end(), i);
	puts("      半升序结果, 5之前满足升序可以正常判断, 后面部分都不能正常判断");
}

binary_search 算法底层实现

//第一种语法格式的实现
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
    first = std::lower_bound(first,last,val);
    return (first!=last && !(val<*first));
}
//第二种语法格式的底层实现
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& val, Compare comp)
{
    first = std::lower_bound(first, last, val, comp);
    return (!(first == last) && !(comp(val, *first)));
}

其使用的lower_bound() 查找第一个大于等于val的元素, 如果lower_bound() 返回值有解且等于val 那就找到了

这里传入的规则, 其实是传入给lower_bound()一个规则, 更改二分查找方式, 如果lower_bound()返回值有解, 并且结果不满足规则 (这里为什么是不满足规则, 是因为lower_bound函数就是找首个不满足规则的数据, 具体看后面)

2.lower_bound：查找第一个大于或等于某个元素的位置。

函数模板：普通数组: lower_bound(arr[], arr[] + size, val)

vector: lower_bound(arr.begin(), arr.end(), val)

lower_bound(arr.begin(), arr.begin() + cnt, val)

函数功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置

这里同样也只支持升序, 不支持降序数组

解决方法: 使用自定义规则

#include<bits/stdc++.h>
using namespace std;
vector<int>x = { 0, 2, 3, 3, 4, 5, 6, 9, 10, 11 };
vector<int>y = { 11, 10, 9, 6, 5, 4, 3, 3, 2, 0 };
vector<int>z = { 0, 2, 3, 3, 4, 5, 9, 7, 6, 11 };
bool cmp(int a, int b) { //从左往右找数组第一个小于等于val的
	return a > b;		 //规则是传入的val大于数组中的值, 但是函数要找第一个违反规则的
}
int main()
{
	for(int i = 0;i <= 11; i++)cout << lower_bound(x.begin(), x.end(), i) - x.begin();
	puts("      升序结果");
	for (int i = 0; i <= 11; i++)cout << lower_bound(y.begin(), y.end(), i, cmp) - y.begin();
	puts("      降序+规则结果");
	for (int i = 0; i <= 11; i++)cout << lower_bound(z.begin(), z.end(), i) - z.begin();
	puts("      半升序结果, 5之前满足升序可以正常判断, 后面部分不能正常判断");
}

3.upper_bound：查找第一个大于某个元素的位置。

函数模板：普通数组: upper_bound(arr[], arr[] + size, val)

vector: upper_bound(arr.begin(), arr.end(), val)

upper_bound(arr.begin(), arr.begin() + cnt, val)

函数功能：函数upper_bound()在first和last中的前闭后开区间进行二分查找，返回大于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置

upper_bound 和 lower_bound 区别: 前者仅大于, 后者则找大于等于

#include<bits/stdc++.h>
using namespace std;
vector<int>x = { 0, 2, 3, 3, 4, 5, 6, 9, 10, 11 };
vector<int>y = { 11, 10, 9, 6, 5, 4, 3, 3, 2, 0 };
vector<int>z = { 0, 2, 3, 3, 4, 5, 9, 7, 6, 11 };
bool cmp(int a, int b) { //从左往右找数组第一个小于val的
	return a >= b;		 //规则是传入的val大于等于数组中的值, 但是函数要找第一个违反规则的
}
int main()
{
	for(int i = 0;i <= 11; i++)cout << upper_bound(x.begin(), x.end(), i) - x.begin();
	puts("      升序结果");
	for (int i = 0; i <= 11; i++)cout << upper_bound(y.begin(), y.end(), i, cmp) - y.begin();
	puts("      降序+规则结果");
	for (int i = 0; i <= 11; i++)cout << upper_bound(z.begin(), z.end(), i) - z.begin();
	puts("      半升序结果, 5之前满足升序可以正常判断, 后面部分不能正常判断");
}

3. 关于STL二分底层与自定义规则详解!!

※※※※※※※※※※※※※※※※※※※※※※※这是重点内容※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

学会了这个, 才能真正会用, 熟练掌握STL二分算法函数

基础的规则分为4个

bool cmp1(int a, int b) { //从左往右找数组第一个小于等于val的
	return a > b;		  //规则是传入的val大于数组中的值, 但是函数要找第一个违反规则的
}
bool cmp2(int a, int b) { //从左往右找数组第一个小于val的
	return a >= b;		  //规则是传入的val大于等于数组中的值, 但是函数要找第一个违反规则的
}
bool cmp3(int a, int b) { //从左往右找数组第一个大于等于val的
	return a < b;		  //规则是传入的val小于数组中的值, 但是函数要找第一个违反规则的
}
bool cmp4(int a, int b) { //从左往右找数组第一个大于val的
	return a <= b;		  //规则是传入的val小于等于数组中的值, 但是函数要找第一个违反规则的
}

那么他们放到二分函数里是什么意义呢

以lower_bound为例, lower_bound(arr.begin(), arr.end(), val, cmp)

arr : 排好序的数组

val : 要查找的值

cmp : 自定义的规则

数组x : 0, 2, 3, 3, 4, 5, 6, 9, 10, 11 (纯升序)

数组y : 11, 10, 9, 6, 5, 4, 3, 3, 2, 0 (纯降序)

y 为 x 的逆序

int main()
{
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(x.begin(), x.end(), i) - x.begin());
	puts("      升序  默认结果");
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(x.begin(), x.end(), i, cmp1) - x.begin());
	puts("      升序 模板1结果");
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(x.begin(), x.end(), i, cmp2) - x.begin());
	puts("      升序 模板2结果");
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(x.begin(), x.end(), i, cmp3) - x.begin());
	puts("      升序 模板3结果");
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(x.begin(), x.end(), i, cmp4) - x.begin());
	puts("      升序 模板4结果");
}

可以明显发现一些特点

默认结果与模板3结果相同, 其都是查找第一个大于等于val的位置
模板4结果与默认结果略有偏差, 其查找第一个大于val的位置
模板1和模板2结果明显错误, 其不能用于查找升序数组

下面是用upper_bound() 产生的结果, 和上面除了默认不同, 其余都是一样的

假如换上降序的数组y呢???

int main()
{
	for (int i = 0; i <= 11; i++)printf("%3d", upper_bound(y.begin(), y.end(), i) - y.begin());
	puts("      降序  默认结果");
	for (int i = 0; i <= 11; i++)printf("%3d", upper_bound(y.begin(), y.end(), i, cmp1) - y.begin());
	puts("      降序 模板1结果");
	for (int i = 0; i <= 11; i++)printf("%3d", upper_bound(y.begin(), y.end(), i, cmp2) - y.begin());
	puts("      降序 模板2结果");
	for (int i = 0; i <= 11; i++)printf("%3d", upper_bound(y.begin(), y.end(), i, cmp3) - y.begin());
	puts("      降序 模板3结果");
	for (int i = 0; i <= 11; i++)printf("%3d", upper_bound(y.begin(), y.end(), i, cmp4) - y.begin());
	puts("      降序 模板4结果");
}

可以明显发现一些特点

模板1结果查找第一个小于val的位置
模板2结果查找第一个小于等于val的位置
模板1和模板2, 默认结果结果明显错误, 其不能用于查找升序数组

诶??? 是不是不太对, 怎么和模板表达的意思不一样, 不应该是模板1表示小于等于, 模板2表示小于才对

换成upper_bound试试

int main()
{
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(y.begin(), y.end(), i, cmp1) - y.begin());
	puts("      降序 模板1结果");
	for (int i = 0; i <= 11; i++)printf("%3d", lower_bound(y.begin(), y.end(), i, cmp2) - y.begin());
	puts("      降序 模板2结果");
}

这回就正确了

模板1结果查找第一个小于等于val的位置
模板2结果查找第一个小于val的位置

**注意: ** 如果使用降序模板查找降序数组, 使用 lower

!!!关于自定义的规则为何代表了某个含义, 见自定义规则代码注释

a 代表二分函数中的 val

b 代表待查找的数组数据

4.如何用STL二分查找范围内的上界和下界

数组升序:

lower_bound(iter.begin(), iter.end(), x)寻找

*it\ge x

的下界，如果返回

iter.end()

说明无解 upper_bound(iter.begin(), iter.end(), x)寻找

*it> x

的下界，如果返回

iter.end()

说明无解 lower_bound(iter.begin(), iter.end(), x) - 1寻找

*it< x

的上界，如果返回

iter.begin()-1

说明无解 upper_bound(iter.begin(), iter.end(), x) - 1寻找

*it\le x

的上界，如果返回

iter.begin()-1

说明无解

以数组 x : 0, 2, 3, 3, 3, 3, 6, 9, 10, 11 为例

int main()
{
	auto f1 = lower_bound(x.begin(), x.end(), 3) - x.begin();		// [3,+∞) 下界
	auto f2 = upper_bound(x.begin(), x.end(), 3) - x.begin();		// (3,+∞) 下界
	auto f3 = lower_bound(x.begin(), x.end(), 3) - 1 - x.begin();	// (-∞,3] 上界
	auto f4 = upper_bound(x.begin(), x.end(), 3) - 1 - x.begin();	// (-∞,3) 上界
	cout << f1 << " " << f2 << " " << f3 << " " << f4 << endl;
}

输出结果: 2 6 1 5

数组降序:

upper_bound(y.begin(), y.end(), 3, cmp1) - 1 upper_bound(y.begin(), y.end(), 3, cmp2) - 1 lower_bound(y.begin(), y.end(), 3, cmp1) lower_bound(y.begin(), y.end(), 3, cmp2)

以数组 y : 11, 10, 9, 6, 3, 3, 3, 3, 2, 0 为例

bool cmp1(int a, int b) { //从左往右找数组第一个小于等于val的
	return a > b;		  //规则是传入的val大于数组中的值, 但是函数要找第一个违反规则的
}
bool cmp2(int a, int b) { //从左往右找数组第一个小于val的
	return a >= b;		  //规则是传入的val大于等于数组中的值, 但是函数要找第一个违反规则的
}

int main()
{
	auto f1 = upper_bound(y.begin(), y.end(), 3, cmp1) - 1 - y.begin();	// [3,+∞) 下界
	auto f2 = upper_bound(y.begin(), y.end(), 3, cmp2) - 1 - y.begin();	// (3,+∞) 下界
	auto f3 = lower_bound(y.begin(), y.end(), 3, cmp1) - y.begin();		// (-∞,3] 上界
	auto f4 = lower_bound(y.begin(), y.end(), 3, cmp2) - y.begin();		// (-∞,3) 上界
	cout << f1 << " " << f2 << " " << f3 << " " << f4 << endl;
}

输出结果: 7 3 4 8

我是废物, 搞了好久, 感觉里面有哪里不太对, 希望有大神能够仔细阅读, 帮助我解决难题

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

c++

登录后参与评论

0 条评论

热度