[problem:https://codeforces.me/contest/2254/problem/E

std::upper_bound vs set::upper_bound: The Hidden TLE Trap in C++

Many competitive programmers know that std::upper_bound runs in O(log n).

Many also know that std::set::upper_bound() runs in O(log n).

So naturally, this code should also be O(log n), right?

set<int> s = {1,2,3,4,5};

auto it = upper_bound(s.begin(), s.end(), 3);

Unfortunately...

Wrong.

This can easily turn an accepted solution into a TLE.

The Catch

The free algorithm

std::upper_bound(first, last, x)

works on Forward Iterators.

A std::set provides bidirectional iterators, not random-access iterators.

Binary search requires jumping to the middle quickly.

For vectors, this is easy:

mid = first + (last - first) / 2;

Both + and - are O(1).

For a set, however, there is no indexing.

To reach the middle, the algorithm repeatedly uses

std::advance(it, k);

which is O(k) for bidirectional iterators.

Although only O(log n) comparisons are made, moving the iterator costs linear time overall.

Hence

upper_bound(s.begin(), s.end(), x);

has complexity

O(n) on std::set.

The Correct Way

Always use the container member function.

auto it = s.upper_bound(x);

This directly navigates the Red-Black Tree and runs in

O(log n)

A Quick Comparison

The same applies to

• lower_bound
• equal_range
• binary_search

Example

Slow (can TLE)

set<int> s;

for (int i = 0; i < 200000; i++)
    s.insert(i);

for (int i = 0; i < 200000; i++) {
    auto it = upper_bound(s.begin(), s.end(), i);
}

Overall complexity becomes approximately

O(n²)

Fast

set<int> s;

for (int i = 0; i < 200000; i++)
    s.insert(i);

for (int i = 0; i < 200000; i++) {
    auto it = s.upper_bound(i);
}

Overall complexity

O(n log n)

Why Does std::upper_bound Even Accept Set Iterators?

The STL algorithms are written generically.

std::upper_bound only requires a Forward Iterator, so set iterators satisfy the requirements.

The Standard guarantees correctness—not optimal complexity.

If the iterator isn't random access, the algorithm still works, but iterator movement becomes linear.

Rule of Thumb

Whenever you're working with ordered associative containers:

• set
• multiset
• map
• multimap

Always use the member functions

container.lower_bound(x);
container.upper_bound(x);
container.equal_range(x);

instead of the generic STL algorithms.

Takeaway

The two functions have the same name but very different performance characteristics.

It's a tiny difference in syntax that can be the difference between Accepted and Time Limit Exceeded.

So the next time you're working with set or map, remember:

Generic algorithms are not always the fastest choice. Use the container's member functions whenever they exist.