Binary Search Technique with Algorithmic Analysis

---

Binary searching is a searching method which is based on divide and conquer approach and It is most suitable when items are stored in sorted order i.e either increasing or decreasing manner.
Binary search technique has time complexity of O(logn) (on base 2) which if much better than other searching techniques.
Binary search can be implemented in two ways : in recursive way or in iterative way.
Complete Source code for Binary Search  is listed here.

Binary Search Recursive: 

int Bsearchrec(int arr[],int low,int high,int item){ int mid=low+(high-low)/2;
if(arr[mid]==item)
        return mid;
else if(arr[mid]<item)
        return Bsearchrec(arr,mid+1,high,item)
else
        return Bsearchrec(arr,low,mid-1,item)
return -1; // control will reach here only if item not found
}

Binary Search Iterative: 

 int Bsearchiter(int arr[],int size,int item){
 int low=0;int high=size-1;
 while(low<=high){                 
                         mid=low+(high-low)/2;                 
                         if(arr[mid]==item)                        
                             return mid;                 
                         else if(arr[mid]<item)                         
                             low=mid+1;                
                         else  high=mid-1;      
                         }  
        return –1;// Unsuccessful result
}

Algorithmic analysis of Binary Search:


If we analyse the Binary Search carefully we would find that each time size of array to search is decreased by half.After ith opertaion we have problem of size 1 i.e reached the goal state.

Initially we have

           1opertaion: Problem of size=n/2(size of array)
           2opertation: Problem of size=n/4
           3opertation: Problem of size=n/8
            ……………………………………
           ……………………………………

           ith operation: Problem of size=n/2^i

ith stage is the stage when we have problem of size=1

=> n/2^i=1

=>n=2^i

=>Taking logarithms on both side

=>logn=log(2^i)

=>ilog2=logn

=>i=logn/log2

=>i=logn(on base 2)

It means total running time is O(logn) (on base 2).

If we go by recurrence relation them we find following recurrence relation:

T(n) =T(n/2)+ ?(1)

Solution of this recurrence is also T(n) = O(logn).