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 の値が右よりも大きくなります (実質的に と同じであるためmid = 1.5 * left + 0.5 * right)。これは次のようになります。

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

または、mawia が示唆するように (左 + 右の合計が MAXINT を超えない限り) さらに良い:

mid = ( left + right ) / 2;