C++ · Course navigation

C++ binary search with lower_bound

Find an insertion position and check whether it is a match.

On this page

Before you start

Sorted vectors and iterators.

Find an insertion position and check whether it is a match.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <algorithm>

2#include <iostream>

3#include <vector>

4#include <cassert>

5int 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

Prepared trace of the published program. Some rows group repeated iterations.
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

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

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.