[SOLVED] return value problem in recursive binary search

atlantis43 · 08-27-2014, 08:02 AM

trying to use the following code, but can't figure out how to parse it properly so that the function exits after value return true;, rather than also subsequent execution of "return false". Probably a very simple error, and hope someone can help.

Code:

int binary_search(int haystack[],int value, int lo,int hi)

{
int mid;

//int lo = 0,hi = MAX;

    if (lo > hi)    //would print "not found""
    {
         return 0;
    }
    mid=(hi+lo)/2;
    if (haystack[mid] == value)
    {

        return true;
    }
    else if (haystack[mid] > value)
    {
        binary_search(haystack,value, lo, mid - 1);
    }
    else if (haystack[mid] < value)
    {
        binary_search(haystack,value, mid + 1, hi);
    }
    return false;
}

mina86 · 08-27-2014, 08:23 AM

When you call binary_search recursively you are ignoring it's return value:

Code:

bool binary_search(int *haystack, int value, unsigned lo, unsigned hi) {
    unsigned mid;
    if (lo > hi) {
         return false;
    }
    mid = (hi + lo) / 2;
    if (haystack[mid] == value) {
        return true;
    } else if (haystack[mid] > value) {
        return binary_search(haystack,value, lo, mid - 1);
    } else if (haystack[mid] < value) {
        return binary_search(haystack,value, mid + 1, hi);
    }
}

atlantis43 · 08-27-2014, 08:30 AM

Is there any way to use a recursive call with a return value, as in my original code?

ntubski · 08-27-2014, 08:53 AM

Quote:

Originally Posted by atlantis43

Is there any way to use a recursive call with a return value, as in my original code?

You put a return in front of the recursive call... like in mina86's post. Or if you mean something else, can you elaborate?

pan64 · 08-27-2014, 08:57 AM

I do not really understand what do you need, but probably:

Code:

int binary_search(int haystack[],int value, int lo,int hi)
{
int mid;
int b;

    if (lo > hi)    //would print "not found""
    {
         return 0;
    }
    mid=(hi+lo)/2;
    if (haystack[mid] == value)
    {
        return true; // << you should return int, not boolean
    }
    else if (haystack[mid] > value)
    {
        b = binary_search(haystack,value, lo, mid - 1);
    }
    else if (haystack[mid] < value)
    {
        b = binary_search(haystack,value, mid + 1, hi);
    }
//  calculate return value (based on b)
    return something
}

atlantis43 · 08-27-2014, 09:17 AM

Just trying to learn what I'm not understanding in the following Rube Goldberg creation!
Well, here's the long (and confused) explanation for my question:

Given the following function to write, (and not allowed to change this call)

Code:

bool search(int value, int values[], int n)

I,ve tried to use it to subsequently call a recursive function, by means of the following:

Code:

{       
int needle = value;
int lo = 0,hi = n;ret;
ret=binary_search(values,needle, lo, hi);
if(ret==1)
    {
    return true;
    }
    else
    return false;
}

Then I'd like an int returned from my originally posted code.
I know I can call a recursive function directly, but cant pass the "lo" argument as per the instructions.

NevemTeve · 08-27-2014, 09:19 AM

You should return an int, not a bool. Also, if you want recursion (bad idea), you might want to use a helper function:

Code:

static int binary_search_core (const int haystack[], int needle, int lo, int hi)
{
    ...
}

int binary_search (const int haystack[], int n, int needle)
{
    return binary_search_core (haystack, needle, 0, n-1);
}

ntubski · 08-27-2014, 10:13 AM

Quote:

Originally Posted by atlantis43

Well, here's the long (and confused) explanation for my question:

Yeah, still confused. Doesn't mina86's post #2 answer your question?

Quote:

I,ve tried to use it to subsequently call a recursive function, by means of the following:

Doesn't that work?

Quote:

Then I'd like an int returned from my originally posted code.

You can rename bool -> int, true -> 1, false -> 0. It doesn't really make any difference in C.

Quote:

I know I can call a recursive function directly, but cant pass the "lo" argument as per the instructions.

There's no "lo" argument in the search function, but binary_search is a different function.

atlantis43 · 09-15-2014, 04:16 PM

OMG: Mina's post finally sank into my thick head!!!!!

psionl0 · 09-15-2014, 05:50 PM

Quote:

Originally Posted by atlantis43

Given the following function to write, (and not allowed to change this call)

Code:

bool search(int value, int values[], int n)

Do you have to be write a recursive function? A loop would be more efficient:

Code:

bool search(int value, const int *values, int n) {
   int lo, mid, hi;

   lo = 0;
   hi = n - 1;

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

Note that you don't need a separate binary_search function.

atlantis43 · 09-16-2014, 03:20 PM

Psion10;
Yes, I already had written a loop, but was just trying to learn recursion for same purpose (within the limitation of the given calling function).

ntubski · 09-16-2014, 09:04 PM

FYI, gcc recognizes the tail recursion and generates looping code.