Having trouble with pset3 helpers.c binary search

Question

bool search(int value, int values[], int n)
{
    int midpoint = n / 2;
    int startpoint = 0;
    int endpoint = n - 1;

    // if the midpoint doesn't equal the vales we're looking for, repeat this loop
    while (values[midpoint] != value)
    {
        // if value is smaller than midpoint
        if (value < values[midpoint])
        {
            endpoint = midpoint - 1;
            midpoint = (int) ((endpoint - startpoint + 1) / 2);
        }

        // if value is larger than midpoint
        else if (value > values[midpoint])
        {
            startpoint = midpoint + 1;
            midpoint = (int) ((endpoint - startpoint + 1) / 2);
        }

        if (endpoint - startpoint == 0 && values[startpoint] != value)
        {
            return false;
        }
    }
    return true;
}

Read over it a couple times and watched the walkthrough. Not sure what's wrong :/

Answer 1

It's going into an infinite loop when the needle is the last number in the stack. If you were to print out the values for min, mid and max, you'd be surprised. I did so, along with a pass counter and here's a sample for 40,41,42.

min=startpoint, mid= midpoint, max=endpoint
Count is the # of the current pass through the loop.

Count: 0, Min: 0, mid: 1, max: 2
Count: 1, Min: 2, mid: 0, max: 2
Count: 2, Min: 1, mid: 1, max: 2
Count: 3, Min: 2, mid: 0, max: 2
Count: 4, Min: 1, mid: 1, max: 2
Count: 5, Min: 2, mid: 0, max: 2
Count: 6, Min: 1, mid: 1, max: 2

Clearly, there's a problem with the code because mid cannot be less than min. Think about how mid is being calculated:

    // if value is larger than midpoint
    else if (value > values[midpoint])
    {
        startpoint = midpoint + 1;
        midpoint = (int) ((endpoint - startpoint + 1) / 2);
    }

The needle is at the end of the list. To amplify the effect, let's say that startpoint = 4, midpoint = 6 and endpoint is 8. Startpoint gets updated to 6+1 = 7. Next, midpoint = (8-7+1)/2 = 2/2 = 1. So on the next pass, midpoint is 1! This, plus the effect of integer division plays havoc on the setting of midpoint and thus, on startpoint on the next pass.

The root problem is this: the code, as written, calculates roughly 1/2 the distance between the startpoint and the endpoint. That amount has to be added to the startpoint. As written, it is being used relative to 0, not to the startpoint. The midpoint value as calculated in the coded needs to be added to startpoint.

I suspect that a similar problem exists with code dealing with the lower half of the list too, but is not being exercised by the test data.

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