# 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 {
}

//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 {
}

return 0;
}
```

The output of the above code will be:

```20 is 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 {
}

//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 {
}

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

5