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.

It is late, and my brain is shutting down. In reviewing your code, perhaps there is a problem with the line 'int max = sizeof(values) / sizeof(int);' You may wish to 'printf("max[%d]\n", max);' and verify that it prints what you expect (ie: 10 ?). — Mahonri Moriancumer
– Mahonri Moriancumer, Commented Apr 23, 2014 at 5:49
Why don't you use a simple iteration with while? It is simpler, faster and safer than recursion... — CiaPan
– CiaPan, Commented Apr 23, 2014 at 6:24
@Mahonri - I did test it that way before; it comes up with the correct size of max. — user3237895
– user3237895, Commented Apr 23, 2014 at 20:20
@CiaPan, I can't conceptualize how a while loop would be coded... — user3237895
– user3237895, Commented Apr 23, 2014 at 20:21

BlackMamba · Accepted Answer · 2014-04-23 06:10:50Z

3

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

answered Apr 23, 2014 at 6:10

BlackMamba

10.3k8 gold badges47 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3237895 Over a year ago

this worked! You won't believe how long I've spent on this. I have learned a lot along the way though. Can you explain to me, however, why it is necessary to add midPoint - 1 and midPoint + 1. I tried tracing this out on paper and it is not making sense to me.

CiaPan Over a year ago

@user3237895 Try to follow your program with a sheet of paper and a pencil while searching for 7 in a single-item array with the only value of 3.

user3386109 · Accepted Answer · 2014-04-23 06:01:28Z

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.

answered Apr 23, 2014 at 6:01

user3386109

35k7 gold badges52 silver badges69 bronze badges

Collectives™ on Stack Overflow

PSet 3 - CS50 - Binary Search Implementation

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related