我在第一次递归调用时收到一个错误,错误:
Unhandled exception at 0x002A2E44 in rekBinSearch.exe: 0xC0000005: Access violation reading location 0x0000000A.
这是由于:
if ((*pEnd - pBegin) == 0) / There's only one element */
似乎当我设置新的起始地址和结束地址时,我做错了什么,因为在递归调用中无法读取这些地址。它们由以下人员“设置”:
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
我哪里做错了或者我怎么想错了?
最佳答案
What am I doing wrong or how am I thinking wrong?
问题一
您混淆了指针和值。示例:
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
关于c++通过递归进行二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33244552/