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

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.

SHARE Binary Search using C/C++.

You may also like...

5 Responses

  1. It is very usefull website for me. I like it to much.
    Thanks!

  2. Unknown says:

    It is very usefull website for me. I like it to much.
    Thanks!

  3. This information has helped a lot
    Thank you

  4. Anonymous says:

    thank you so much

Leave a Reply

Your email address will not be published. Required fields are marked *

Share