Data Structures and Algorithms - Old Questions

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.

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)

Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.