Binary Search

Binary Search

• Basic concept : Binary search is a searching algorithm in which the list of elements is divided into two sublists and key element is compared with middle element. If match is found then the location of that element is returned. Otherwise, we search into either of the halves depending upon the result produced through the match.

• The prerequisite for this searching technique is that the list should be sorted.

Example:

• As mentioned earlier the necessity of this method is that all the elements should be sorted. So let us take an array of sorted elements.

Step 1: Now the key element which is to be searched is 99

 key = 99.

Step 2 : Find the middle element of the array. Compare it with the key

if middle  key

i.e. if 42  99

if 42 < 99 search the sublist 2

Now handle only sublist 2. Again divide it, find mid of sublist 2

if middle  key

i.e. if 99  99

if middle  key

i.e. if 99  99

So match is found at 7^th position of array i.e. at array [6]

Thus by binary search method we can find the element 99 present in the given list at array [6]^th location.

Algorithm for binary search using recursive definition :

1. if(low > high)

2. return;

3. mid = (low + high)/2;

4. if(x= =a[mid])

5. return (mid);

6. if(x < a[mid])

7. search for x in a[low] to a[mid‒1];

8. else

9. search for x in a[mid + 1] to a[high];

Searching method  ‒ Time complexity

Linear Search          ‒      O(n)

Binary Search          ‒     O(nlogn)

Advantages of binary searching

1. It is an efficient technique.

Disadvantages of binary searching

1. It requires specific ordering before the applying the method.

2. It is complex to implement.

Time complexity

Let, the recurrence relation be,

T(n) = T (n/2 ) + c

    T (n/2 ) ‒ Time to search in half the array

          c     ‒    Constant time to compute the mid point and make one comparison

T(n) = T (n/2 ) + c

        =  T(n/4) + c + c

        = T(n/8) + c  + c + c

         = …

         =    T(n/2^k)  + c

Let us assume  n /2^k  = 1

                               n = 2^k

                               k = long₂ n

Equation (9.9.1) becomes,

T(n) = T(n/n) + c.log₂n

        = T (1)+c‒log₂n

As T(1) = 1 (Base case, compares only 1 element)

T(n) = O(log n)

In binary search,

Best case : O(1)

Average case : O(log n)

Worst case : O(log n)

Space complexity :

For iterative implementation O(1)

For recursive implementation O(log n) (stack space)

Review Questions

1. With example explain the binary search technique.

2. Write C++ code to implement linear search with suitable example.

3. Write C++ code to implement binary search with suitable example.

4. Explain in detail about linear search algorithm with an example.

5. Describe binary search in detail.

6. Explain linear search in detail.

7. Explain the binary search with sample program.

8. Write the algorithm to perform binary search on an array and demonstrate with an example.