Binary Search | Data structure
  1. Binary search is a fast searching algorithm as compare to linear search algorithm.
  2. Binary search looks for a particular item by comparing the middle item with the searched value. If a match occurs, then the index of item is returned.
  3. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item.

Example:

10

14

17

21

25

29

31

35

       0                 1                    2                   3                    4                   5                    6                   7

 

In the above array we have to search for an element 29.

 

Some terms related with binary search:-

Low=0                 High=7

Mid=( low + high )/2 = (0+7)/2 = 3.5 = (Approx) 3   

The value present in index 3 is 21

 

Step1: we will compare the mid value 21 with the searched value 29.

          29>21 so  we will take the forward part of 21 and skip the other one.

21

25

29

31

35

 

         3                            4                                5                                6                                 7

 

Step 2: Again we have to calculate the low, high and mid value.

          Low=mid+1=3+1=4                 High=7

          Mid=( low + high )/2= (4+7)/2 = 5.5 = (Approx) 5

          The value present in index 5 is 29

          We are searching for the value 29 and we got it.

 

So, the searched value 29 is present in the index value of 5.

 

Implementation:

Procedure binary_search

   A ← sorted array

   n ← size of array

   x ← value to be searched

 

   Set lowerBound = 1

   Set upperBound = n

 

   while x not found

      if upperBound < lowerBound

         EXIT: x does not exists.

  

      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

     

      if A[midPoint] < x

         set lowerBound = midPoint + 1

        

      if A[midPoint] > x

         set upperBound = midPoint - 1

 

      if A[midPoint] = x

         EXIT: x found at location midPoint

   end while

  

end procedure.

 

Note:

  1. Binary search is also known as “Half- Interval search”.
  2. Time complexity :
  • Best case performance of binary search = O (1)
  • Worst case performance of binary search = O (log n)
  • Average case performance of binary search = O (log n)

 

Applications:

Binary search algorithm is mostly used for making “Binary search tree” and “Hashing techniques”.

 

Drawback:

For performing binary search technique the array must be in sorted order. Binary search technique can’t be used in unsorted array.

 

But as compare to linear search , Binary search is preferable.

 

0Comment