BINARY SEARCH IN STL

INTRODUCTION

BINARY SEARCH IN STL

In this tutorial, we are going to learn about the binary_search, the pre-defined keyword in the standard template library of the C++ programming language. As a part of the data structures, we all know that binary search is an efficient method for searching an element from the given array of elements, the standard template library of the C++ programming language provides a pre-defined keyword binary_search, which provides the functionality and services likewise we implement binary search on any kind of array of elements. Let’s understand more about the binary_search keyword.

The elements on which we wanted to apply the binary_search method must be in sorted( increasing ) order. The main idea of the binary_search algorithm is to divide the array elements into halves until the key element is found or else until there is no more possibility for division. This method follows the divide and conquer policy.

Let’s look at the algorithm which is inside the binary_search method.

• Starts with breaking the array elements into equal half.
• Checks the key element to be searched with the middle-most element of the array.
• If the key element is greater than the middle-most element, apply the same process on the right sub-array and if, the key element is lesser than the middle-most value, apply the same process in the left sub-array until the key element found or until there is no chance for occurrence of the division.

This is the algorithm inside the binary_search method.

The time complexity of the pre-defined sort() function is of O( N log N ), whereas the time complexity of the binary_search() method is of O( logN ).

The auxiliary space of the binary_search() is O( 1 ).

Let’s look at the syntax of the binary_search() method.

binary_search( starting_index, ending_index, key_element);

Where,

staring_index and ending_index are the indices of the array.

key_element is the element to be searched.

Let’s look at a sample program implementing the binary_search() method.

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

void display(int a[], int arraysize)
{ 
    for (int i = 0; i < arraysize; ++i)
        cout << a[i] << " ";
}
int main() {

    int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
    int asize = sizeof(a) / sizeof(a[0]);
    cout << "Array elements : \n";
    display(a, asize);
    cout<<"\n\nArray after arranged in sorted order : \n";
    sort(a, a + asize); // sorting the array elements using sort()
    display(a, asize);
    int key1 = 6;
    cout<<"\nkey element : "<<key1;
    if (binary_search(a, a + 10, key1))
        cout<<endl <<key1<< " found in the array";
    else
        cout<<endl <<key1<< " not found in the array";
    int key2 = 10;
    cout<<"\n\nkey element : "<<key2;
    if (binary_search(a, a + 10, key2))
        cout<<endl <<key2<< " found in the array";
    else
        cout<<endl<<key2<< " not found in the array";
return 0;

}

The output of the program is.

In the above program,

1. We included the < algorithm > header for the implementation of the binary_search() method.
2. After sorting the elements, we applied the binary_search() method for the array elements.

CONCLUSION

That’s it from the tutorial. Hope you guys found it interesting. We have learned about the implementation of the binary_search() method in the standard template library in C++. Happy coding!