C++ STL二分查找std::binary_search()函数入门

前面一节我们学习了equal_range()函数，该函数的功能是在指定有序区间内查找第一个高于目标元素的元素。本节我们开始学习新的二分查找函数——binary_search()函数。“binary”意为“二分的”，“search”意为“查找”，binary_search()函数的功能是在指定有序范围内判断是否存在目标元素。

binary_search()函数的语法格式为：

/*查找 [first, last) 区域内是否包含val*/
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val); 
/*根据 comp 指定的规则，查找 [first, last) 区域内是否包含val*/
 bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

binary_search(first , last , val)函数指的是在指定有序区间[first , last)内二分查找目标元素，如果存在则返回bool值true；否则返回bool值false。

下面我们通过binary_search(first , last , val)来判断有序序列{1，2，3，4，5}是否存在目标元素3：

#include<iostream>
#include<vector>
#include<iterator> //使用distance()来获取下标 
#include<algorithm>//需包含算法头文件才能使用binary_search()函数
using namespace std;
  
/*binary_search(first , last , val)*/ 
void test()
{
    vector<int> v{1,2,3,4,5};
    cout << "原序列为：";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
    cout << '\n';
    /*通过binary_search(first , last , val)来判断有序序列{1，2，3，4，5}是否存在目标元素3*/ 
 if(binary_search(v.begin(),v.end(),3))//找到该区间 
 {
 cout << "有序序列存在目标元素【3】\n";
 }
} 
  
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

对于指定有序序列{1，2，3，4，5}，由于该序列包含元素3，因此binary_search(v.begin(),v.end(),3)函数会返回true，使得我们能看到屏幕输出3，输出完全符合我们的预期。

总结：binary_search() 函数能够在有序序列中快速判断指定元素是否存在，在蓝桥杯、ACM等算法竞赛上该函数主要应用于二分查询、预处理优化等。