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

Question

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

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

原因是：

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

似乎当我设置新的起始地址和结束地址时，我做错了什么，因为在递归调用中无法读取这些地址。他们 "set" 来自：

find(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

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

问题 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)吗？请注意，没有解引用指针。取消引用挂起总是一个坏主意，因为它不指向任何东西。

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

c++ Binary search through recursion

c++

recursion

binary-search-tree