segmentation fault on binary search

Question

Can anyone tell me how to stop segmentation fault from happening in my binary search? I am trying to implement a recursive binary search and it works when it finds the needle in the haystack but if the needle is not there it accesses bad memory somehow. I unfortunately can't get GDB to work on my computer since I'm using Mac OS X and I installed the Homebrew version which is incompatible so I can't think of any other way to debug the program. here is the function that is called in find after giving lo 0 and hi n

 bool look (int value, int values[], int hi, int lo)
{
 int mid = round(hi / 2);
if (hi > 1)
{
    for (int i = lo; i < hi; i++)
    {
        if (values[mid] == value || values[lo] == value || values[hi - 1] == value)
        {
            return true;
            break;
        }

        else if (values[mid] > value)
        {
            hi = mid;
          return  look ( value,  values,  hi, lo);
            break;
        }

        else if (values[mid] < value)
        {
            lo = mid;
           return look (value, values, hi, lo);
            break;
        }

    }
}
else if (values[hi - 1] == value)
{
    return true;
}

return false;
}

Answer 1

The seg fault is a result of running out of system stack memory. The code creates an infinite recursion when the needle is not in the haystack, but is larger than the largest element in the haystack.

If you create a global counter var and insert the following into the top of your look() function after the declaration of mid, you'll find the run results intriguing.

int loops=0;  // before look()

printf("pass %i, value: %i, lo: %i, mid: %i, hi: %i.\n", loops, value, lo, mid, hi);

This will get you going in the right direction. I'm also concerned about passing n, as hi. In some ways, you are using it as the number of array elements (correct), and at other times, you are using it as the index for the array, values[hi]. The last array element would be hi - 1. You even correct for this in one spot but not others. Time to clean that up and standardize on one usage.

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