CODEWITHSUNDEEP
cbinary-search
novice
novice

Reputation: 3

Infinite loop in this binary search implementation?

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

Answers (2)

Gopi
Gopi

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

Arkku
Arkku

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

Related Questions