std::lower_bound(3)

💅 std::lower_bound(3) 💅

Okay bestie, gather 'round because we are about to stan one of the most iconic search algorithms in the entire C++ Standard Libary. This is std::lower_bound, and she is literally the moment. No cap. 🎀✨

---

✨ NAME ✨

std::lower_bound — she finds things. Iconically. 💅

---

🌸 SYNOPSIS 🌸

Defined in header <algorithm>, and let me tell you, she's been serving looks since forever but keeps getting glow-ups:

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                       const T& value );

(constexpr since C++20, until C++26) 👑

template< class ForwardIt, class T =
          typename std::iterator_traits<ForwardIt>::value_type >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                                 const T& value );

(since C++26) ✨

And the version with a custom comparator, because sometimes you need to do things your way:

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                       const T& value,
                       Compare comp );

(1) (constexpr since C++20, until C++26) 🦋

template< class ForwardIt, class T =
          typename std::iterator_traits<ForwardIt>::value_type,
          class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                                 const T& value, Compare comp );

(2) (since C++26) 🌈

---

💖 DESCRIPTION 💖

So here's the vibe: she's searching for the first element in the partitioned range [first, last) that is not ordered before value. Basically she's like "who's the first one here who isn't less than you?" and she finds them. Sorted. 🔥

🎀 Overload (1) — the operator< girlie (until C++20)

The order is determined by operator<:

She returns the first iterator iter in [first, last) where bool(*iter < value) is false, or last if no such iter exists.

⚠️ BESTIE LISTEN: If the elements elem of [first, last) are not partitioned with respect to the expression bool(elem < value), the behavior is UNDEFINED. That's not a vibe. Don't do that. 💀

🦋 Overload (1) — the glow-up (since C++20)

Equivalent to std::lower_bound(first, last, value, std::less{}). She's fancy now. Periodt. 💅

🌟 Overload (2) — the custom comparator era

The order is determined by comp:

She returns the first iterator iter in [first, last) where bool(comp(*iter, value)) is false, or last if no such iter exists.

⚠️ Same energy: if the elements elem of [first, last) are not partitioned with respect to the expression bool(comp(elem, value)), the behavior is UNDEFINED. Do not test her like that. 😭

---

🌸 PARAMETERS 🌸

• first, last — the partitioned range of elements to examine. Like, the whole squad she's checking out.
• value — the value to compare the elements to. The one. The target. The main character. 👑
• comp — a binary predicate which returns true if the first argument is ordered before the second. Here's what the signature of the predicate function should be equivalent to:

bool pred(const Type1 &a, const Type2 &b);

So like, while the signature doesn't need to have const &, the function must not modify the objects passed to it. She's not about that destructive energy. 🚫 And it must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category — thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11).

The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implicitly converted to Type2. Type requirements, but make it fashion. 💁‍♀️

---

🫶 TYPE REQUIREMENTS 🫶

• ForwardIt must meet the requirements of LegacyForwardIterator. She's gotta have that iterator energy.
• Compare must meet the requirements of BinaryPredicate. It is not required to satisfy Compare. Iykyk. ✨

---

👑 RETURN VALUE 👑

Iterator to the first element of the range [first, last) not ordered before value, or last if no such element is found.

That's it. That's the tea. 🍵

---

🔥 COMPLEXITY 🔥

Given N as std::distance(first, last):

• Overload (1): At most log₂(N)+O(1) comparisons with value using operator< (until C++20) or std::less{} (since C++20).
• Overload (2): At most log₂(N)+O(1) applications of the comparator comp.

💡 HOWEVER — and this is highkey important — if ForwardIt is not a LegacyRandomAccessIterator, the number of iterator increments is linear in N. Notably, std::map, std::multimap, std::set, and std::multiset iterators are not random access, and so their member lower_bound functions should be preferred. Use the member functions, bestie. They're right there. 🙈

---

🧚 POSSIBLE IMPLEMENTATION 🧚

See also the implementations in libstdc++ and libc++. But here's the vibe check in code form:

lower_bound (1)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    return std::lower_bound(first, last, value, std::less{});
}

lower_bound (2)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);

    while (count > 0)
    {
        it = first;
        step = count / 2;
        std::advance(it, step);

        if (comp(*it, value))
        {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }

    return first;
}

She's giving binary search realness. Literally algorithmic excellence. 🌟

---

💜 NOTES 💜

Even though std::lower_bound only requires [first, last) to be partitioned, this algorithm is usually used in the case where [first, last) is sorted, so that the binary search is valid for any value. That's the classic use case and honestly? She slays it. 💅

And here's a fun fact: unlike std::binary_search, std::lower_bound does not require operator< or comp to be asymmetric — that is, a < b and b < a always have different results. In fact, she doesn't even require value < *iter or comp(value, *iter) to be well-formed for any iterator iter in [first, last). Iconic flexibility. 🎀

🌈 Feature-test macro 🌈

You love to see it. Modernization. We stan progress. 😌

---

🌸 EXAMPLE 🌸

// Run this code

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>

struct PriceInfo { double price; };

int main()
{
    const std::vector<int> data{1, 2, 4, 5, 5, 6};

    for (int i = 0; i < 8; ++i)
    {
        // Search for first element x such that i ≤ x
        auto lower = std::lower_bound(data.begin(), data.end(), i);

        std::cout << i << " ≤ ";
        lower != data.end()
            ? std::cout << *lower << " at index " << std::distance(data.begin(), lower)
            : std::cout << "not found";
        std::cout << '\n';
    }

    std::vector<PriceInfo> prices{{100.0}, {101.5}, {102.5}, {102.5}, {107.3}};

    for (const double to_find : {102.5, 110.2})
    {
        auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find,
            [](const PriceInfo& info, double value)
            {
                return info.price < value;
            });

        prc_info != prices.end()
            ? std::cout << prc_info->price << " at index " << prc_info - prices.begin()
            : std::cout << to_find << " not found";
        std::cout << '\n';
    }

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = std::lower_bound(nums.cbegin(), nums.cend(), {2, 0}, cmpz);
    #else
        auto it = std::lower_bound(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz);
    #endif
    assert((*it == CD{2, 2}));
}

✨ Output ✨

0 ≤ 1 at index 0
1 ≤ 1 at index 0
2 ≤ 2 at index 1
3 ≤ 4 at index 2
4 ≤ 4 at index 2
5 ≤ 5 at index 3
6 ≤ 6 at index 5
7 ≤ not found
102.5 at index 2
110.2 not found

She ate and left no crumbs. 🔥👑

---

🎀 DEFECT REPORTS 🎀

The following behavior-changing defect reports were applied retroactively to previously published C++ standards. History was made, and she was part of it. 💅

• LWG 270 — C++98: Compare was required to satisfy Compare and T was required to be LessThanComparable (strict weak ordering required). Correct behavior: only a partitioning is required; heterogeneous comparisons permitted. She got an upgrade. ✨
• LWG 384 — C++98: At most log(N)+1 comparisons were allowed. Correct behavior: corrected to log₂(N)+O(1). Math but make it accurate. 🔢
• LWG 2150 — C++98: If any iterator iter exists in [first, last) such that bool(comp(*iter, value)) is false, std::lower_bound could return any iterator in [iter, last). Correct behavior: no iterator after iter can be returned. She's precise now. 🎯

---

(To be continued, bestie — part 2 is coming and it's gonna be even more iconic 💖)

✨ See also ✨

okay bestie, you ate that whole page, and now for the lil friends-and-family section 💖 these are the other pages you're gonna wanna keep in your orbit — the whole sorted-range squad, fr fr:

• equal_range — returns range of elements matching a specific key (function template) — bestie this one hands you the whole matching range, not just one end of it 🫶
• partition — divides a range of elements into two groups (function template) — the original group-chat splitter 😭
• partition_point (C++11) — locates the partition point of a partitioned range (function template) — finds where the vibes flip, no searching required
• upper_bound — returns an iterator to the first element greater than a certain value (function template) — the other half of the duo, the "strictly greater" girlie
• lower_bound — returns an iterator to the first element not less than the given key (public member function of std::set<Key,Compare,Allocator>) — yes queen, same name, but this one's a member of std::set 👑
• lower_bound — returns an iterator to the first element not less than the given key (public member function of std::multiset<Key,Compare,Allocator>) — and here she is again, this time living inside std::multiset 💅
• ranges::lower_bound (C++20) — returns an iterator to the first element not less than the given value (niebloid) — the shiny modern remix, and yeah, it's a niebloid, iconic terminology, iykyk ⭐

---

and that's a wrap on std::lower_bound, bestie 🎀 go forth and binary-search responsibly — remember, sorted range or it's giving undefined behaviour 💀

source: cppreference.com · version/date: 2024.06.10 · page: std::lower_bound(3) 🌸🦋✨