Binary Search on Arrays using Recursion in C

Question

I was implementing Binary Search on arrays using recursion in C. However I keep getting erroneous index values for the search results. Please can anyone test run the code for different values and comment on how to fix the problem?

My code is as below:

#include<stdio.h>
#include<process.h>
int arr[100];
int retindex(int, int, int);
void main()
{
    int i=0, num=0, digits=0, j=0, temp=0, element=0, beg=0, mid=0, last=0, index=0, flag=0;
    printf("%s\n", "Please enter the numeric array (Enter 10101 to terminate) : ");
    for(i=0; ; i++)
    {
        scanf("%d", &num);
        if(num==10101)
        break;
        else
        {
            arr[i]=num;
            ++digits;
        }
    }
    printf("\n\nSorting the numeric array...\nHence the entered numeric array is: \n\n");
    for(i=0; i<(digits-1); i++)
    {
        for(j=(i+1); j<digits; j++)
        {
            if(arr[i]>arr[j])
            {
                temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
    }
    for(i=0; i<digits; i++)
    printf("%d\t", arr[i]);
    printf("\n\nEnter the element you want to search for: ");
    scanf("%d", &element);
    printf("\n\nPerforming binary search...\n\n");
    beg=0, last=digits, mid=(beg+last)/2;
    index=retindex(element, beg, last);
    if(index==-1)
        printf("%s", "Element not found, exiting!");
    else
        printf("%s%d\n\n", "Hence the element being searched for lies at index number ", (index));
    getch();
}
int retindex(int ele, int be, int la)
{
    int mid;
    mid=(be+la)/2;
    if(ele<arr[mid])
        retindex(ele, be, (mid-1));
    else if(ele>arr[mid])
        retindex(ele, (mid+1), la);
    if(ele==arr[mid])
        return mid;
}

thanks a lot everyone for the speedy and accurate response. It was my first time on stackoverflow and guys like you just made it sweeter. Thank you :) (too new to upvote anyone's answer here, really sorry) — Shubham Mehta
– Shubham Mehta, Commented Feb 12, 2015 at 16:09

Mike Nakis · Accepted Answer · 2015-02-12 15:44:55Z

1

Try this:

int retindex( int element, int lo, int hi )
{
    int mid = (lo+hi)/2;
    if( element < arr[mid] )
        return retindex( element, lo, (mid-1) );
    else if( element > arr[mid] )
        return retindex( element, (mid+1), hi );
    return mid;
}

answered Feb 12, 2015 at 15:44

Mike Nakis

63k11 gold badges128 silver badges172 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Weather Vane · Accepted Answer · 2015-02-12 16:12:20Z

1

Your function never returns the -1 that is looked for in main(). The best way I find to do a binary search, is to have the top index always out of range, i.e. it is never a candidate.

int retindex(int ele, int be, int la)
{
    int mid;
    mid = (be + la) / 2;
    if (mid == be) {
        if (ele == arr[mid])
            return mid;
        return -1;
    }
    if(ele < arr[mid])
        return retindex(ele, be, mid);
    if(ele > arr[mid])
        return retindex(ele, mid, la);
    return mid;
}

edited Feb 12, 2015 at 16:12

answered Feb 12, 2015 at 15:58

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

3 Comments

R Sahu Over a year ago

I think the line return retindex(ele, mid, la); should be return retindex(ele, mid+1, la);. Also you can fix the error in the line if (ele == arr[mid];.

Weather Vane Over a year ago

@RSahu It could be but it won't matter, and thank you for the other correction.

Weather Vane Over a year ago

@RSahu on second thoughts I was correct. OP passed la as the number of elements, i.e. the index past the end of the array. Suppose there are 10 elements and we reach the point where be=8 and la=10 making mid=9. If you then pass mid+1 to be for the next recursion, it will be out of range.

R Sahu · Accepted Answer · 2015-02-12 16:59:13Z

When you have a recursive function whose return type is anything other than void, you have to make sure that you use the return value of the recursive call.

if(ele<arr[mid])
    retindex(ele, be, (mid-1));  // Missing return 
else if(ele>arr[mid])
    retindex(ele, (mid+1), la);  // Missing return

In your case, the function reaches the end of the function without executing a return when a recursive call is made. That leads to undefined behavior.

A programming suggestion -- minimize use of global variables in functions. retindex can easily be changed to accept the array as one of the arguments.

int retindex(int sorted_array[], int ele, int be, int la)
{
   int mid=(be+la)/2;
   if (mid == be) {
      if (ele == sorted_array[mid])
         return mid;
      return -1;
   }
   if(ele<sorted_array[mid])
      return retindex(sorted_array, ele, be, mid);
   else if(ele>sorted_array[mid])
      return retindex(sorted_array, ele, mid, la);
   else
      return mid;
}

Drew McGowen · Accepted Answer · 2015-02-12 16:01:13Z

0

    return retindex(ele, be, (mid-1));

else if(ele>arr[mid])

    return retindex(ele, (mid+1), la);

Would be a good starting point.

edited Feb 12, 2015 at 16:01

Drew McGowen

11.7k1 gold badge35 silver badges58 bronze badges

answered Feb 12, 2015 at 15:45

Jeffrey

11.1k1 gold badge26 silver badges46 bronze badges

Collectives™ on Stack Overflow

Binary Search on Arrays using Recursion in C

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related