0

I wrote the following recursive binary search function. No matter which exit codes I use (e.g., true, false, 1, 0, -1, "Swedish Chef"), I fail at least two of the checks I need to pass. The code looks right, however, I'm out of ideas as to fixing the return values. Note, the accompanying sort function works perfectly with arrays of all sizes.

Here is the code: bool binary(int value, int values[], int min, int max) {

if (max < min)
{
    return false;
}

int midpoint = (min + (max + min)/2);

if (values[midpoint] == value)
{
    return midpoint;
}
else if (values[midpoint] < value)
{
    return binary(value, values, (midpoint + 1), max);
}
else if (values[midpoint] > value)
{
    return binary(value, values, min, (midpoint - 1));
}

return false; }

And here are the error messages.

:) helpers.c exists

:) helpers.c compiles

:) finds 42 in {42,43,44}

:) finds 42 in {41,42,43}

:( finds 42 in {40,41,42} \ expected an exit code of 0, not 1

:( finds 42 in {41,42,43,44} \ expected an exit code of 0, not 1

:( finds 42 in {40,41,42,43} \ expected an exit code of 0, not 1

:( finds 42 in {39,40,41,42} \ expected an exit code of 0, not 1

:) doesn't find 42 in {39,40,41}

:) doesn't find 42 in {39,40,41,43}

  • Possible duplicate of Pset3 Binary Search problems This is the common problem of no recursive return code. See link. – Cliff B May 3 '16 at 15:56
  • Cliff, thanks for looking at the question! I added changed the binary calls to statements that return binary calls, as noted in the post you referenced, but the problem sadly persists. – Ryan May 3 '16 at 16:26
  • Well, I observe that you're computing the midpoint using twice the minimum index value. It could be a typo in the above code. Also, the last if-block has no associated else-block, or you could just forego checking the greater than boolean conditional. – Pooja May 3 '16 at 22:53
0

Many thanks to those who responded! The winning code involved, as Cliff noted by reference, the insertion of the "return" keyword after every recursive call to my homemade binary function. This, however, did not fix the code entirely. A second change, made prior to Pooja's astute observation, was the use of midpoint. I did not want to return the midpoint. In my thoughtlessness, I wrote "midpoint" instead of "value." Lastly, I restructured the entire branching structure -- including the base case -- to look as follows, which helped bring everything home.

if (max >= min)
{
        int midpoint = ...

        if (values[...] == ...)
        {
            return value;
        }    
        else if (values[...] > ...)
        {
            return binary(...);
        }
        else
            return binary(...);
}
return false; 
| improve this answer | |
  • Interesting solution. The only problem I have with it is that it is supposed to return a bool, meaning true or false, not a value. Returning a value can get complicated as different architectures, different programming languages and different operating systems can behave unpredictably. – Cliff B May 4 '16 at 4:05
  • Thanks again for the input, Cliff! I totally understand your critique. It was the only fix, however, that allowed me to pass the single check I kept missing. That said, as a sorta/kinda noob, return statements are less transparent to me, at least in C, than say Python. For example, I want to return a value for the system to use later, but 0 and 1 are values, and they are simply success and failure, respectively. So, I obviously need to do a bit more reading in this area. The reference you provided certainly helped. – Ryan May 4 '16 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .