本文共 2304 字,大约阅读时间需要 7 分钟。
前面一篇学习了常用查找算法的三个方法,现在接着学习剩下三个查找相关的算法。binary_search,这个二分查找,在任何语言中都是重点需要掌握的,面试经常被考察。二分查找是一种解决问题的思想,在实际工作中排查错误,定位什么节点开始出现错误的,也是通过人工二分查找或者自动化脚本二分查找去定位。count是查找出现元素的个数,count_if是带条件查找统计结果的函数。
1.binary_search 二分查找
功能描述:
查找指定元素是否存在,返回布尔值类型函数原型:bool binary_search(iterator beg, iterator end, value);
注意事项:
查找指定的元素,查找到返回true,否则返回false 只能在有序序列中使用,也就是排好序才能使用二分查找算法
#include#include #include #include using namespace std;void test01(){ vector v; for(int i = 0; i < 10; i++) { v.push_back(i); } // binary_search 二分查找 bool res1 = binary_search(v.begin(), v.end(), 6); cout << res1 << endl; bool res2 = binary_search(v.begin(), v.end(), 9); cout << res2 << endl; bool res3 = binary_search(v.begin(), v.end(), 11); cout << res3 << endl;}int main(){ test01(); system("pause"); return 0;}
测试结果
数字1表示true,数字0表示false
如果序列不是有序,先需要排序,例如利用sort()算法。
2.count 查找统计
统计元素个数
函数原型:int count(iterator beg, iterator end, value);
#include#include #include #include using namespace std;void test01(){ vector v; v.push_back(10); v.push_back(20); v.push_back(10); v.push_back(20); v.push_back(50); // count 统计元素出现次数 int res1 = count(v.begin(), v.end(), 10); cout << res1 << endl; int res2 = count(v.begin(), v.end(), 20); cout << res2 << endl; int res3 = count(v.begin(), v.end(), 60); cout << res3 << endl;}int main(){ test01(); system("pause"); return 0;}
代码运行结果:
3.count_if带条件查找统计
按条件统计出现次数
这个条件可以是一个仿函数或者一个回调函数
函数原型:count_if(iterator beg, iterator end, _pred);
#include#include #include #include using namespace std;class MyCount{public: bool operator()(int val) { return val > 20; }};void test01(){ vector v; v.push_back(10); v.push_back(30); v.push_back(10); v.push_back(20); v.push_back(50); // count_if 按条件查找统计元素出现次数 int res1 = count_if(v.begin(), v.end(), MyCount()); cout << res1 << endl;}int main(){ test01(); system("pause"); return 0;}
上面使用了仿函数,里面写了一个元素大于20的判断,也就是遍历过程中加上这个条件,找出元素大于20的元素出现次数
代码运行结果
上面明显只有元素30 和50大于20,所以结果是2
转载地址:http://lexws.baihongyu.com/