Learn the advantages and restrictions of Binary Search, and then implement it using the two main C++ standard library algorithms:

`std::binary_search`

and `std::lower_range`

Posted

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.

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

`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:

- The range to search
- 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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
bool Result{
std::ranges::binary_search(Numbers, 4)};
std::cout << "The object "
<< (Result ? "was" : "was not")
<< " found";
}
```

```
The object was found
```

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{3, 2, 5, 4, 1};
bool Result{
std::ranges::binary_search(Numbers, 4)};
std::cout << "The object "
<< (Result ? "was" : "was not")
<< " found";
}
```

```
The object was not found
```

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

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{5, 4, 3, 2, 1};
auto GreaterThan{
[](int x, int y) { return x > y; }};
bool Result{std::ranges::binary_search(
Numbers, 4, GreaterThan)};
std::cout << "The object "
<< (Result ? "was" : "was not")
<< " found";
}
```

```
The object was found
```

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`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct Character {
Character(const char* Name) : Name{Name} {}
std::string Name;
};
int main() {
std::vector<Character> Characters{
"Aragorn", "Frodo", "Gandalf", "Gimli",
"Legolas"};
auto Comparer{[](const Character& a,
const Character& b) {
return a.Name < b.Name;
}};
bool Result{std::ranges::binary_search(
Characters, Character{"Legolas"},
Comparer)};
std::cout << "The object "
<< (Result ? "was" : "was not")
<< " found";
}
```

```
The object was found
```

`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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
auto Result{
std::ranges::lower_bound(Numbers, 4)};
std::cout
<< "The number 4 would be in position "
<< std::distance(Numbers.begin(), Result);
std::cout
<< "\nThe element in that position is "
<< *Result;
}
```

```
The number 4 would be in position 3
The element in that position is 4
```

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

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{2, 4, 6, 8, 10};
auto Result{
std::ranges::lower_bound(Numbers, 5)};
std::cout
<< "The number 5 would be in position "
<< std::distance(Numbers.begin(), Result);
std::cout
<< "\nThe element in that position is "
<< *Result;
}
```

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

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{2, 4, 6, 8, 10};
auto Result{
std::ranges::lower_bound(Numbers, 100)};
std::cout
<< "The number 100 would be in position "
<< std::distance(Numbers.begin(), Result);
if (Result == Numbers.end()) {
std::cout
<< "\nThis is the end of the container";
}
}
```

```
The number 100 would be in position 5
This is the end of the container
```

If `lower_bound`

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

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
int Target{4};
auto Result{std::ranges::lower_bound(Numbers,
Target)};
if (Result != Numbers.end() &&
*Result == Target) {
std::cout << "Object found: " << *Result;
} else {
std::cout << "Object not found";
}
}
```

```
Object found: 4
```

`lower_bound`

with Comparison FunctionsThe 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:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct Character {
Character(const char* Name) : Name{Name} {}
std::string Name;
};
int main() {
std::vector<Character> Characters{
"Aragorn", "Frodo", "Gandalf", "Gimli",
"Legolas"};
Character Target{"Legolas"};
auto Comparer{[](const Character& a,
const Character& b) {
return a.Name < b.Name;
}};
auto Result{std::ranges::lower_bound(
Characters, Target, Comparer)};
if (Result != Characters.end() &&
!Comparer(Target, *Result)) {
std::cout << "Object found: "
<< Result->Name;
} else {
std::cout << "Object not found";
}
}
```

```
Object found: Legolas
```

`lower_bound`

to maintain sorted containersThe `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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 5};
int NumberToInsert{4};
auto Position{std::ranges::lower_bound(
Numbers, NumberToInsert)};
Numbers.insert(Position, NumberToInsert);
std::cout << "Numbers: ";
for (auto Num : Numbers) {
std::cout << Num;
}
}
```

```
Numbers: 12345
```

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
bool Result{std::binary_search(
Numbers.begin(), Numbers.end(), 4)};
std::cout << "The object "
<< (Result ? "was" : "was not")
<< " found";
}
```

```
The object was found
```

Posted

This lesson is part of theÂ course:### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.