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

前面一节我们学习了upper_bound()函数，该函数的功能是在指定有序区间内查找第一个高于目标元素的元素。本节我们开始学习新的二分查找函数——equal_range()函数。“equal”意为“对等的”，“range”意为“范围”，equal_range()函数的功能是在指定有序范围内查找等于目标元素的元素范围，作用区间和upper_bound()函数一样都必须为有序区间，比如我们有一个有序序列{1，3，3，3，5}，通过数组的视角来看如果我们想要查找等于3的元素范围，那它的区间就是[1,4)。

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

equal_range()函数函数的语法格式为：
/*找到 [first, last) 范围中所有等于 val 的元素*/
 pairequal_range (ForwardIterator first, ForwardIterator last, const T& val);
/*找到 [first, last) 范围内所有等于 val 的元素*/
 pairequal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare
comp);

equal_range(first, last, val) 函数的功能是在指定有序区间 [first, last) 内找到等于目标元素的元素范围，返回类型为 pair<iterator, iterator>。如果找到相等的元素，则返回 {指向第一个相等元素的迭代器, 指向最后一个相等元素的下一个位置的迭代器}；如果没有找到相等的元素，则返回 {指向第一个大于 val 的元素迭代器, 指向第一个大于 val 的元素迭代器}，即两个迭代器相等，表示应该插入的位置。

下面我们通过equal_range(first, last,val)来查找有序序列{1，3，3，3，5}中元素==3的区间：

#include<iostream>
#include<vector>
#include<iterator> //使用distance()来获取下标 
#include<algorithm>//需包含算法头文件才能使用equal_range()函数
using namespace std;
  
/*equal_range(first, last,val)*/ 
void test()
{
    vector<int> v{1,3,3,3,5};
    cout << "原序列为：";
    for(auto it = v.begin();it!=v.end();++it)cout << *it << " ";
    cout << '\n';
    /*查找元素==3的范围*/ 
 pair<vector<int>::iterator,vector<int>::iterator> range =equal_range(v.begin(),v.end(),3);
 if(range.first!=range.second)//找到该区间 
 {
 cout << "在{1,3,3,3,5}找到元素==3的区间为：[" << distance(v.begin(),range.first)<< ","<<distance(v.begin(),range.second)<< ")\n" ;
 }
} 
  
int main(){
    system("title dotcpp.com");
    test();
    return 0;
}

编译结果如下：

对于有序序列{1，3，3，3，5}来说，以数组的视角来看元素==3的区间为[1,4)，输出完全符合我们的预期！

总结：equal_range(first, last,val)函数是有序数据范围查询的“利器”，在蓝桥杯、ACM等算法竞赛上该函数主要应用于统计重复元素、高效处理有序范围查询和离散化数据处理等。