How to Implement the Binary Search in C++

1. Implement the Binary Search Algorithm for the std::vector Container in C++
2. The Complexity Analysis of the Binary Search Algorithm

This article will explain how to implement the binary search algorithm in C++.

Implement the Binary Search Algorithm for the std::vector Container in C++

Search algorithms are fundamental subroutines utilized in most common problems, and it’s important to execute them in the most efficient ways. There are various types of search algorithms; some are tailored for special data structures, and some can be applied more generally.

Binary search is a divide-and-conquer type algorithm that should be used on a sorted array of keys. It’s often called a logarithmic search because of its worst-case performance, which we are going to overview later in the article.

You can describe binary search as the following: Once we have the sorted array of objects where the k key needs to be found, we should compare the given key to the middle element in the array. If the key is less than the element, it should be located in the left half of the array, or if it’s larger - we should look for it in the right half.

After we repeat this lookup process recursively on each smaller half-arrays, we will eventually find the position of the key or indicate that the key is not in the array. Even though we describe the algorithm as naturally recursive, it can be implemented using the iterative method, but we will focus on the recursive one.

The following example code generates a thousand random integers in the range of [1-1000] and stores them in the std::vector container. The vector is then sorted using the std::sort algorithm, and we declare another vector of nine integers to search for. Note that the searchVector wrapper function is used to call the recursive function binarySearch.

The latter checks if the first from two-position indices is more than the other; if so, the function returns. The return value -1 is used to indicate the not-found status for the given key. Next, the middle position is calculated and compared to the key, which returns the index value if true. Finally, we choose which part of the array needs to be searched and call the same function with the corresponding indices.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::default_random_engine eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  return EXIT_SUCCESS;
}

Output:

did not, found, found, did not, found, did not, found, did not, found,

The Complexity Analysis of the Binary Search Algorithm

Binary search has the O(log n) complexity, hence the alias name - logarithmic search. We can loosely estimate the running time of recursive algorithm implementations by analyzing the recurrence cost. Note that looking up the middle element is a constant time operation, and we need to traverse half of the array.

In the following program, we demonstrate the verification test for our binary search function using the STL std::sort algorithm. Keep in mind, though, this check is not a formal verification and just provides a fast test case during the algorithm implementation process to debug and analyze the code behavior.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  for (auto &item : vec2) {
    std::find(vec.begin(), vec.end(), item) != vec.end() ? cout << "found, "
                                                         : cout << "did not, ";
  }

  return EXIT_SUCCESS;
}

Output:

found, found, found, found, did not, did not, found, found, found,
found, found, found, found, did not, did not, found, found, found,