Data Structures and Algorithms - Old Questions
12. Differentiate between sequential searching and binary searching.
Sequential Search
In this technique, we access each element of list one by one sequentially and see whether it is desired element or not. i.e. the key element is compared with the first element of the list, if the match is found, then search is successful and return the position of key. Otherwise next element of the list is compared with key and this process is continued till the key is found or list is completely searched.
Algorithm:
LinearSearch(A, n,key)
{
for(i=0;i<n;i++)
{
if(A[i] == key)
return i;
}
return -1; //-1 indicates unsuccessful search
}
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.
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) ;
}
}
