Data Structures and Algorithms - Old Questions
10. Explain the binary searching.
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.