How to Use lower_bound in C++: Syntax and Examples

In C++, lower_bound is a standard library function that finds the first position in a sorted range where a given value can be inserted without changing the order. It returns an iterator pointing to the first element not less than the value. Use it with sorted containers like vectors to efficiently search insertion points.

Syntax

The lower_bound function is used with iterators to specify the range to search. It has two common forms:

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

Here:

• first and last define the sorted range to search.
• value is the value to find the insertion point for.
• comp is an optional comparison function (like std::less<>).

cpp

auto it = std::lower_bound(first, last, value);
// or with custom comparator
auto it = std::lower_bound(first, last, value, comp);

Example

This example shows how to use lower_bound to find the position to insert a value in a sorted vector without breaking the order.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data = {10, 20, 30, 40, 50};
    int value = 35;

    auto it = std::lower_bound(data.begin(), data.end(), value);

    if (it != data.end()) {
        std::cout << "Lower bound for " << value << " is at index " << (it - data.begin()) << ", value: " << *it << "\n";
    } else {
        std::cout << "Value " << value << " would be inserted at the end." << std::endl;
    }

    return 0;
}

Output

Lower bound for 35 is at index 3, value: 40

Common Pitfalls

Common mistakes when using lower_bound include:

• Using it on an unsorted range, which leads to undefined or incorrect results.
• Confusing lower_bound with upper_bound (which finds the first element greater than the value).
• Not checking if the returned iterator is last before dereferencing.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> unsorted = {30, 10, 50, 20, 40};
    int value = 25;

    // Wrong: using lower_bound on unsorted vector
    auto it_wrong = std::lower_bound(unsorted.begin(), unsorted.end(), value);
    std::cout << "Wrong result (unsorted): " << (it_wrong != unsorted.end() ? std::to_string(*it_wrong) : "end") << "\n";

    // Correct: sort first
    std::sort(unsorted.begin(), unsorted.end());
    auto it_right = std::lower_bound(unsorted.begin(), unsorted.end(), value);
    std::cout << "Correct result (sorted): " << (it_right != unsorted.end() ? std::to_string(*it_right) : "end") << "\n";

    return 0;
}

Output

Wrong result (unsorted): 30
Correct result (sorted): 30

Quick Reference

lower_bound finds the first position where value can be inserted without breaking order in a sorted range.

• Input: sorted range [first, last), value to search
• Output: iterator to first element ≥ value
• Time complexity: O(log n)
• Use only on sorted containers

Function	Description
lower_bound(first, last, value)	Returns iterator to first element not less than value
upper_bound(first, last, value)	Returns iterator to first element greater than value
binary_search(first, last, value)	Returns true if value exists in sorted range

Key Takeaways

Use std::lower_bound on sorted ranges to find insertion points efficiently.

It returns an iterator to the first element not less than the given value.

Always ensure the range is sorted before calling lower_bound to get correct results.

Check if the returned iterator is not the end before dereferencing.

lower_bound runs in O(log n) time, making it faster than linear search.