c++ - 运行时“分段错误”

Question

void binarysearch(string key, vector<string>& f2){
sort_vector(f2);

int mid = 0;
int left = 0;
int right = f2.size();
bool found = false;
while (left < right){
    mid = left + (left+right)/2;
    if (key > f2[mid]){ 
        left = mid + 1;
    }
    else if(key < f2[mid]){
        right = mid;
    }
    else{
        found = true;
        left = right;
    }
}
cout << "out of while loop" << endl;
if (found == true){
    cout << "YES: " << key << endl;
}
else{
    cout << " NO: " << key << endl;
}
found = false;
}

当我运行它时，它会自动终止并显示“分段错误”，但没有给出行号。这甚至意味着什么，为什么我会遇到这个错误？

提前致谢

Answer 1

分段错误意味着程序访问了无效的内存地址。我怀疑在这种情况下，事实是这样的：

mid = left + (left+right)/2;

导致 mid 的值在某些时候大于 right（因为它实际上与 相同mid = 1.5 * left + 0.5 * right）。应该是这样的：

mid = left + ( right - left ) / 2;

或者，更好的是（只要 left + right 的总和不超过 MAXINT），正如 mawia 建议的那样：

mid = ( left + right ) / 2;