sort, binary_search, lower_bound & upper_bound
Scenario
You need to find the closest value to X in a massive sorted array. You write a custom binary search with `while (left <= right)`. After 30 minutes of debugging infinite loops and off-by-one errors, your interviewer tells you C++ has a 1-line function for this.
Which STL algorithm instantly solves the "closest value" binary search problem?
Mental model
`std::sort` is a highly optimized robot that organizes your bookshelf. `std::binary_search` just tells you "Yes" or "No" if a book exists. `std::lower_bound` is a librarian who walks you to the exact spot where a book is, or where it *should* be inserted if it's missing.
The `<algorithm>` header provides robust, heavily optimized implementations of common algorithms. `std::sort` is an O(N log N) hybrid sorting algorithm. For sorted ranges, the binary search family (`binary_search`, `lower_bound`, `upper_bound`) provides O(log N) lookups without writing manual loops.
Explanation
**1. std::sort**
`std::sort(vec.begin(), vec.end())` sorts elements in ascending order. It uses *IntroSort*: it starts with QuickSort, but if the recursion depth gets too deep, it switches to HeapSort to guarantee O(N log N) worst-case. For tiny sub-arrays, it switches to InsertionSort. You should *never* write your own sorting algorithm in production.
**2. The Binary Search Family**
These algorithms **require** the range to already be sorted. If it's not sorted, the result is undefined garbage.
- `std::binary_search`: Returns a simple `bool` (true if found, false if not).
- `std::lower_bound`: Returns an iterator to the **first element that is >=** the target.
- `std::upper_bound`: Returns an iterator to the **first element that is strictly >** the target.
If no such element exists in the container (i.e. the target is greater than all elements), both bounds safely return the `.end()` iterator.
**Real-world Engineering:**
`lower_bound` is incredibly powerful. It is used in databases to find insertion points for indexing, in game physics to find the nearest collision frame in a timeline, and in interviews to solve almost any "find the closest number" problem without writing manual `while` loops.
Code examples
Using lower_bound and upper_bound
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {10, 20, 20, 20, 30, 40};
// Find the first element >= 20
auto lb = std::lower_bound(vec.begin(), vec.end(), 20);
std::cout << "Lower bound index: " << (lb - vec.begin()) << '\n'; // Prints 1
// Find the first element strictly > 20
auto ub = std::upper_bound(vec.begin(), vec.end(), 20);
std::cout << "Upper bound index: " << (ub - vec.begin()) << '\n'; // Prints 4
// The number of 20s in the vector is simply the distance between them:
std::cout << "Count of 20s: " << (ub - lb) << '\n'; // Prints 3
return 0;
}Subtracting `vec.begin()` from the resulting iterator gives you the exact integer index. The range `[lb, ub)` perfectly encapsulates all instances of the target.
Key points
- lower_bound is >= : `lower_bound` is the most powerful search algorithm. It tells you exactly where an element is, or where it should be inserted to maintain order.
- Use member functions for trees: Always use `set.lower_bound()` or `map.lower_bound()` instead of the generic `<algorithm>` version to ensure O(log N) performance.
Common mistakes
- Using std::lower_bound on a std::set: `std::lower_bound(set.begin(), set.end(), val)` is a catastrophic performance bug. Because `set` iterators are not random-access, this generic algorithm will run in O(N) time. You MUST use the member function `set.lower_bound(val)`, which uses the tree structure to run in O(log N).
Recall questions
- What sorting algorithm does `std::sort` use under the hood?
- What is the exact difference between `lower_bound` and `upper_bound`?
- What happens if you run `std::binary_search` on an unsorted vector?
Questions & answers
A candidate is asked to find the first number greater than or equal to `X` in a sorted vector. They write `std::lower_bound(vec.begin(), vec.end(), X)`. What happens if all elements in the vector are strictly less than `X`?
The function will return the `vec.end()` iterator. This is why you must always check `if (it != vec.end())` before dereferencing the result of `lower_bound`.
Approach: Identify the boundary conditions and return values of standard search algorithms.
How can you use `lower_bound` and `upper_bound` to efficiently count the occurrences of a number in a sorted array?
You find the `lower_bound` (start of the duplicates) and the `upper_bound` (end of the duplicates). Subtracting the two iterators (`std::distance(lb, ub)`) gives the exact count in O(log N) time.
Approach: Combine boundary algorithms to extract ranges.