Pset3: Helpers.c Binary Search Fails on checks that have 42 entered last

Question

For some reason my implementation of binary search for Pset3 fails to work correctly whenever the last number added to the "haystack" is 42. During use of GDB, I found that this is due to the part of my code after the while loop where is sets the currentvalue variable according to the state of the variable i. Despite i pointing to the correct location in the array, the currentvalue update fails to return 42 and instead gives me 41 when searching in the numbers "40, 41, 42".

The distinctly strange thing is that once every 10 or so run throughs of the code in GDB, it actually WOULD update to 42 and pass correctly, which even further confused me. Your help is much appreciated.

// Binary search
int i = n - 1;
int min = 0;
int max = n - 1;
int currentval = 0;
while ((max - min) > 0)
{
    // Check middle of array
    i = (min + max) / 2;

    currentval = values[i];
    // Check if middle of array is value
    if (currentval == value)
    {
        return true;
    }

    // Is value larger than i? check 2nd half, else check first
    if (value > values[i])
    {
        min = i + 1;
    }
    else
    {
        max = i - 1;
    }
}
// Check if middle of array is value
currentval = values[i];
if (currentval == value)
{
    return true;
}
return false;
}

Answer 1

I inserted your search routine into my code and found an additional clue. When the needle is either the smallest or the largest number in the sorted list, it would fail. This should be recognized as a conspicuous clue.

So, you need to look at your code to see what happens when you're checking the ends of the list, either the small end or the large end. You also need to take into account when you use the following line i = (min + max) / 2; when the two numbers involved are integers. It will truncate down. Now, when 42 is the largest number, that means that the test will eventually get to the last element (42) and the one before it. Let's say they are elements 2 and 1. The code will then calculate i = (2+1)/2 = (int) 3/2 = 1, followed by min = i+1 = 1+1 = 2.

Now the next pass through the while loop starts. IF it were to execute, it would find 42. BUT, max - min = 2 - 2 = 0. The test is for (max-min)>0. Test fails, while loop ends, search fails.

When 42 is at the small end, a similar logic occurs.

So, a slight adjustment to the while test will cure the problem, but I don't want to steal the fun of discovery, so I'll let you figure out what to change. ;-)

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