std::lower_bound and std::upper_bound

lower_bound and upper_bound

---

Prerequisites

---

1. What are lower_bound and upper_bound?

They are STL algorithms used for binary search on sorted ranges. They work in O(log N) time

• lower_bound → first element ≥ value
• upper_bound → first element > value

#include <algorithm>

std::lower_bound(begin, end, value);
std::upper_bound(begin, end, value);

Example

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

int main()
{
    std::vector<int> v = {1, 2, 2, 2, 3, 4};

    auto lb = std::lower_bound(v.begin(), v.end(), 2);
    auto ub = std::upper_bound(v.begin(), v.end(), 2);

    std::cout << "lower_bound: " << *lb << "\n";
    std::cout << "upper_bound: " << *ub << "\n";
}

lower_bound → first 2
upper_bound → first 3

value = 2

[1, 2, 2, 2, 3, 4]
     ↑        ↑
     lb       ub

Function	Meaning
lower_bound	first ≥ value
upper_bound	first > value

1-1. Counting Duplicates

int count = ub - lb;

Number of occurrences of value

int count = std::upper_bound(v.begin(), v.end(), 2)
          - std::lower_bound(v.begin(), v.end(), 2);

1-2. Custom Comparator

std::lower_bound(v.begin(), v.end(), value, std::greater<int>());

Works with custom ordering

1-3. with Struct

struct Item
{
    int key;
};

std::vector<Item> v;

auto it = std::lower_bound(v.begin(), v.end(), 10,
    [](const Item& a, int value)
    {
        return a.key < value;
    });

1-4. Performance

• Time complexity: O(log N)
• Requires random access iterator for best performance

🧠 Insight

• On std::vector → fast
• On std::set → use member function instead

2. STL Containers Version

std::set<int> s;

auto it = s.lower_bound(10);

Better than std::lower_bound for tree containers

3. Real-World Patterns

✔️ Find insertion position

v.insert(std::lower_bound(v.begin(), v.end(), x), x);

✔️ Binary search existence

auto it = std::lower_bound(v.begin(), v.end(), x);

if (it != v.end() && *it == x)
{
    // found
}

✔️ Range query

auto start = std::lower_bound(v.begin(), v.end(), L);
auto end   = std::upper_bound(v.begin(), v.end(), R);