PSet 3 - CS50 - Binary Search Implementation

Question

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 1

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
        }
     } 

Answer 2

The problem is here

if (max < min)

Eventually, max will equal min, but nothing in the code forces max to become less than min. Hence, the function will recurse forever, if the specified value is not in the array.