Why not use Recursion for Binary Search for a sorted array

Question

I'm trying to implement a binary search where n is the size of my array and it's not working with recursion, only when I don't use recursion does it work, and I don't seem to understand why

int mid = 0;
int low = 0;

bool search(int value, int values[], int n)
{
   do
   {
   mid = (low + n)/2; 
   if(values[mid] == value) 
   {
        return true;
   }
   else if (values[mid]>value) 
   {
       n= mid -1;
       return search(value, values,  n);


   }
   else if (values[mid]<value)
   {
        low = mid + 1;
       return search(value, values,  low);

   }
 }
 while (n > low);

return false;
}

is this what the function header of search must look like? or are we allowed to make it just bool search(int value, int values[])? — Marc Lambrichs
– Marc Lambrichs, Commented Sep 10, 2017 at 20:00
or perhaps bool search(int value, int values[], int low, int high)? — Marc Lambrichs
– Marc Lambrichs, Commented Sep 10, 2017 at 20:15

Chris Dodd · Accepted Answer · 2017-09-11 02:07:25Z

2

The problem is that you call your recursive call to search the upper half of the array with a pointer to the lower half. So if the value is in the upper half, it won't find it. You need something like:

bool search(int value, int values[], int n) {
    int mid = n/2;
    if (n <= 0) {
        return false;
    } else if (values[mid] == value) {
        return true;
    } else if (values[mid] > value) {
        return search(value, values, mid);
    } else if (values[mid] < value) {
        return search(value, values + mid + 1, n - mid - 1);
    }
 }

edited Sep 11, 2017 at 2:07

answered Sep 11, 2017 at 2:02

Chris Dodd

127k14 gold badges150 silver badges243 bronze badges

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

1 Comment

Chris Dodd Over a year ago

@MarcLambrichs: Arrays in function arguments are really pointers, so this is passing a pointer not an int

Marc Lambrichs · Accepted Answer · 2017-09-10 20:42:40Z

Your program is a mix of two different solutions. You either have to solve this one with a loop or with a recursive function.

The loop you're trying to use should do something like this. No recursion needed here.

while (low <= high) {
   mid = (low+high) / 2;
   if (value < values[mid])
      high = mid - 1;
   else if (value > values[mid])
      low = mid + 1;
   else
      return true;
}
return false;

If you need to use recursion, no loop needed. your answer can look like this:

bool search(int value, int values[], int low, int high ) {
   if (low <= high) {
      int mid = (low + high)/2;
      if (values[mid] == value)
         return true;
      else if (value > values[mid])
         return search(value, values, mid+1, high);
      else
         return search(value, values, 1, mid-1);
   }
   return false;
}

I'm assuming here you can define your own function header.

Collectives™ on Stack Overflow

Why not use Recursion for Binary Search for a sorted array

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related