Binary Search in C++ STL(Standard Template Library)

This tutorial will teach us how to use binary search in C++ STL(standard template library).

Binary search is a searching algorithm that needs the array to be sorted first before it is used.

The principle behind this algorithm is to divide the array into half of its whole array until the element is found else, till the elements are exhausted. This returns true when the element is found. if it is greater then it searches in the right part else it searches in the left part.

Syntax

binary_search(first_address, last_address, Element_to_be_find)

first_address=The first element address of the array.

last_address=The last element address of the array.

Element_to_be_find=Element which need to be find.

ReturnType

The return type of the binary_serach() is boolean.

if the element is found it returns true else, it returns false.

Complexity of Binary Search in C++ – STD

Time Complexity: O(nlogn)

Space Complexity: O(1)

C++ program: Binary search

Here is the sample program for binary_search().

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

int main()
{
    int n;
    cout<<"enter the size of the array\n";
    cin>>n;
    int arr[n];
    cout<<"Enter the elemeents of the array\n";
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int key;
    cout<<"Enter the element need to be searched\n";
    cin>>key;
    cout<<"The elements of the array are\n";
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    bool temp=binary_search(arr,arr+n,key);
    if(temp)
    {
        cout<<"\nElement is found";
    }
    else
    {
        cout<<"\nElement is not found";
    }
    return 0;
}

Output :

enter the size of the array
5
Enter the elemeents of the array
1 2 3 4 5
Enter the element need to be searched
4
The elements of the array are
1 2 3 4 5 
Element is found

Explanation :

  • Here firstly, we need to take the size of the array from the user.
  • Then the user needs to enter the elements of the array and the element which needs to be found.
  • Then by using binary_search() as its first address is arr and last address is arr+n, an element needs to be found.  and its datatype as a bool.
  • If it returns true then it returns as element is found else, element is not found.

Leave a Reply

Your email address will not be published.