Binary Search

If we look at the questions viz. How do we search for a person’s telephone number? If we know only the person’s name. and How difficult is this? Similarly How do we search for a person’s name? If we know only the person’s telephone number. and Why is this more difficult? similarly How do we search for a student blue book, when blue books are unsorted? AND when blue books are sorted?
Here what we can notice is Searching will be easier if the list is sorted. The technique what we use in searching of key element in sorted list is Binary Search. It works only on Sorted Elements.
How does it work...

It finds the middle element in the complete list of sorted elements then Compares the key element with middle element and STOPS if middle element is KEY and declare Successful Search. If KEY is less than middle element then it search in the lower half of the sorted list in the same way and If KEY is greater than middle element it search in the higher half of the sorted list in the same way and finally If Array exhaust it STOPS and declare Unsuccessful search.

The algorithm of Binary Search can be given as

Algorithm : Binary_Search( )
Begin
read the number of elements n
read n elements of an array a
read the key element to be searched
low = 0 high = n-1 flag = FALSE
do
mid = (low + high) / 2
if a[mid] == key then
flag = TRUE break
else if a[mid] > key then
low = mid + 1
else
high = mid – 1
end if
until low <= high
if flag == TRUE then
print “Successful Search”
else
print “UnSuccessful Search”
end if