Binary Search using C/C++.

The most efficient method of searching a sequential table without the use of auxiliary indices or tables is the binary search. Basically, the argument is compared with the key or the middle element of the table. If they are equal, the search ends successfully; otherwise, either the upper or lower half of the table must be searched in a similar manner.

The binary search can be defined recursively. As a result, a recursive definition, a recursive algorithm, and a recursive program can be presented of the binary search. However, the overhead associated with recursion my make it inappropriate for use in practical situations in which efficiency is a prime consideration. Therefore the following algorithm uses non recursive fashion.

Algorithm

low = 0;
hi = n - 1;
while(low <= hi){
   mid = (low+hi)/2;
   if(key==k(mid))
     return (mid);
   if(key <  k(mid))
     hi = mid-1;
   else
     low = mid+1;
}
return(-1);

Source Code

#include<iostream>
using namespace std;
int main(){
    int n, search[10],low , high,mid ,temp, key;
    bool found = false;
    cout<<"Enter the number of element: ";
    cin>>n;
    for(int i = 0; i < n; i++){
        cout<<"search["<<i<<"]: ";
        cin>>search[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n-i-1; j++){
            if(search[j] > search[j+1]){
                temp = search[j];
                search[j] = search[j+1];
                search[j+1] = temp;
            }
        }
    }
    cout<<"the sorted array is: ";
    for(int i = 0; i < n; i++){
        cout<<search[i]<<" ";
    }
    cout<<"\nEnter the number to search: ";
    cin>>key;
    low = 0;
    high = n-1;
    while(low<=high){
        mid  = (low + high)/2;
        if(key == search[mid]){
            cout<<"The key is found at index "<<mid<<endl;
            found = true;
            break;
        }else if(key < search[mid]){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    if(!found){
        cout<<"Key not found!";
    }
    return 0;
}

Output

Enter the number of element: 7
search[0]: 5
search[1]: 9
search[2]: 21
search[3]: 45
search[4]: 11
search[5]: 3
search[6]: 78
the sorted array is: 3 5 9 11 21 45 78
Enter the number to search: 45
The key is found at index 5
Efficiency of Binary Search

Each comparison in the binary reduces the number of possible candidates by a factor of 2. Thus, the maximum number of key comparisons is approximately logn with base 2.