Home » C++ STL

std::binary_search() in C++

In this article, we are going to see C++ STL function binary_search() which uses the standard binary search algorithm to search an element within a range.
Submitted by Radib Kar, on July 15, 2020

binary_search() as a STL function

Syntax:

bool binary_search (
    ForwardIterator first, 
    ForwardIterator last, 
    const T& value);

Where,

• ForwardIterator first = iterator to start of the range
• ForwardIterator last =iterator to end of the range
• T &value = reference to searching element which is of datatype T, T can be any inbuilt datatype or user-defined data type

Return type: bool

• True - if element found in the range
• False - If the element not found in the range

The above syntax is used to compare elements using standard comparison operators. Two elements a & b are said to be equal if (!(a<b) && !(a>b)).

We can also define the user-defined comparator for comparing. The syntax with user-defined comparator is like below:

bool binary_search(
    ForwardIterator first, 
    ForwardIterator last, 
    const T& val, 
    Comparator comp);

Using the above syntax two elemnts a & b would be equal if (!comp(a<b) && !comp(a>b)).

1) Using default comparator

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> arr{ 3, 2, 1, 4, 5, 6, 7 };

    //tp perform binary search we need sorted 
    //input array
    sort(arr.begin(), arr.end());

    int search_element = 4;

    //ForwardIterator first=arr.begin()
    //ForwardIterator last=arr.end()
    //const T& val=search_element
    if (binary_search(arr.begin(), arr.end(), search_element)) {
        cout << "search_element " << search_element << " found\n";
    }
    else
        cout << "search_element" << search_element << " not found\n";

    search_element = 7;
    
    //ForwardIterator first=arr.begin()
    //ForwardIterator last=arr.begin()+arr.size()-1
    //const T& val=search_element
    if (binary_search(arr.begin(), arr.begin() + arr.size() - 1, search_element)) {
        cout << "search_element " << search_element << " found\n";
    }
    else
        cout << "search_element " << search_element << " not found\n";

    return 0;
}

Output:

search_element 4 found
search_element 7 not found

In the above program, we have checked to cases and have used the default comparator. No need to mention, since this uses the binary search algorithm for searching, we need to feed sorted array only.

So as a pre-requisite we sorted the array. The sorted array is: [1,2,3,4,5,6,7]

Then for the first case, our range is the entire vector, and it returned true is since it finds the searched element 4.

For the second case, our range is [1-6] as we mentioned the end iterator as arr.begin()+arr.size()-1 which leaves the last element 7. So searched element 7 is not found.

2) Using user-defined comparator function

Here we have taken a use case where we have student details for five students. By using the user-defined comparator we have checked whether there is a student with the specified marks or not.

#include <bits/stdc++.h>
using namespace std;

class student {

    int score;
    int roll;
    string name;

public:
    student()
    {
        score = 0;
        roll = 0;
        name = "";
    }
    student(int sc, int ro, string nm)
    {
        score = sc;
        roll = ro;
        name = nm;
    }

    int get_score()
    {
        return score;
    }
    int get_roll()
    {
        return roll;
    }
    string get_name()
    {
        return name;
    }
};

//comparator for sorting
bool myfunc(student a, student b)
{

    if (a.get_score() < b.get_score()) //no swap
        return true;

    else //swap
        return false;
}

//comparator for binary search
//match found if !mycomp(a,b) && !mycomp(b,a)

bool mycomp(student a, student b)
{

    if (a.get_score() < b.get_score())
        return true;

    return false;
}

int main()
{
    vector<student> arr(5);
    //1st student
    arr[0] = student(80, 5, "XYZ"); //roll 5, marks 80
    //2nd student
    arr[1] = student(70, 10, "INC"); //roll 10, marks 70
    //3rd student
    arr[2] = student(85, 7, "HYU"); //roll 7, marks 85
    //4th student
    arr[3] = student(83, 1, "EFG"); //roll 1,  marks 83
    //5th student
    arr[4] = student(81, 11, "ABC"); //roll 11,  marks 81

    //sort based on marks
    //user-defined compartor=myfunc to sort
    sort(arr.begin(), arr.end(), myfunc);

    //find if any student exists who scored 81
    student t1(81, -1, ""); //dummy search element just to search the student marks
    if (binary_search(arr.begin(), arr.end(), t1, mycomp))
        cout << "Student with marks 81 exists\n";
    else
        cout << "Student with marks 81 doesn't exist\n";

    //find if any student exists who scored 75
    student t2(75, -1, ""); //dummy search element just to search the student marks
    if (binary_search(arr.begin(), arr.end(), t2, mycomp))
        cout << "Student with marks 75 exists\n";
    else
        cout << "Student with marks 75 doesn't exist\n";

    return 0;
}

Output:

Student with marks 81 exists
Student with marks 75 doesn't exist

Here we have first sorted the student vector using the user-defined comparator function. We have defined a separate comparator for binary search, though both have the same body. We have specified just to underline the factor that both comparators are not used in the same way. In case of searching, there is a match b/w T a and T b (T be the datatype) if !comp(a,b) && !comp(b, a) where a is element from the vector and b is the searching element.

So in this article, you saw how efficiently we can use binary_search to search elements within a range, no matter what kind of object it is. Even for the user-defined datatype, we can do by using a user-defined comparator as shown above. But, the main thing to remember is that the input list must be sorted(based on the key). For example, as we were searching for the marks, we sorted the student list based on marks.