[解決済み] 修正方法 - コントロールが非ボイド関数の終わりに達する可能性があります。

質問事項

cs50の授業で、バイナリサーチ関数を書かなければならない問題が発生しました。 コードを実行しようとすると、このようなメッセージが表示されます。 control may reach end of non-void function . 私は最後の行を追加することによって修正しようとしました return false が、これでは出力が常に false . 何かヒントがあれば教えてください。

以下は私のコードです。

bool search_r(int value, int values[], int l, int r) {
    int v = values[(l + r) / 2];
    int right = r;
    int left = l;
    if ((l + r) / 2 > 0) {
        if (v == value) {
            return true;
        } else 
        if (v > value) {
            right = ((l + r) / 2);
            search_r(value, values, left, right);
        } else
        if (v < value) {
            left = ((l + r) / 2);
            search_r(value, values, left, right);
        }
    } else {
        return false;
    }         
}

解決方法は？

この関数にはいくつかの問題があります。

• を再帰的に呼び出したときの値を返す必要があります。 search_r() . このエラーは、関数に return 文の後に、ネストされた if ステートメントを使用します。それを作ること return false; を返すべきであり、最後に書くのは正しくありません。 true もし value が見つかりました。
• (l + r) / 2 はオーバーフローする可能性があります。 l または r が非常に大きい場合。この場合、結果は正しくないでしょう。正しい中間インデックスの計算方法は次の通りです。 l + (r - l) / 2 .
• 終了のためのテストは (l + r) / 2 > 0 であるかどうかだけをテストします。 > 0 . 代わりに l < r つまり、範囲が空でない場合です。 l が含まれ r を除く。
• テストの様子 if (v < value) は冗長であり、すでに v == value と v > value .
• 使用方法 l と視覚的に非常に似ているため、変数名として使用するとやや混乱します。 1 特にコードに使用される固定ピッチのフォントの場合。

以下は修正版です。

bool search_r(int value, int values[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        int v = values[middle];
        if (v == value) {
            return true;
        } else
        if (v > value) {
            return search_r(value, values, left, middle);
        } else {
            return search_r(value, values, middle + 1, right);
        }
    } else {
        return false;
    }
}

最後に、この関数は再帰を使用する代わりにループとして実装することもできます。 再帰は終端なので、コンパイラは同じコードを生成する可能性が高いが、人によっては一方の方法の方が直感的だと感じることもある。

bool search_r(int value, int values[], int left, int right) {
    while (left < right) {
        int middle = left + (right - left) / 2;
        int v = values[middle];
        if (v == value) {
            return true;
        } else
        if (v > value) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    return false;
}

どちらの場合も、このように関数を呼び出す必要があります。 length の要素数です。 array .

bool found = search_r(value, array, 0, length);