Namaran

Code daily. Without assist.

2026-09-13

binary_search.c

#include <stddef.h>

// Returns the index of key in the sorted range a[lo, hi), or -1.
int search(const int a[], size_t lo, size_t hi, int key) {
    if (lo >= hi)
        return -1;

    size_t mid = lo + (hi - lo) / 2;
    if (a[mid] == key)
        return (int)mid;

    if (a[mid] < key)
        search(a, mid + 1, hi, key);
    else
        search(a, lo, mid, key);
}

手元のテストではsearchは正しいインデックスを返していましたが、別のコンパイラで最適化を有効にしたら結果がおかしくなりました。何が問題で、どう直せばよいでしょうか?

Answer

再帰呼び出しの結果をreturnしていません。最初の比較で見つからなかった場合、内側のsearchが値を返しても外側はそれを捨て、return文のないまま関数の終わりの}に到達します。値を返す関数がそうやって終わり、呼び出し側がその値を使うのは未定義動作です。「たまたま動いていた」のは、内側の呼び出しが戻り値を置いたレジスタがそのまま残っていただけで、最適化の仕方次第でゴミ値にも暴走にもなります(-Wallなら警告が出ます)。再帰の結果をそのまま返せば直ります: 

if (a[mid] < key)
    return search(a, mid + 1, hi, key);
else
    return search(a, lo, mid, key);

「区間が空なら-1、真ん中が当たりならその位置、そうでなければ半分の区間の答えがそのまま全体の答え」という定義を、各分岐がそれぞれreturnで言い切る形になります。