Reputation: 3
Can anyone help me find the error in this implementation of the binary search algorithm. I guess it is running in an infinite loop. There is a problem in function definition but not sure what.
#include <stdio.h>
#define max 5
int binarysearch(int a[],int element,int first,int last);//prototype
int main(void)
{
int arr[max]={1,2,3,7,8};
int b;
int start=0;
scanf("%d",&b);
int search=binarysearch(arr,b,start,max-1);
if(search==-1)
{
puts("element is not there in array");
}
else
{
printf("element found at position %d",search);
}
}
int binarysearch(int a[],int element,int first,int last)//definition
{
int mid=(first+last)/2;
int initial;int final;
while(first<=last)
{
if(a[mid]==element)
{
return mid;
}
else if(a[mid]<element)
{
initial=mid+1;
final=last;
binarysearch(a,element,initial,final);
}
else if(a[mid]>element)
{
initial=first;
final=mid-1;
binarysearch(a,element,initial,final);
}
}
return -1;
}
Upvotes: 0
Views: 147
Reputation: 19874
Make the below changes
int binarysearch(int a[],int element,int first,int last)//definition
{
int mid=(first+last)/2;
int initial;int final;
if(first > last)
{
printf("Not found\n");
return -1;
}
if(a[mid]==element)
{
return mid;
}
else if(a[mid]<element)
{
initial=mid+1;
final=last;
binarysearch(a,element,initial,final);
}
else if(a[mid]>element)
{
initial=first;
final=mid-1;
binarysearch(a,element,initial,final);
}
}
Upvotes: 0
Reputation: 42169
You have an unnecessary loop inside the function:
while(first<=last)
This is an infinite loop, because first
and last
are never reassigned inside the loop. You already use recursion by calling binarysearch
inside the loop body. Either change the while
to if
, or remove the recursive calls and assign to first
and last
instead of initial
and final
(and recalculate mid
accordingly).
If you decide to stick with the recursive approach, also change the calls to return binarysearch(…);
or the return value is lost.
Upvotes: 2