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:

       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.

         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.