Binary Search pset3

Question

bool search(int value, int values[], int n)
{
int found = 0;
int notfound = 0;
int minindex = 0;
int maxindex = n;
int midindex = 0;
do 
{
    midindex = (minindex + maxindex) / 2;

    if (minindex > maxindex)
    {
        notfound = 1;
        return false;
    }

    else if (value > values[midindex])
    {
        minindex = midindex + 1;
    }

    else if (value < values[midindex])
    {
        maxindex = midindex - 1;
    }

    else
    {
        found = 1;
        return true;
    }
} while (found == 0 && notfound == 0);
}

Q1) Why does the above code not compile but causes "helpers.c:51:1: error: control may reach end of non-void function" error? I found online that the error is caused when a value may not be returned as a result of the function running. However, I don't ever see the possibility of this code not returning true or false booleans.

bool search(int value, int values[], int n)
{
int found = 0;
int notfound = 0;
int minindex = 0;
int maxindex = n;
int midindex = 0;
do 
{
    midindex = (minindex + maxindex) / 2;

    if (value < values[minindex] || value > values[maxindex])
    {
        notfound = 1;
        return false;
    }

    else if (value > values[midindex])
    {
        minindex = midindex + 1;
    }

    else if (value < values[midindex])
    {
        maxindex = midindex - 1;
    }

    else
    {
        found = 1;
        return true;
    }
} while (found == 0 && notfound == 0);

if (found == 1)
    return true;

else
    return false;
}

Q2) Why does the above code always return false? Instead of checking for the indexes, I am checking for if the key value I am looking for is outside the bounds of minindex and maxindex. However, the code always returns false. For example, if the array has 1 and 10 as integers, and the value I'm looking for is 10 it returns false. Wouldn't the thought process of the code be: initial midindex is 0, inital minindex is 0, initial maxindex is 1, so the value 10 > 0, increase the minindex to 1. therefore both maxindex and minindex is 1, so the next iteration there midindex is 1. 10 is not greater than values[maxindex] or smaller than values[minindex], is not greater than values[midindex], is not smaller than values[midindex], therefore return true?

I've seen some solutions as taking maxindex=n-1 starting.

However, this search function is inputting "size" from the find.c function, which should be the correct index numbers as it is counting from 0.

Answer 1

Q1: Remember this: COMPILERS ARE DUMB! While it may be logically impossible to not execute a return, compilers aren't capable of interpreting all of the complex logic possibilities to know. So, they don't try, beyond the most basic checks. So, the compiler looks for a structural way to complete execution of the function without executing a return, and it sees one. It sees that when the do/while loop completes and the code continues from there, the code will not execute a return before completing. I did say that compilers are dumb!

On a related note, the do while loop may as well be a while(true){...} loop. Both notfound and found are local vars set to 0. For the while test to fail, one or the other has to be set to 1. But, when either is set to 1, the next line will execute a return statement, so the code will immediately return to the calling program or function. Effectively, both variables serve no purpose.

Q2: The problem here is most likely related to maxindex. You set maxindex = n;. That's a problem. Remember that while there are n elements in the array, the largest valid index is n-1. By accessing values[n], you are accessing undetermined data, possibly (if not likely) a 0. Since it's likely less than the number that you're searching for, it results in FALSE.

I would test the code, but the IDE seems to be offline at the moment.

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