【C++】STL 算法 - 查找算法 ( 查找两个相邻重复元素 - adjacent_find 函数 | 有序容器中通过二分法查找指定元素 - binary_search 函数 )
【C++】STL 算法 - 查找算法 ( 查找两个相邻重复元素 - adjacent_find 函数 | 有序容器中通过二分法查找指定元素 - binary_search 函数 )
一、查找两个相邻重复元素 - adjacent_find 函数
1、函数原型分析
在 C++ 语言 的 标准模板库 ( STL , STL Standard Template Library ) 中 , 提供了 adjacent_find 算法函数 用于 在 容器 中查找两个相邻的重复元素 ;
- 如果 找到 两个相邻的重复元素 , 则返回指向这对元素的第一个元素的迭代器 ;
- 如果 没有找到 两个相邻的重复元素 , 则返回指向序列末尾的迭代器 ;
adjacent_find 算法 函数 接受两个参数 , 表示 要搜索的 迭代器范围 的 起始迭代器 和 终止迭代器 , 这是一个 前闭后开 区间 ;
默认情况下 , 使用 重载 == 操作符函数 进行比较操作 , 即 operator==() 函数 ;
adjacent_find 算法 函数原型 如下 :
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); - 参数解析 :
- ForwardIterator first 参数 : 迭代器范围 的 起始迭代器 ( 包含该迭代器指向的元素 ) ;
- ForwardIterator last 参数 : 迭代器范围 的 终止迭代器 ( 不包含该迭代器指向的元素 ) ;
- 返回值解析 : 返回 指向 " 容器中 两个相邻的重复元素 的 第一个元素 " 的迭代器 ;
2、代码示例
在下面的代码中 ,
首先 , 创建 vector 容器 , 并对其初始化 ;
// 创建一个 set 集合容器
vector<int> myVector;
// 向容器中插入元素
myVector.push_back(9);
myVector.push_back(5);
myVector.push_back(2);
myVector.push_back(2);
myVector.push_back(7);然后 , 调用 adjacent_find 函数 , 将 vector 单端数组 容器的 begin 和 end 作为迭代器范围传入到函数中 ;
// 查找重复元素
auto it = adjacent_find(myVector.begin(), myVector.end());最后 , 在 9 5 2 2 7 元素中, 找到了重复元素 2 ;
9 5 2 2 7
查找到的重复元素 : 2
Press any key to continue . . .代码示例 :
#include "iostream"
using namespace std;
#include <vector>
#include <algorithm>
#include "functional"
int main() {
// 创建一个 set 集合容器
vector<int> myVector;
// 向容器中插入元素
myVector.push_back(9);
myVector.push_back(5);
myVector.push_back(2);
myVector.push_back(2);
myVector.push_back(7);
// 向 foreach 循环中传入 Lambda 表达式
for_each(myVector.begin(), myVector.end(), [](int a) {
std::cout << a << " ";
});
cout << endl;
// 查找重复元素
auto it = adjacent_find(myVector.begin(), myVector.end());
// 打印结果
if (it != myVector.end()) {
cout << "查找到的重复元素 : " << *it << endl;
}
else {
cout << "没有查找到重复元素"<< endl;
}
// 控制台暂停 , 按任意键继续向后执行
system("pause");
return 0;
};执行结果 :
9 5 2 2 7 查找到的重复元素 : 2 Press any key to continue . . .
二、有序容器中通过二分法查找指定元素 - binary_search 函数
1、函数原型分析
在 C++ 语言 的 标准模板库 ( STL , STL Standard Template Library ) 中 , 提供了 binary_search 算法函数 用于 在 有序元素的容器 中 使用二分法 查找 指定值的元素 ;
- 如果 找到 指定的元素 , 则返回 布尔值 true , 也就是 1 ;
- 如果 没有找到 指定的元素 , 则返回 布尔值 false , 也就是 0 ;
binary_search 算法 函数 接受三个参数 , 前两个表示 要搜索的 迭代器范围 的 起始迭代器 和 终止迭代器 , 这是一个 前闭后开 区间 ; 最后一个表示要搜索的值 ;
默认情况下 , 使用 重载 < 操作符函数 进行比较操作 , 即 operator<() 函数 ;
binary_search 算法 函数原型 如下 :
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); - 参数解析 :
- ForwardIterator first 参数 : 迭代器范围 的 起始迭代器 ( 包含该迭代器指向的元素 ) ;
- ForwardIterator last 参数 : 迭代器范围 的 终止迭代器 ( 不包含该迭代器指向的元素 ) ;
- const T& value 参数 : 要查找的元素 ;
- 返回值解析 : 返回 一个布尔值 , 表示 是否找到指定元素 ;
- 如果 找到 指定的元素 , 则返回 布尔值 true , 也就是 1 ;
- 如果 没有找到 指定的元素 , 则返回 布尔值 false , 也就是 0 ;
2、二分查找时间复杂度分析
二分查找 是 在已排序的数组中查找特定元素 , 时间复杂度 是 O(log n) ;
在 未排序的 序列中 , 查找特定元素 , 只能从头到尾进行遍历 , 时间复杂度是 O(n) ;
在 哈希表 中 , 查找元素 , 时间复杂度是 O(1) ;
在 二叉树 , 一般都是 平衡搜索树 中 , 查找的时间复杂度是 O(log n) ; 平衡搜索树 一般是 AVL 树 或 红黑树 ;
3、代码示例
代码示例 :
#include "iostream"
using namespace std;
#include <set>
#include <algorithm>
#include "functional"
int main() {
// 创建一个 set 集合容器
set<int> mySet;
// 向容器中插入元素
mySet.insert(9);
mySet.insert(5);
mySet.insert(2);
mySet.insert(2);
mySet.insert(7);
// 向 foreach 循环中传入 Lambda 表达式
for_each(mySet.begin(), mySet.end(), [](int a) {
std::cout << a << " ";
});
cout << endl;
// 通过二分法查找指定元素
auto isFind = binary_search(mySet.begin(), mySet.end(), 2);
// 打印结果
cout << "是否查找到指定元素 isFind = " << isFind << endl;
// 控制台暂停 , 按任意键继续向后执行
system("pause");
return 0;
};执行结果 :
2 5 7 9 是否查找到指定元素 isFind = 1 Press any key to continue . . .
