为什么会出现分段错误以及如何解决它

Question

#include<iostream>
using namespace std;
int BSearch(int array[],int key,int left,int right)
{
    if(array[left+right/2]==key)
        cout<<left+right/2;
    else if(array[left+right/2]<key)
        BSearch(array,key,left,right/2-1);
    else 
        BSearch(array,key,right/2,right);

}

int main()
{
int list[]={1,2,3,4,5,6,7,8,9,11,15,21};
BSearch(list,5,0,sizeof(list)/sizeof(int)-1);
}

我写这个程序是为了进行二分查找。我每次运行都会遇到分段错误。

Answer 1

在这里查看：

if(array[left+right/2]==key)

并专注于此 left+right/2。在这里，运算符的优先级开始发挥作用。您的意思可能是左右相加，然后将总和除以二。

但是，它会先将右边除以二，然后再将其加到左边。

所以改变：

left+right/2

至：

(left+right)/2

无处不在 你需要。

而且，你的逻辑有问题。我已经在 Binary Search (C++), but even Wikipedia 中写了一个例子可以在这里提供帮助。您的代码适用于此：

#include <iostream>
using namespace std;

void BSearch(int array[], int key, int left, int right) {
    if (array[(left + right) / 2] == key) {
        cout << "found at position " << (left + right) / 2;
        return;
    } else if (array[(left + right) / 2] > key) {
        BSearch(array, key, left, (left + right)/ 2 - 1);
    } else {
        BSearch(array, key,  (left + right)/ 2 + 1, right);
    }
}

int main() {
    int list[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15, 21};
    BSearch(list, 5, 0, sizeof(list) / sizeof(int) - 1);
}

输出：

found at position 4

Answer 2

其实正确的做法并不是

(left+right)/2

但是

left + (right - left)/2

不同之处在于，在处理大型列表时，第一个变体存在溢出问题（带符号整数的未定义行为，不按预期方式使用无符号）。

让我们说明范围为 0..255 无符号和 -128..127 有符号的 char 类型（int 范围更大，但问题仍然存在）。

假设您要查找有符号字符 40 和 100 的中间值：

第一个表达式 [(left+right)/2] 的结果是：(40+100)/2 = (-116)/2 = -58（技术上未定义，40+100 字符在标准二进制补码实现中只会是 -116，但这不是由C/C++ 标准）
第二个[left + (right - left)/2]的结果是40 + (100-40)/2 = 40 + (60)/2 = 40 + 30 = 70

无符号字符 100 和 250:

第一个：(100 + 250)/2 = (94)/2 = 47
第二个：100 + (250 - 100)/2 = 100 + 150 / 2 = 175

对于递归调用，您需要提供沿 "middle" 点的范围（再次 L + (R-L)/2 而不是 R/2）。

特别是Wikipedia article中也提到：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… (Donald Knuth)

Answer 3

您必须在第二个 if 语句中将小于号更改为大于号：else if(array[(left+right)/2]>key) 因为您搜索反面。

并且您必须在第三个 if 语句中将 right/2 更改为 (left+right)/2，因为 left 可能不是 0，并且 right/2 不会更正。你必须从中间到右边搜索。解决方案是

#include <iostream>

using namespace std;

int BSearch(int array[],int key,int left,int right)
{
    if(array[(left+right)/2]==key)
        cout<<(left+right)/2 << endl;
    else if(array[(left+right)/2]>key)
        BSearch(array,key,left,(left+right)/2-1);
    else 
        BSearch(array,key,(left+right)/2+1,right);
}

int main()
{
    int list[]={1,2,3,4,5,6,7,8,9,11,15,21};
    BSearch(list,5,0,sizeof(list)/sizeof(int)-1);
}

Answer 4

其他答案中讨论的括号问题肯定是个大问题，必须解决。但是，我不认为这是导致段错误的原因。

第一次调用BSearch()时，left和right分别为0和11。 5 是（错误地）计算出的索引，指向值 6。因此，调用 BSearch() 的最后一行，为 left 和 right 传递 5 和 11。

再次执行函数，最后一行再次调用，再次传递5和11，无穷大.

您必须更正 BSearch() 计算传递给自身的索引的方式。

为什么会出现分段错误以及如何解决它

Why am I getting segmentation fault and how to resolve it

c++

algorithm

binary

binary-search

segmentation-fault