Data Structures and Algorithms - Old Questions
9. How do you implement binary search algorithm? What is time complexity of this algorithm?
Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is:
1. First find the middle element of the list
2. Compare the mid-element with searched item.
There are three cases:
a. If it is a desired element then search is successful.
b. If it is less than desired item then search only in the first half of the list.
c. If it is greater than desired item then search in the second half of the list.
Recursive Algorithm:
BinarySearch(A,l,r, key)
{
if(l= = r)
{
if(key = = A[l])
return l+1; //index starts from 0
else
return 0;
}
else
{
m = (l + r) /2 ;
if(key = = A[m])
return m+1;
else if (key < A[m])
return BinarySearch(l, m-1, key) ;
else
return BinarySearch(m+1, r, key) ;
}
}
Example:
Consider an array of data:
21, 36, 56, 79, 101, 123, 142, 203
Now,
Tracing binary search for above data;
Set L=0, R=7, key=123 (search for 123)
S.No. | L | R | Mid=(L+R)/2 | Remarks |
1. 2. | 0 4 | 7 7 | (0+7)/2=3 (4+7)/2=5 | Key>a[3] Key==a[5] |
Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.
Efficiency:
From the above algorithm we can say that the running time of the algorithm is
T(n) = T(n/2) + O(1)
= O(logn)
In the best case output is obtained at one run i.e. O(1) time if the key is at middle.
In the worst case the output is at the end of the array so running time is O(logn) time. In the average case also running time is O(logn).