Двоичный поиск, чтобы найти меньшее или равное значение в мультимножестве 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(), что означает, что нет элементов, меньших или равных тому, что вы ищете.