equal_range

c++

equal_range()是c++ STL中一种二分查找的方法。

头文件：#include <algorithm>

vecotor<int>nums; int val;
auto bounds = equal_range(nums.begin(), nums.end(), val);

equal_range()返回std::pair对象，其first和second成员都为迭代器，且分别指向输入序列中所有值等于 val 的元素所组成的子序列的起始及末尾（即最后一个元素之后的位置）位置。

first 成员的值等同于 std::lower_bound 执行于同一输入序列后的返回。

second 成员的值等同于 std::upper_bound 执行于同一输入序列后的返回。

如果(nums.begin(),nums.end())并未含“与value等同”的任何元素，以上叙述仍然合理，这种情况下，”与value等同”的所有元素形成的，其实是一个空区间，在不破坏次序的情况下，只有一个位置可以插入value，而equal_range所返回的pair，其first和second（都是迭代器）皆指向该位置。

if (bounds.first == bounds.second)
return{ -1, -1 };
return{ bounds.first - nums.begin(), bounds.second - nums.begin() - 1};

上述代码意思是说，如果nums中没有val，则返回[-1,-1];

如果nums中有val，则返回val元素的起始index和结束index。

例nums = {3,7,7,8,8,10},target = 8;则返回[3,4].

示例：

int main()
{
    vector<int> vec({1,2,3,3,3,5,5,6});
    //pair<vector<int>::const_iterator, vector<int>::const_iterator> pr;
    auto pr = equal_range(vec.begin(), vec.end(), 3);//3换成4/7
    cout<<"第一个等于 3 的下标 ："<<pr.first - vec.begin()<<endl;
	cout<<"第一个大于 3的下标 ： "<<pr.second - vec.begin()<<endl;
    system("pause");
    return 0;
}

IO:

第一个等于 3 的下标 ：2/5/8
第一个大于 3 的下标 ：5/5/8

原文地址：https://blog.csdn.net/qq_26079093/article/details/98479934