c++ - 再帰的二分探索におけるセグメンテーション違反への対処

Question

配列内で探している番号が見つからない再帰的バイナリ検索でセグメンテーション違反を防ぐにはどうすればよいですか。

int recursive_binary_search(int A[], int beg, int end, int key)
{
    if(end < beg)
        return -1;
    int mid = beg + end / 2;
    if(A[mid] == key)
        return mid;
    else if(A[mid] > key)
        return recursive_binary_search(A, beg, mid - 1, key);
    else
        return recursive_binary_search(A, mid + 1, end, key);
}

Answer 1

次のコードで十分かもしれませんが、

int recursive_binary_search(int A[], int beg, int end, int key)
{
    if(end < beg)
        cout<<"\nKey not Found";
    int mid = beg + end / 2;
    if(A[mid] == key)
        return mid;
    else if(A[mid] > key)
        return recursive_binary_search(A, beg, mid - 1, key);
    else
        return recursive_binary_search(A, mid + 1, end, key);
}

Answer 2

()の定義の周りを忘れていたことがわかりましたmid。

定義を次のように修正します。

int mid = (beg + end) / 2;

問題を修正しました。