Binary search using recursion C code
Finding the location of the element with a given value or the record with a given key that is called searching. Operation of finding the location LOC of ITEM in data .Search is called successful if ITEM does appear in DATA and unsuccessful otherwise.
Searching Algorithm
- Linear search
- Binary search
Linear search
Which traverse DATA sequentially to locate ITEM is called linear search or sequential search.Find ITEM in in DATA where DATA contains n elements.Worst case occurs when must search through the entire array DATA. When ITEM does not appear in DATA. Algorithm require (n+1) comparisons. So running time proportional to n.
Binary search
That searching algorithm based on divide and conquer algorithm.Binary search have time complexity less than the linear search.Binary search work with sorted data.Number of comparison is less in binary search compared to the linear search.
Recursive binary search code is
void binarysearch(int a[],int lb,int ub,int item)
{
int mid;
if(lb>ub)
printf("element not found");
else
{
mid=(lb+ub)/2;
if(a[mid]>item)
binarysearch(a,lb,mid-1,item);
else if(a[mid]==item)
printf("search successfull element found at index %d",mid);
else
binarysearch(a,mid+1,ub,item);
}
}
Output
enter number of elemnet5
1
2
3
4
5
enter element you search1
search successfull element found at index 0
Recurrence equation of binary search
T(n)=T(n/2)+1
Solve using substitution method
T(n/2)=T(n/4)+1
Put the value of T(n/2)
T(n)=T(n/4)+2
So
T(n)=T(n/2^2)+2
......
.......
.......
upto k steps
T(n)=T(n/2^k)+k
n/2^k=1
n=2^k
k=logn
T(n)=T(1)+logn
T(n)=O(logn)
So Complexity of binary search is O(logn).
#include<stdio.h>
void binarysearch(int a[],int lb,int ub,int item);
void main()
{
int a[10];
int item;
int n;
int i;
printf("enter number of elemnet");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter element you search");
scanf("%d",&item);
binarysearch(a,0,n-1,item);
}
void binarysearch(int a[],int lb,int ub,int item)
{
int mid;
if(lb>ub)
printf("element not found");
else
{
mid=(lb+ub)/2;
if(a[mid]>item)
binarysearch(a,lb,mid-1,item);
else if(a[mid]==item)
printf("search successfull element found at index %d",mid);
else
binarysearch(a,mid+1,ub,item);
}
}
Output
enter number of elemnet5
1
2
3
4
5
enter element you search1
search successfull element found at index 0
0 Comments