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

## No comments:

## Post a Comment

Your comment may wait for moderation....