How do you implement binary search algorithm? What is time complexity of this algorithm?

This answer is restricted. Please login to view the answer of this question.

Login Now

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:

  1. If it is a desired element then search is successful.
  2. If it is less than desired item then search only in the first half of the list.
  3. 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;

21 36 56 79 101 123 142 203
0 1 2 3 4 5 6 7

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).

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .