0

I'm stuck on implementing the binary search function in pset3. I am trying to do the recursion method but I am stuck and have been for hours. It seemed easy enough but I am discovering that it's more complicated than I thought, or maybe I over complicated it. I keep getting segmentation fault and I can't figure it out. I also cant use the debugger as the button doesn't appear on my IDE.

    bool binarysearch(int key, int array[], int min, int max)
    {
    //check to make sure key is a positive int
    if (key <= 0)
    {
        return false;
    }
    else if (max < min)
    {
        return false;
    }
    else
    {
        int mid = min + ((max + min) / 2);
        //if key is greater that mid, search mid + 1 to max
        if (array[mid] < key)
        {
            return binarysearch(key, array, mid + 1, max);

        }
        //If key is less that mid, search min to mid - 1
        else if (array[mid] > key)
        {
             return binarysearch(key, array, min, mid - 1);
        }
        //If key == mid return true
        if (key == array[mid])
        {
        return true;
        }
        return false;
    }
    return false;
}


bool search(int value, int values[], int n)
{
    // TODO: implement a searching algorithm
    return binarysearch(value, values, 0 , n - 1);
}
1

First - think about what a segmentation fault is. It happens when you try to access memory that doesn't belong to you.

https://stackoverflow.com/questions/2346806/what-is-a-segmentation-fault

Try to plug in some sample numbers into this equation. Here's a hint - try to start with a min of 0 and a max of 10 and see if your mid always stays between 0 and 10.

int mid = min + ((max + min) / 2);

Instead try: int mid = (max + min)/ 2

Please upvote my answer and accept it if it helps you. Feel free to ask a question if you have one.

| improve this answer | |
  • Thanks so much, It makes so much sense now. I was pulling out my hair over this haha. I don't know where I got 'int mid = min + ((max + min) / 2);' from but again, Thank you so much! – Taylor Adam Aug 10 '16 at 6:36

You must log in to answer this question.

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