Binary Search in C++

The standard library search functions covered in the previous lesson, like std::ranges::find are examples of linear search. In order to determine if our container contains the object we’re looking for, the algorithm needs to potentially check every single position in the container.

If our containers have many objects, or we’re doing the search frequently, this can affect performance. They’re referred to as examples of linear scaling, as how long they take to run scales in proportion to the number of objects in the container. If we double the number of objects, the algorithm takes twice as long to complete on average.

If our container is sorted, we can instead use binary search algorithms, which have better performance.

What is Binary Search?

Examples of binary searches that we do in the real world include looking for a word in a physical dictionary or searching through the index of a book.

Imagine we’re searching for the word “garden”. We can open the dictionary to a page somewhere around the middle. On that page, we check the first word, and find it to be “machine”. Given we know the dictionary is sorted in alphabetical order, we know that the word “garden” will be on one of the pages on the left. We can ignore the entire right side, cutting our search space in half.

We repeat this process on the remaining search space, ie the pages on the left. We open a page somewhere in the middle, check the first word, and use it to cut our problem in half again. After two lookups, the search space is now a quarter of its original size. We repeat this over and over and over until we find what we’re looking for.

This approach is an example of logarithmic scaling. If the dictionary is double the size, let's say from 1,000 to 2,000 pages, our search only takes one additional step. After the first lookup, we cut the search space down to 1,000 pages again.

As such, logarithmic scaling is much preferred to linear scaling

Implementing Binary Search with std::ranges::binary_search

The standard library’s binary search algorithms are available by including <algorithm>. In its most basic use, std::ranges::binary_search accepts two arguments:

1. The range to search
2. The value to search for

It returns a boolean value that is true if the object was found. Later in this lesson, we cover std::ranges::lower_bound, which we can use if we want to access the object that was found.

Below, we search our sorted vector for the number 4:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  bool Result{
9      std::ranges::binary_search(Numbers, 4)};
10
11  std::cout << "The object "
12            << (Result ? "was" : "was not")
13            << " found";
14}
15

1The object was found
2

Remember, our container needs to be sorted for binary search to be effective. Below, we try to use it on an unsorted container, and the incorrect result is returned:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{3, 2, 5, 4, 1};
7
8  bool Result{
9      std::ranges::binary_search(Numbers, 4)};
10
11  std::cout << "The object "
12            << (Result ? "was" : "was not")
13            << " found";
14}
15

1The object was not found
2

There is some nuance in what it means to be sorted. We go into that and explain how to change that meaning, later in the lesson

Custom Sort Behaviour

By default, the standard library binary_search algorithms expect our container to contain objects that implement the < operator, and for those objects to be sorted in ascending order. For example, if ObjectA < ObjectB, then ObjectA should be to the left of ObjectB.

However, the algorithms have an additional optional parameter, which we can use to pass a comparison function. That function defines how our objects are sorted. It accepts two objects of the same type in our container and returns true if the first argument comes before the second argument.

Below, we use it to communicate that our container is sorted in descending order:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{5, 4, 3, 2, 1};
7
8  auto GreaterThan{
9      [](int x, int y) { return x > y; }};
10
11  bool Result{std::ranges::binary_search(
12      Numbers, 4, GreaterThan)};
13
14  std::cout << "The object "
15            << (Result ? "was" : "was not")
16            << " found";
17}
18

1The object was found
2

This function allows us to define the sort order of objects that don’t even implement comparison operators. Below, we use it to search a collection of custom Character objects that are sorted alphabetically by their Name:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Character {
6  Character(const char* Name) : Name{Name} {}
7  std::string Name;
8};
9
10int main() {
11  std::vector<Character> Characters{
12      "Aragorn", "Frodo", "Gandalf", "Gimli",
13      "Legolas"};
14
15  auto Comparer{[](const Character& a,
16                   const Character& b) {
17    return a.Name < b.Name;
18  }};
19
20  bool Result{std::ranges::binary_search(
21      Characters, Character{"Legolas"},
22      Comparer)};
23
24  std::cout << "The object "
25            << (Result ? "was" : "was not")
26            << " found";
27}
28

1The object was found
2

std::ranges::lower_bound

Interestingly, when doing binary searches, the lower_bound function is often more useful than binary_search.

The two functions are closely related - lower_bound also accepts a sorted collection, a value to search for, and an optional comparison function.

It will use our comparison function (or the default < operator if we don’t provide one) to return an iterator. That iterator will point to the position where our element would be, if it was in our sorted container.

Below, we show an example where the element in that position is indeed equal to our target:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  auto Result{
9      std::ranges::lower_bound(Numbers, 4)};
10
11  std::cout
12      << "The number 4 would be in position "
13      << std::distance(Numbers.begin(), Result);
14
15  std::cout
16      << "\nThe element in that position is "
17      << *Result;
18}
19

1The number 4 would be in position 3
2The element in that position is 4
3

Here, we rerun the example with a target that is not in our container:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{2, 4, 6, 8, 10};
7
8  auto Result{
9      std::ranges::lower_bound(Numbers, 5)};
10
11  std::cout
12      << "The number 5 would be in position "
13      << std::distance(Numbers.begin(), Result);
14
15  std::cout
16      << "\nThe element in that position is "
17      << *Result;
18}
19

1The number 5 would be in position 2
2The element in that position is 6
3

It’s also possible that our element would be at the end of the container, in which case lower_bound will return a past-the-end iterator for our container. Dereferencing that would be dangerous, but we can test for it:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{2, 4, 6, 8, 10};
7
8  auto Result{
9      std::ranges::lower_bound(Numbers, 100)};
10
11  std::cout
12      << "The number 100 would be in position "
13      << std::distance(Numbers.begin(), Result);
14
15  if (Result == Numbers.end()) {
16    std::cout
17        << "\nThis is the end of the container";
18  }
19}
20

1The number 100 would be in position 5
2This is the end of the container
3

If lower_bound returns a past-the-end iterator, we can infer the container doesn't contain the object we're looking for.

Accessing the Object that was Found

The binary_search algorithms return a boolean representing whether or not the object was found. Our requirements may be slightly different - we possibly want access to the item that was found.

Sadly, the standard library doesn’t provide a direct function for that, but we can quickly build this using std::lower_bound.

std::lower_bound will return an iterator pointing to where the element would be. By inspecting that element, we can examine if we found what we’re looking for.

Remember, lower_bound can return a past-the-end iterator, so we should check for that before we dereference it:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7  int Target{4};
8
9  auto Result{std::ranges::lower_bound(Numbers,
10                                       Target)};
11
12  if (Result != Numbers.end() &&
13      *Result == Target) {
14    std::cout << "Object found: " << *Result;
15  } else {
16    std::cout << "Object not found";
17  }
18}
19

1Object found: 4
2

lower_bound with Comparison Functions

The previous example shows the simple case: we’re not using a comparison function and can compare our objects using the == operator. To adapt our previous example to support comparison functions, we need to clarify an important insight.

The comparison function we provide to binary_search and lower_bound will be given two objects. It will return true if the first argument is to the left of the second argument within our container.

We can use this to come up with another definition of equality from the perspective of our comparison function: two elements are equal if the comparison function returns false regardless of the order of the arguments. In other words, if a is not less than b, and b is not less than a, then a and b are equal.

When using a custom comparison function, lower_bound will return an iterator to the first object for which Comp(Object, Target) returns false. If we change the order of arguments and Comp(Target, Object) also returns false, we can infer Target and Object are equal.

Let's update our earlier example to use this:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Character {
6  Character(const char* Name) : Name{Name} {}
7  std::string Name;
8};
9
10int main() {
11  std::vector<Character> Characters{
12      "Aragorn", "Frodo", "Gandalf", "Gimli",
13      "Legolas"};
14  Character Target{"Legolas"};
15
16  auto Comparer{[](const Character& a,
17                   const Character& b) {
18    return a.Name < b.Name;
19  }};
20
21  auto Result{std::ranges::lower_bound(
22      Characters, Target, Comparer)};
23
24  if (Result != Characters.end() &&
25      !Comparer(Target, *Result)) {
26    std::cout << "Object found: "
27              << Result->Name;
28  } else {
29    std::cout << "Object not found";
30  }
31}
32

1Object found: Legolas
2

Using lower_bound to maintain sorted containers

The lower_bound algorithm returning an iterator to where an element would be in our sorted container has another useful property. When we want to add an element to our collection, and we want to maintain the sort order, lower_bound can give us the position we need to insert it.

We can then use our container-specific methods, like the insert function on std::vector to add our object to the correct place:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 5};
7  int NumberToInsert{4};
8
9  auto Position{std::ranges::lower_bound(
10      Numbers, NumberToInsert)};
11
12  Numbers.insert(Position, NumberToInsert);
13
14  std::cout << "Numbers: ";
15  for (auto Num : Numbers) {
16    std::cout << Num;
17  }
18}
19

1Numbers: 12345
2

Binary Search with Iterators

The ranges::binary_search and ranges::lower_bound algorithms uses the ranges feature, added in C++20.

We can omit the ranges component of our namespace, and use std::binary_search or std::lower_bound instead. Rather than accepting a range to search, they accept two iterators, denoting the beginning and end of what we want to search.

Below, we rewrite our first example to use std::binary_search instead:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  bool Result{std::binary_search(
9      Numbers.begin(), Numbers.end(), 4)};
10
11  std::cout << "The object "
12            << (Result ? "was" : "was not")
13            << " found";
14}
15

1The object was found
2