c++ Binary search through recursion

Question

I receive an error when the first recursice call is made, the error:

Unhandled exception at 0x002A2E44 in rekBinSearch.exe: 0xC0000005: Access violation reading location 0x0000000A.

It is caused by:

if ((*pEnd - pBegin) == 0) / There's only one element */

It seems that that when i set the new start- and end-adress, i do something wrong since these can't be read on the recursive call. They are "set" by:

find(x, (int*)pBegin, pMid);

Full code:

    bool find(const int x, const int* pBegin, const int* pEnd)
{
   if ((*pEnd - *pBegin) == 0) /* There's only one element */
    {
        if (x == (int)pEnd)    /* That element could be the correct one */
            return true;
        else                   /* If it is not then return false, x is not in the array */
            return false;
    }

    int *pMid = (int*)(pEnd - pBegin);  /* pMid should be the adress to the element in the middle of the array */
    if (x >= (int)pMid)                 /* If x is in array it is to the right of the middle */
        find(x, (int*)pMid, pEnd);  
    else                                /* If x is in array it is to the left of the middle */           
        find(x, (int*)pBegin, pMid);

}// find

What am I doing wrong or how am I thinking wrong?

Get rid of all those casts and you'll be half-way to solving the problem, I suspect. — davmac
– davmac, Commented Oct 20, 2015 at 18:53
(pEnd - pBegin) doesn't compute a midpoint, but the number of elements between the pointers. Perhaps there are 0x0A elements? — Bo Persson
– Bo Persson, Commented Oct 20, 2015 at 18:59
The idiomatic use of an iterator like syntax is to treat equality of the beginning and ending to indicate an empty interval. Your function does not detect being passed an empty array. — jxh
– jxh, Commented Oct 20, 2015 at 19:15

Dharman · Accepted Answer · 2020-03-21 21:04:40Z

2

What am I doing wrong or how am I thinking wrong?

Problem 1

You are confusing between pointers and values. Examples:

if ((*pEnd - *pBegin) == 0) /* There's only one element */

and

if (x == (int)pEnd)

int(pEnd) does not get the value of the object that pEnd points to. It just treats the pointer value as an int.

Problem 2

Also, you are not returning properly from the recursive calls.

    find(x, (int*)pMid, pEnd);  // Missing return

and

    find(x, (int*)pBegin, pMid); // Missing return

Fixed up function

Here's a version that should work.

bool find(const int x, const int* pBegin, const int* pEnd)
{
   if ((pEnd - pBegin) == 0) /* There's only one element */
   {
      return (x == *pEnd);  /* That element could be the correct one */
                            /* If it is not then return false, x is not in the array */
   }

   int midIndex = (pEnd - pBegin)/2;
   int const* pMid = pBegin + midIndex; /* pMid should be the adress to the element in the middle of the array */
   if (x >= *pMid)                     /* If x is in array it is to the right of the middle */
      return find(x, pMid, pEnd);  
   else                                /* If x is in array it is to the left of the middle */           
      return find(x, pBegin, pMid-1);

}// find

edited Mar 21, 2020 at 21:04

Dharman♦

34k27 gold badges106 silver badges158 bronze badges

answered Oct 20, 2015 at 18:52

R Sahu

207k15 gold badges168 silver badges291 bronze badges

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

2 Comments

NoseKnowsAll Over a year ago

I think it would be helpful to OP to reiterate that (int)pEnd does not return the int value pointed to by pEnd. In order to get the value of a pointer, you use (as you've correctly done in your fixed function) *pEnd.

MattiasLarsson Over a year ago

@R-Sahu I missed to give feedback, sorry. This helped a lot, thanks!

Robert Jacobs · Accepted Answer · 2015-10-20 18:54:55Z

0

Do you want if ((pEnd - pBegin) == 0)? Notice that there is no dereference pointers. Dereferencing pend is always a bad idea since it doesn't point to anything.

answered Oct 20, 2015 at 18:54

Robert Jacobs

3,3701 gold badge22 silver badges31 bronze badges

Collectives™ on Stack Overflow

c++ Binary search through recursion

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