user3237895 user3237895 - 4 months ago 60
C Question

PSet 3 - CS50 - Binary Search Implimentation

this is PSET 3 from the CS50 course on edX.org.

I have been struggling with this problem set for a very long time; particularly, I cannot get the binarySearch function to work. I keep getting a segmentation fault and I can't figure out how to deal with it. I have spent a lot of time thinking through this and I just don't see it.

Here is my code. Can someone point out conceptually where I am going askew here? Thanks.

#include <stdio.h>
#include <cs50.h>

bool binarySearch(int value, int values[], int min, int max)
{
bool answer = false;

if (max < min)
{
answer = false;
}

else if (values[max] == value)
{
answer = true;
}

else if (values[min] == value)
{
answer = true;
}

else
{
int midPoint = (max + min) / 2;

if (values[midPoint] == value)
{
answer = true;
}

else if (values[midPoint] > value)
{
answer = binarySearch(value, values, min, midPoint);
}

else
{
answer = binarySearch(value, values, midPoint, max);
}
}

return answer;
}

int main (int argc, char *argv[])
{
int value = 34;

int values[] = {11,22,33,44,55,66,77,88,99,1010};

int max = sizeof(values) / sizeof(int);

if (binarySearch(value, values, 0, max - 1))
{
printf("Found needle!\n");
}

else
{
printf("Did not find needle\n");
}
}


I keep getting a segmentation fault when the value I am searching for is not in the array.

Answer

I think you should change you code to:

 else
    {   
        int midPoint = (max + min) / 2;

        if (values[midPoint] == value)
        {
            answer = true; 
        }

        else if (values[midPoint] > value)
        {
            answer = binarySearch(value, values, min, midPoint-1); // not midPoint
        }

        else
        {
            answer = binarySearch(value, values, midPoint+1, max); //not midPoint
        }
     }