Binary Search Algorithm

.Binary Search is an application of Divide and Conquer

Binary Search:

Input: A Sorted array of ' n' elements and element 'x'

Output:Return position of element 'x' if found else return (-1)

 

let 'i' is a variable used to store the first element index  and 'j' is a variable used to store the last element index and 'mid ' is a variable  for mid element index

 

BinarySearch(a,i,j,x)

{

                      if (i==j)

                       { 

                                       if(a[i]==x)

                                        return (i)

                                         else

                                        return (-1)

                           }

                    else

                           {   

                                    mid=\left \lfloor( i+j)/2 \right \rfloor

                                        if(a[mid]=='x')

                                         return mid;  

                                 }

                                        else    

                                                           {

                                                                  if(x<a[mid])

                                                                     BinarySearch(a,i,mid-1,x)

                                                                         else

                                                                        BinarySearch(a,mid+1,j,x)

                                                                  }

 }

 

let T(n) be the time complexity  of the  above algorithm then recurrence relation 

 

T(n)=\left \{ O(1)if i==j \right \}

         \left \{ T(n/2)+C if n>1 \right \} where C is a constant

After applying master Theorem we get  time complexity

Best case O(1)

Avg. and Worst-case O(logn)

0Comment