Cpp Program for implementing Binary Search

In this post we will discuss on a basic searching technique called as binary search . It searches an element (generally called a key ) from a sorted array.

The array is divided into 2 sub arrays one from middle to start and other sub array from middle to end. If the sorted array is in ascending order and the key element is greater than the middle it searches the right sub array else left sub array  and the same process continues in those sub arrays until the key element is found.


Download Code
PROGRAM :

#include <iostream>

using namespace std;
int main()
{
    int i, first, last, middle, n, key, array[100];

    cout << "How many elements ?\t";
    cin >> n;


    for ( i = 0 ; i < n ; i++ )
    {
        cout << "\nEnter number "<< i+1 << " :\t";
        cin >> array[i];
    }


    cout << "\nEnter value to find :\t";
    cin >> key;

    first = 0;
    last = n - 1;
    middle = (first+last)/2;

    while( first <= last )
    {
        if ( array[middle] < key )
            first = middle + 1;
        else if ( array[middle] == key )
        {
            cout << "\n" << key <<" found at position "<<  middle+1 << endl;
            break;
        }
        else
            last = middle - 1;

        middle = (first + last)/2;
    }
    if ( first > last )
        cout << "\nNot found!"<< key <<" is not present in the list. "<< endl ;
    return 0;
}

OUTPUT :  

Cpp Program to implement Binary Search

Cpp Program to implement Binary Search

Download Code