Recursive binary search implementation is crashing... why?

Question

I'm trying to find and fix what is wrong with this code. It's a binary search implemented by recursion. I dont know why it's returning stack overflow and crashing.

bool find( const int x, const int* pBegin, const int* pEnd)
{
    int medel = (*pBegin +(( *pEnd-1) - *pBegin)/2) ;

    if(x == medel)
        return true ;

    else if( x > medel) 
    {
        int begin = (medel +1);

        return find (x, &begin, pEnd);
    }
    else if( x< medel)
    {
        int last = (medel-1);

        return find(x,pBegin, &last);
    }

}


void main()
{
    int arr[10];
    for (int i=0;i<10;++i)
        arr[i] = i;
    bool hittat = find(7, &arr[0], &arr[9]);
    cout << "hittat = " << hittat << endl;

    system("pause");
}

When I debug the code, I see that when the function "find" is called it takes weird arguments, like in this pic.

It should take 0 and 9, not these huge numbers :/ Is there anything wrong with my pointers?

As much as I agree with the answer given so far, suggesting to compute the average of pointers rather than the average of values, I do not think that this is at the root of your problem: your code is only testing values, never pointers, so it should run without troubles. In fact, it is as if it was passing values instead of pointers and determine if the first argument is between the second and the third. Which is likely not what you want, but should not be the root cause of your problem. I tried it on my system and I do not observe that behavior. Aren't you debugging a release build? — Andy Prowl
– Andy Prowl, Commented Jan 26, 2013 at 19:41

Ivaylo Strandjev · Accepted Answer · 2013-01-26 19:34:01Z

1

You should compute the average of the pointers and check what it's the value of the element hallway between them. Instead you compute the average of the values pointed by them which is significantly different.

answered Jan 26, 2013 at 19:34

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

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

1 Comment

Fadi Alkadi Over a year ago

could you please describe more

Ben Hocking · Accepted Answer · 2013-01-26 19:59:06Z

1

You're using medel (I'm assuming that should be middle) as a pointer to an int in some places, but as an int in others.

Try declaring it like this:

const int* middle = pBegin + (pEnd - pBegin + 1) / 2;

Then, when you want to access what is stored there, use *medel.

Also, you'll need a second terminating condition (for when it won't be found). Something like:

if (((middle == pEnd) && (x > *middle)) ||
         ((middle == pBegin) && (x < *middle))) {
  // Terminating condition                                                                                                                                                                              
  return false;
}

edited Jan 26, 2013 at 19:59

answered Jan 26, 2013 at 19:28

Ben Hocking

8,1425 gold badges40 silver badges53 bronze badges

1 Comment

JoergB Over a year ago

The -sizeof(int) part does not belong here. Arithmetic with typed pointers increments already takes size into account under the hood. And only some variants of the algorithm would have a -1 here.

lpostula · Accepted Answer · 2013-01-26 19:35:42Z

0

You are mixing pointer on int and int with your medel, just set it to be a pointer and access his data with *medel

answered Jan 26, 2013 at 19:35

lpostula

5841 gold badge6 silver badges23 bronze badges

Comments

JoergB · Accepted Answer · 2013-01-26 19:45:50Z

The problem shown in your picture looks like it was taken from your original code as seen in a prior question. There you had pEnd pointing past the end of an array, so that dereferencing it was not allowed (and yields weird values).

That should not occur with the code as posted.

Your current code only uses pointers to valid integers. But most of those don't point into your array, so what you do is not a search in your array. The program simply does calculations with integers. Only the values of the first and last element of your array are ever used.

The program is confusing, because you pass around the integer values as pointers to their storage. While you start with pointers into your array, you then mix in pointers to automatic variables (beginand end), where you have stored a calculated value. (You never use pointers to array elements other than the first and last.

Collectives™ on Stack Overflow

Recursive binary search implementation is crashing... why?

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related