Program for Binary Search in C++ and its Algorithm Efficiency

Binary search Algorithm is one of the most efficient algorithm after Linear search algorithm for Searching an element . Binary search Algorithm mainly involves dividing the list into two halves with their index values and finding the key value of middle element . In each step of the algorithm the middle key value is compared with the search key value . Then there arises 3 situations .

1. If search key value is equal to middle element key value : In this case Search element is found and the process is stopped . The algorithm returns the index where search key is found .
2. If search key value is less than the middle element key value : In this case you need to perform the search towards the Left of the middle element key value .

3. If search key value is greater than the middle element key value : In this case the search need to be performed towards the Right of the middle element key value .
In this Tutorial I will be discussing about Program for Binary Search in C++ and also it Efficiency when compared to linear search algorithm .

Output for below code:

Note :

To implement a Binary search algorithm the array should be in the sorted order . Use any sorting algorithm to sort the array and then apply Binary search algorithm to search an element .

Also check : Program for Bubble sort using c++

Program for Binary search in C++

#include<iostream>
using namespace std ;
int main()
{
    int a[10],n,i;
    while(1)
    {
        cout<<"\nEnter the no. of elements in the array :";
        cin>>n;
        if((n>=0)&&(n<=10))
            break;
        else
            cout<<"\n Array Size must have minimum 1 element and maximum 10 elements \n";
    }
    cout<<"\n---------------------------------\n";
    cout<<"Enter array elements :";
    cout<<"\n---------------------------------\n";

    for(i=0;i<n;i++)
    {
        cout<<"["<<(i+1)<<"]";
        cin>>a[i];
    }
    char ch;
    do
    {
        int key;
        cout<<"\n Enter the element to be Searched \n";
        cin>>key;
        int lbound=0;
        int ubound=n-1;
        int mid=(lbound+ubound)/2;
        int c=1;
        while((key!=a[mid])&&(lbound<=ubound))
        {
            if(key>a[mid])
                lbound=mid+1;
            else
                ubound=mid-1;
            mid=(lbound+ubound)/2;
            c++;
        }
        if(key==a[mid])
            cout<<"\n"<<key<<" Found at position "<<(mid+1)<<endl;
        else
            cout<<"\n"<<key<<" not found in the array"<<endl;
        cout<<"\n Number of comparisons: "<<c;
        cout<<"\n\n continue search (y/n) :";
        cin>>ch;
    }while((ch=='y')||(ch=='Y'));
return 0;
}

Efficiency of Binary search Algorithm :

In one of my previous post I discussed about Linear search algorithm . The worst case timing complexity of Linear search Algorithm is O(n) where n is number of elements . 
When it comes to Binary search after each case of first bisection the space for searching element is reduced by n/2 elements , similarly after 2nd bisection the space for searching element is reduced by n/4 elements and so on
On the whole the worst case timing complexity of Binary search algorithm is O(logn) . 

Also check : Algorithm for searching a Node in Binary Search Tree


If I have missed anything please get it to me through comments . Also share your ideas and logics to improve the program codes through comments .