C++ STL常用算法-62-查找算法_binary_search/count/count

C++ STL常用算法-62-查找算法_binary_search/count/count_if

前面一篇学习了常用查找算法的三个方法，现在接着学习剩下三个查找相关的算法。binary_search，这个二分查找，在任何语言中都是重点需要掌握的，面试经常被考察。二分查找是一种解决问题的思想，在实际工作中排查错误，定位什么节点开始出现错误的，也是通过人工二分查找或者自动化脚本二分查找去定位。count是查找出现元素的个数，count_if是带条件查找统计结果的函数。

1.binary_search 二分查找

功能描述：
查找指定元素是否存在，返回布尔值类型

函数原型：bool binary_search(iterator beg, iterator end, value)；

注意事项：
查找指定的元素，查找到返回true，否则返回false
只能在有序序列中使用，也就是排好序才能使用二分查找算法

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void test01()
{
    vector<int> 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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void test01()
{
    vector<int> 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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class MyCount
{
public:
    bool operator()(int val)
    {
        return val > 20;
    }
};
void test01()
{
    vector<int> 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;
}