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 mid = (low+hi)/2;
if(key==k(mid))
return (mid);
if(key hi = mid-1;
else
low = mid+1;
}
return(-1);

Source Code

 
#include
 
 
 
using namespace std;
 
 
 
int main(){
 
    int n, search[10],low , high,mid ,temp, key;
 
    bool found = false;
 
    coutEnter the number of element: ";
 
    cin>>n;
 
 
 
    for(int i = 0; i 
 
        coutsearch["]: ";
 
        cin>>search[i];
 
    }
 
 
 
    for(int i = 0; i 
 
        for(int j = 0; j 
 
            if(search[j] > search[j+1]){
 
                temp = search[j];
 
                search[j] = search[j+1];
 
                search[j+1] = temp;
 
            }
 
        }
 
    }
 
 
 
    coutthe sorted array is: ";
 
    for(int i = 0; i 
 
        cout ";
 
    }
 
    cout\nEnter the number to search: ";
 
    cin>>key;
 
 
 
    low = 0;
 
    high = n-1;
 
 
 
    while(low
 
        mid  = (low + high)/2;
 
        if(key == search[mid]){
 
            coutThe key is found at index "
 
            found = true;
 
            break;
 
        }else if(key 
 
            high = mid - 1;
 
        }else{
 
            low = mid + 1;
 
        }
 
    }
 
 
 
    if(!found){
 
        coutKey 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.