0
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.

2

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. ;-)

6
  • First off, thanks for the reply, highly appreciate this community. Q1) I understand compilers are dumb. What would be a fix for this? Is it necessary to always have a return outside of the loop so that even if the loop does not return anything, it is guaranteed that something will return outside of the loop? Q2) As noted in my opening post, maxindex = n was set deliberately as such because n inputted into the function is number the number of elements in the array but the maximum index number (or at least I think it is because in find.c, size is being inputted as n counting upwards from 0. Nov 19 '16 at 6:46
  • About Q2: your code works perfectly with values = {1, 10} and value = 10 and n = 1. The only thing I can see you doing wrong here is passing n as 2 (the size of the array) instead of 1 . The correct call would be search(value, values, 1) or even search(value, values, sizeof(values) / sizeof(int) - 1) if you want to automate the choosing of size. Nov 19 '16 at 13:02
  • Q2) I fail to understand why 'n' is passed in as '2' (the size of the array). In the 'find.c' program, 'size' is being passed into the function as 'n', where size is defined as 'for (size = 0; size < MAX; size++)' which makes size appear to be the array indices, and not the array size. Also, the code is not working with values = {1, 10} which is why I have asked the question. Nov 19 '16 at 18:06
  • Q2) Taking another look, size as defined by find.c is indeed for (size = 0; size < MAX; size++) and is indeed the number of elements in the array and not the array indices because the way to break out of the for loop causes an increase in size by 1 even though haystack{size] has not been assigned yet. ie. I assign values{1, 10}, but the for loop doesn't break at size=1, because the for loop cycles back and increases size and asks for the next integer and then break if EOF is triggered. TY for all the help guys. Nov 19 '16 at 18:17
  • The parameter n is the number of elements in the array. When you have an array size of n= 2, the array elements are numbered 0 and 1. Therefore value[2] is outside of the array. Unfortunately, this won't be reported as an error. Since maxindex is the index number of the last element in the array, it can't be set to n. It must be n-1 initially. If arrays started at 1 instead of 0, the number of elements and the index of the last element would be the same.
    – Cliff B
    Nov 19 '16 at 18:39

You must log in to answer this question.

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