C++ <algorithm> - binary_search() Function

The C++ algorithm::binary_search function returns true if any element in the range [first,last) is equivalent to the specified value, else returns false. The elements are compared using operator< (in first version) or comp (in second version). The elements in the range should be already sorted using the same criterion (operator< or comp), or at least partitioned with respect to specified value.

Syntax

//equality version
template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

//predicate version
template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

Parameters

`first`	Specify initial position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`last`	Specify final position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`val`	Specify the value to be searched for in the range.
`comp`	Specify a binary function that accepts two element as argument (one element from the range as first, and val as second), and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second.

Return Value

Returns true if the specified value is found in the range, else false otherwise.

Time Complexity

On Average, Logarithmic i.e, Θ(log(n)).

Example:

In the example below, the algorithm::binary_search function is used to check whether the given element is present in the given range or not.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  vector<int> vec= {10, 60, 50, 30, 40, 20};
  vector<int>::iterator up, low;

  //sorting the vector
  sort(vec.begin(), vec.end());

  //search for 20 in vec
  bool retval1 = binary_search(vec.begin(), vec.end(), 20);

  if(retval1) {
    cout<<"20 is found in the range.\n";
  } else {
    cout<<"20 is not found in the range.\n";
  }

  //search for 25 in vec
  bool retval2 = binary_search(vec.begin(), vec.end(), 25);

  if(retval2) {
    cout<<"25 is found in the range.\n";
  } else {
    cout<<"25 is not found in the range.\n";
  }

  return 0;
}

The output of the above code will be:

20 is found in the range.
25 is not found in the range.

Example:

The example below shows how to use comp with algorithm::binary_search function.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mufunc (int i, int j) {
  return (i<j);
}

int main (){
  vector<int> vec= {10, 60, 50, 30, 40, 20};
  vector<int>::iterator up, low;

  //sorting the vector
  sort(vec.begin(), vec.end());

  //search for 45 in vec
  bool retval1 = binary_search(vec.begin(), vec.end(), 45, mufunc);

  if(retval1) {
    cout<<"45 is found in the range.\n";
  } else {
    cout<<"45 is not found in the range.\n";
  }

  //search for 60 in vec
  bool retval2 = binary_search(vec.begin(), vec.end(), 60, mufunc);

  if(retval2) {
    cout<<"60 is found in the range.\n";
  } else {
    cout<<"60 is not found in the range.\n";
  }

  return 0;
}

The output of the above code will be:

45 is not found in the range.
60 is found in the range.

❮ C++ <algorithm> Library