Pset3 recursive binary search function - check50 gives me four :( and I don't know why

Question

I would be really grateful if someone could offer me a hint as to where I'm going wrong with this - I've been stuck for a couple of days now. When I work through the code step by step on paper it seems fine & logical, but obviously something's not right with my search function.

Please excuse my ugly code! A point in the right direction would be wonderful!

:) helpers.c exists
:) helpers.c compiles
:( finds 42 in {42,43,44}
\ expected an exit code of 0, not 1
:) 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}
:( 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}
https://sandbox.cs50.net/c…/595ffa008b4a4ef3a10192819d0dc6a6

int findmid(int start, int end) //function to find midpoint
{
    int mid = (start + end)/2; 
    return mid;
}

bool binarysearch(int value, int values[], int n, int start, int end) //my binary search function
 {
if (start > end) // if end < start we've gone too far, the value isn't there.
    {
      return false; //returns false.
    }

int mid = findmid(start, end); //mid is mid-point of search area

if (values[mid] == value) //if the int at mid position is the same as value, we've found it! WHY DOESN'T THIS WORK?
     {
      return true;//returns true
     }

if (values[mid] > value) //if the int at mid position in array is more than the value we're looking for
     {
        binarysearch(value, values, n, start, mid - 1); //sets end of search area to value to left of mid, calls binarysearch function recursively
     }
else if (values[mid] < value) // if the int at mid position is less than the value we're looking for
    {
        binarysearch(value, values, n, mid + 1, end); //sets start of search area to value to right of mid, calls binarysearch function recursively
    }
    return false; //returns false
}

  bool search(int value, int values[], int n) //this works, don't change it
    {
     int start = 0; //sets start of search area
     int end = n; //sets end of search area to size of array
     if (binarysearch(value, values, n, start, end))//calls binarysearch function, passes search arguments plus start and end and checks if it returns true
        {
         return true;
        }
     else
     {
     return false;
     }
}

Answer 1

Based on the comments in your code and without doing much analysis, I'd say that you have fallen victim to a very common error for new programmers.

A bool is either true or false. It can also be represented by numbers. In all programming languages, FALSE is represented ONLY by 0. TRUE is represented by * any non-zero number * (although this can vary from one programming language to another.) Your code does the opposite. It is representing TRUE as 0 and FALSE as 1.

The error is understandable because of a different standard programming practice. When a program returns a number as a completion code, the standard is that 0 represents normal or successful completion and a non-zero number represents an error code, usually defined by the programmer.

Because of these issues, the best practice is to use return true or return false and not numbers when returning bool results. It completely eliminates confusion.

[EDIT: following revised code]

Two problems remain, one serious and one minor. First, the minor problem.

int end = n; //sets end of search area to size of array

n is the number of elements in the array, so end should be set to n-1. (Surprisingly, it seems to work either way, but I suspect it could fail without warning.)

Second, and most significant, when you recursively call binarysearch() you aren't doing anything with the return value - the true or false that tells whether you found the needle. Because of this, the code is falling through to the catchall 1return false at the end. See the following link for the detailed explanation of this condition: Pset3 Binary Search problems

As a side note, you might want to consider reviewing and simplifying your code. For example, you have included n as a parameter to binarysearch(), but it doesn't use n at all. Also, findmid() is very simple and only called once. This code could be incorporated into binarysearch(). If you're practicing writing and calling functions, great, but normally, this wouldn't be a good reason for writing a separate function.

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