Posts which you will also like.

Friday, March 23, 2012

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.

Pointing upBinary Search Recursive: 

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

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

SunAlgorithmic 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


=>Taking logarithms on both side




=>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).

No comments:

Post a Comment

Your comment may wait for moderation.... Protected by Copyscape Online Plagiarism Tool