Error with Check50 on Binary search

Question

I have some problems with Binary search. Check50 works fine for every case except this one:

:( finds 42 in {42,43,44} \ expected an exit code of 0, not 1 I got no clue why this happens :(

I followed Zamyla Chan's video tutorial and implemented it with a While loop. My code is this:

while (n > 0)
{
    int min = 0;
    int max = n;
    int mid = ((max + min) / 2) + 1;

    if (values[mid] == value)
    {
        return true;
    }

    else if (values[mid] > value)
    {
        max = mid - 1;
    }

    else if (values[mid] < value)
    {
        min = mid + 1;
    }

    n = max - min;
}

return false;        
}

Answer 1

Work through your code with paper and pencil. If I did it right, you have a problem when you get down to two elements left and the needle happens to be the smaller of the two. The line n = max - min; sets n to 0 for the next pass, which will end the while loop, even though there will be 1 element left. Try n = max - min + 1; and see if that cures it.

You might also try running through the IDE debugger or adding a few printf statements to follow the values of min, mid, max and n.

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

Answer 2

Thanks! Now I see the problem with my code, but I still can't fix it. Changing n = max - min; to n = max - min + 1 does not fix it. For what I understand following how the values change, it makes my mid to be in a loop where mid is 2. From your explanation I understand that my mistake is that mid does not reach 0, so when the needle is in the first position I can't find it. Still, I don't know how to fix it :(