Binary Search is quicker than the linear search. However, it cannot be applied on unsorted data structure. The binary search is based on the approach divide-and-conquer. The binary search starts by testing the data in the middle element of the array. This determines target is whether in the first half or second half. If target is in first half, we do not need to check the second half and if it is in second half no need to check in first half. Similarly we repeat this process until we find target in the list or not found from the list.
To implement binary search method, the elements must be in sorted order. Search is performed as follows:
Repeat through step 4 while lower bound(lb) is less than upper bound.
Step 3: [obtain the index of middle value]
if(key < a[mid]) then
otherwise if( key > a[mid]) then
Write “match found”
Step 5: [unsuccessful search]
Write “match not found”
Step 6: [end of algorithm
int bsearch(int [ ],int,int);void main( )
int bsearch(int a[ ],int n, int k)