0

I've been working on find.c for a long time now and I've managed to get to the point where it will return the correct output when the needle is in the haystack, but when it isn't I get a segmentation fault. I've done everything I'm capable of to try and find the problem, I've run GDB multiple times and used printf statements and asked some of my computer science major friends to help me debug but even they can't figure it out. I've been trying to figure this out for a long time now so any hints in the right direction would be appreciated. Here's my code:

bool binarysearch(int key, int array[], int start, int end)
{
    int midpoint = (start + end)/2;
    if (key == array[midpoint])
    {
        return true;
    }
    else if (key < array[midpoint])
    {
        return binarysearch(key, array, start, midpoint-1);
    }
    else if (key > array[midpoint])
    {
        return binarysearch(key, array, midpoint+1, end);
    }
    else if (key == start || key == end)
    {
        return true;
    }
    return false;
}

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    if (n < 0)
    {
        return false;
    }
    int min = 0;
    int max = n;
    return binarysearch(value, values, min, max);
}

I've tried putting the last "return false" in the binarysearch function inside an else statement but that didn't work either so I'm pretty lost.

Thanks!

1

There are two problems - an infinite loop and a parameter that is out of range.

Infinite loop: In binarysearch(), when the target is not in the list, the recursive calls will eventually get to a point where end is less than start. At this point, binarysearch will continue recursively calling itself with the same parameters without end. Eventually, it will use up resources and seg fault. If you'd like to see this, put a printf at the start of binarysearch and print out the parameters passed to it, along with a global counter var to see how many times it is called.

You need to add a check for this condition, since it is an indicator that the target isn't in the list.

Next, the call to binarysearch() from search() uses n as max. n is beyond the end of the array by 1. It should be n-1. Remember, an array index is 0 based, not 1 based.

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

2
  • So I changed max to be n-1 and added two more conditions where the function will return false if (end < start || start > end), and if (key < start || key > end) but I'm still getting a segmentation fault. It also seems to have made less of the test cases in check50 work properly. I added the printf statements so I can see what you mean about the infinite loop but I'm not sure why those conditions aren't fixing the problem.
    – Danielle R
    Jul 26 '16 at 19:55
  • I figured it out, the new conditions were just in the wrong order. Thanks a lot!
    – Danielle R
    Jul 27 '16 at 3:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .