C++ binary search with lower_bound
Find an insertion position and check whether it is a match.
C++
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
int main() {
std::vector<int> values{2, 4, 4, 8};
auto found = std::lower_bound(values.begin(), values.end(), 4);
if (found != values.end() && *found == 4) {
std::cout << (found - values.begin()) << '\n';
}
auto missing = std::lower_bound(values.begin(), values.end(), 5);
std::cout << (missing - values.begin()) << '\n';
assert(missing != values.end() && *missing == 8);
}Output
1 3
Explanation
For ascending sorted input, lower_bound returns the first position whose value is not less than the target, or end if none exists.
That position may be where a missing value should be inserted. Check both that the iterator is not end and that its value equals the target before reporting a successful search.
Explore the dry run
Guided walkthroughReady
1
#include <algorithm>2
#include <iostream>3
#include <vector>4
#include <cassert>5
int main() {6
std::vector<int> values{2, 4, 4, 8};7
auto found = std::lower_bound(values.begin(), values.end(), 4);8
if (found != values.end() && *found == 4) {9
std::cout << (found - values.begin()) << '\n';10
}11
auto missing = std::lower_bound(values.begin(), values.end(), 5);12
std::cout << (missing - values.begin()) << '\n';13
assert(missing != values.end() && *missing == 8);14
}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Create ascending input with duplicates. | values = [2, 4, 4, 8] | — | |
| Find the first element not less than 4. | found index = 1 | — | |
| The value is 4, so print its first index. | found index = 1 | 1 | |
| 5 is missing; its insertion position is before 8. | missing index = 3, *missing = 8 | 1 | |
| Print the insertion index, not a claim that 5 was found. | missing index = 3, *missing = 8 | 1 3 |
Cost and common mistakes
O(log n) comparisons and iterator steps for vector random-access iterators; O(1) additional storage in typical implementations.
- The range must be ordered consistently with the comparison.
- Never dereference end(). Library search internals may vary; the walkthrough explains its guaranteed results.
Try it yourself
Predict lower_bound for 9.
Reveal answer and reasoning
It returns end(), corresponding to insertion index 4. Do not dereference it.