c ++通过递归的二进制搜索

Question

在进行第一次递归调用时收到错误，错误：

rekBinSearch.exe中0x002A2E44的未处理异常：0xC0000005：访问冲突读取位置0x0000000A。

是由于：

if（（（* pEnd-pBegin）== 0）/只有一个元素* /

似乎当我设置新的起始地址和结束地址时，我做错了，因为在递归调用中无法读取这些内容。通过以下方式“设置”：

查找（x，（int *）pBegin，pMid）;

完整代码：

    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

我在做什么错或我怎么想错？

Answer 1

我在做什么错或我怎么想错？

问题1

您在指针和值之间感到困惑。范例：

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

和

if (x == (int)pEnd)

int(pEnd)不会获得pEnd指向的对象的值。它只是将指针值视为int。

问题2

此外，您没有从递归调用中正确返回。

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

和

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

固定功能

这里是应该工作的版本。

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

Answer 2

您要if ((pEnd - pBegin) == 0)吗？请注意，没有取消引用指针。取消对pend的引用总是一个坏主意，因为它没有指向任何内容。