二分查找在 STL C++ 多重集中查找小于或等于的值

Question

我们有 STL（标准模板库）多重集，我们想要实现一个二分搜索，它将为我们提供与某个值 x 相比的第一个小于或等于的元素

从这篇文章：lower_bound == upper_bound中，我们看到我们可以使用标准的 lower_bound 和 upper_bound 来找到比 x 更大的值，或者找到更小的或等于的值。

可以做这样的事吗？

Answer 1

只需使用upper_bound的成员函数即可multiset。 upper_bound将返回大于您正在搜索的值的第一个元素。这意味着之前的迭代器将是等于或小于该值的第一个元素。所以在

int main()
{
    std::multiset<int> ms = {1,1,2,2,3,3,4,4,5,5};
    auto end = ms.upper_bound(3);
    for (auto it = ms.begin(); it != end; ++it)
        std::cout << *it;
}

它将打印，112233因为这是所有小于或等于 的元素3。

当然，您需要确保upper_bound不返回begin()，这意味着没有元素小于或等于您正在搜索的元素。