What's wrong with my binary search code?

Question

I thought I got everything right but when I checked my code with check50 it shows the following errors:

:( finds 42 in {42,43,44}
   \ killed by server

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

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

I see that there's a problem when the value we are searching for is in the beginning or in the end of the array. I don't have a clue what this can mean for my code. At what part of my code should I look to fix this problem? I hope someone of you can push me in the right direction.

bool search(int value, int values[], int n)
{
    int low = 0;
    int high = n;

    while (low < high)
    {
        int middle = (high + low) / 2;
        //base case
        if (value == values[middle])
            return true;

        else if (value > values[middle]) //Value is bigger then midpoint.
           low = values[middle + 1]; 

        else if (value < values[middle]) //Value is smaller then midpoint.
            high = values[middle - 1];
    }
    return false;
}

Answer 1

You're setting "low" and "high" to values[middle - 1]. That is the value stored in that array location, and NOT the index of the array. So, suppose you have this case:

values = {42, 43, 44} looking for 42

So:

low = 0; n = 3;

while loop starts, low < high

middle = 1 ((3+0)/2) So we go to the last else if:

So, now you set "high" to be 42. Which means that middle will be 21, and from then on anything can happen because you will be out of the range of the array the whole time. You're not causing a segmentation fault by sheer luck. :)