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

骑猪看日落 2022-11-29 14:29 86阅读 0赞

前面一篇学习了常用查找算法的三个方法，现在接着学习剩下三个查找相关的算法。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;
    }

测试结果

![20200822093110482.png][]

数字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;
    }

代码运行结果：

![20200822130825650.png][]

**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;
    }

上面使用了仿函数，里面写了一个元素大于20的判断，也就是遍历过程中加上这个条件，找出元素大于20的元素出现次数

代码运行结果

![20200822131516906.png][]

上面明显只有元素30 和50大于20，所以结果是2

[20200822093110482.png]: /images/20221124/f84b9506eda64fcc88e725bb58aa4511.png
[20200822130825650.png]: /images/20221124/2a4f409763f842d1974b26f0bbe8e0b6.png
[20200822131516906.png]: /images/20221124/edfb0e2c0ebb41549b65fbca4e6bdb00.png