如何在C++ STL multiset中通过二分查找获取首个小于等于指定值的元素

嘿，这个问题我太熟悉啦！先帮你捋清楚：我猜你大概率是想找最后一个小于等于x的元素（也就是最大的不超过x的元素）——毕竟如果是找「首个」小于等于x的，在默认升序排列的multiset里，只要第一个元素<=x，那它就是答案，否则就不存在，这显然没太大实际意义。接下来我就针对这个常用需求来解答，完全可以用标准库的函数实现，而且效率是O(log n)的二分查找级别哦！

核心思路：利用upper_bound反向推导 #

我们知道upper_bound(x)的作用是返回multiset中第一个大于x的元素的迭代器，那它的前一个元素，自然就是整个容器里最后一个小于等于x的元素啦！

不过要注意边界情况：如果upper_bound(x)返回的是容器的begin()迭代器，说明容器里所有元素都大于x，这时候就没有符合条件的元素了。

代码示例 #

#include <iostream>
#include <set>

int main() {
    // 初始化一个包含重复元素的multiset
    std::multiset<int> ms = {1, 3, 3, 5, 7, 7, 9};
    int x = 6;

    auto upper_it = ms.upper_bound(x);
    if (upper_it != ms.begin()) {
        // 向前移动一个迭代器，指向最后一个<=x的元素
        auto target_it = std::prev(upper_it);
        std::cout << "最后一个小于等于" << x << "的元素是：" << *target_it << std::endl;
        // 这里会输出5
    } else {
        std::cout << "容器中没有小于等于" << x << "的元素哦！" << std::endl;
    }

    return 0;
}

补充说明 #

• 如果x恰好存在于multiset中，upper_bound(x)会指向第一个大于x的元素，所以它的前一个就是最后一个等于x的元素，完全符合我们的需求。
• 因为multiset的迭代器是双向迭代器，所以std::prev()或者直接--upper_it都是合法操作，效果一致。
• 这种方法完全依赖标准库的有序容器特性，upper_bound本身就是基于二分查找实现的，所以效率很高，不用担心性能问题。

内容的提问来源于stack exchange，提问作者someone12321