pset3 - recursive binary search not compiling

Question

I wrote a recursive function for binary search in pset" and I keep getting the same error from clang: "control may reach end on non-void function" it is driving me crazy... some help would be very welcome. :)

here is my code:

bool binary_search(int value, int array[], int lower, int upper)
{   
    if (array != NULL && lower >= 0 )
    {
        // check boundaries
        if (lower > upper)
        {
            return false;
        }
        else
        {
            // find middle of array
            int middle = (upper + lower) / 2;

            // recurses with left part  
            if (value < array[middle])
                return binary_search(value, array, lower, middle - 1);

            // recurses with right part
            else if (value > array[middle])
                return binary_search(value, array, middle + 1, upper);

            else if (value == array[middle])
                return true;
    }
    else
        return false;
}

Someone?

Answer 1

Common problem. The compiler looks at all the possible paths through the code and checks to see that there is going to be a guaranteed, unconditional return to satisfy the need for a return value. But, compilers are dumb. They don't recognize that you can create a fully conditional path that must hit a return.

In your case, the fix is simple. The final else is redundant, so just delete it. If your code doesn't return somewhere inside the main IF statement, you want to return false no matter what.

[EDIT - added comments] After looking more closely, there's also a mismatch on your curly braces. Add a closing brace after the last return true; statement. That should make it possible to compile.

If this answers your question, please click the check mark to accept this and remove the question from the unanswered pool. Let's keep up on forum maintenance. ;-)