STL_算法_查找算法(binary_search、includes)
算法 查找 STL search Binary
2023-09-11 14:15:00 时间
C++ Primer 学习中。。。
简单记录下我的学习过程 (代码为主)
全部容器适用(O(log(n))) 已序区间查找算法
binary_search //二分查找。返回bool值,
includes //包括查找,返回bool值。
binary_search //二分查找。返回bool值,
includes //包括查找,返回bool值。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; /***************************************** //全部容器适用(O(log(n))) 已序区间查找算法 binary_search() //二分查找。返回bool值, includes() //包括查找,返回bool值。 *****************************************/ /************************************************************************************* std::binary_search 全部排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class ForwardIterator, class T> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value ); template <class ForwardIterator, class T, class Compare> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp ); //eg: template <class ForwardIterator, class T> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value ) { first = lower_bound(first,last,value); return (first!=last && !(value<*first)); } *************************************************************************************/ /************************************************************************************* std::includes 全部排序容器适用 algorithm -------------------------------------------------------------------------------------- template <class InputIterator1, class InputIterator2> bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 ); template <class InputIterator1, class InputIterator2, class Compare> bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp ); //eg: template <class InputIterator1, class InputIterator2> bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 ) { while (first1!=last1) { if (*first2<*first1) break; else if (*first1<*first2) ++first1; else { ++first1; ++first2; } if (first2==last2) return true; } return false; } *************************************************************************************/ bool myfunction (int i,int j) { return (i<j);} int main() { int myints[] = {1,2,3,4,5,4,3,2,1}; vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1 // using default comparison: sort (v.begin(), v.end()); cout << "looking for a 3... "; if (binary_search (v.begin(), v.end(), 3)) cout << "found!\n"; else cout << "not found.\n"; // using myfunction as comp: sort (v.begin(), v.end(), myfunction); cout << "looking for a 6... "; if (binary_search (v.begin(), v.end(), 6, myfunction)) cout << "found!\n"; else cout << "not found.\n"; cout<<endl; /**----------------------------------------------------------------------------------**/ int container[] = {5,15,10,25,20,35,30,50,45,40}; int continent[] = {40,30,20,10}; sort (container,container+10); sort (continent,continent+4); // using default comparison: if ( includes(container,container+10,continent,continent+4) ) cout << "container includes continent!" << endl; // using myfunction as comp: if ( includes(container,container+10,continent,continent+4, myfunction) ) cout << "container includes continent!" << endl; return 0; } /***** Output looking for a 3... found! looking for a 6... not found. container includes continent! container includes continent! */
相关文章
- 算法导论(Introduction to Algorithms )— 第十二章 二叉搜索树— 12.1 什么是二叉搜索树
- 【算法】【链表模块】两个单链表寻找交点
- C#,自平衡二叉查找树(AVL Tree)的算法与源代码
- C#,欧拉数(Eulerian Number)的算法与源代码
- C#,初学琼林(05)——二分法查找(binary search,二分法搜索)数组内指定值的算法与源代码
- C#,整数转为短字符串(Short string)的加解密算法与源代码
- 时间轮算法(TimingWheel)是如何实现的?
- 如何评价一个算法的效率--时空复杂度概念及常用查找、排序算法复杂度
- 排序算法--循环排序(CycleSort)的原理、排序思路、适用场景及代码示例
- 查找算法--线性查找、二分查找和三分查找的原理及适用场景
- 一文搞懂二分查找算法!
- C/C++ 排序&&查找算法(面试)
- 大数据挖掘建模案例分析:利用BP神经网络算法进行用户行为分析(一)
- 基于C++实现(控制台)查找类算法应用【100010504】
- iOS 排序算法总结、二分法查找
- 《Mahout算法解析与案例实战》一一3.2 K-Means算法
- 图像抠图Image Matting算法调研
- 剑指 Offer 26树的子结构(相关话题:对称性递归,在线算法)
- 【基础算法】排序 查找 算法
- 华为OD机试 - 删除指定目录(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -查找单入口空闲区域(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -找终点(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -整数对最小和(Java) | 机试题+算法思路+考点+代码解析 【2023】
- Kosaraju 算法查找强连通分支
- Python人工智能实例 │ 使用Haar级联进行人脸检测、使用CAMShift算法、光流法进行人脸追踪
- 秒懂算法 | 矩阵连乘问题
- 经常使用排序算法
- 二叉排序树查找算法代码
- 回溯算法
- 53数据结构与算法分析之---裴波那契查找
- 50数据结构与算法分析之---顺序查找
- leetcode算法26.删除有序数组中的重复项
- Oracle Id生成算法 —— 雪花算法