アルゴリズムとプログラミング配列操作（線形探索）

n 個の要素を持つ整列されていない配列から、線形探索（逐次探索）で特定の値を探すときの平均比較回数として最も適切なものはどれか。ただし探索する値は必ず配列中に存在するものとする。

ア.n/2 回正解

イ.n 回

ウ.log₂n 回

エ.1 回

解説

線形探索は「落し物を部屋の端から順に探す」捜索。運が良ければ1番目で見つかり、運が悪ければ最後の n 番目。平均すれば「部屋のちょうど真ん中」、つまり n/2 回で見つかるのが期待値。

なぜアが正解か

探索対象が配列中に必ず存在する場合、最良ケースは1回（先頭）、最悪ケースは n 回（末尾）の比較が必要。全要素が等確率で対象となると仮定すると、平均比較回数は (1+2+…+n)/n = (n+1)/2 ≈ n/2 回となる。したがって O(n) であり、平均的には n/2 回が正しい。

なぜイは間違いか

n 回は最悪ケース（対象が末尾にある場合）の比較回数。平均ではなく最悪ケースを答えてしまった誤り。

なぜウは間違いか

log₂n 回は二分探索の平均・最悪比較回数。二分探索はソート済み配列が前提であり、線形探索とは異なるアルゴリズム。探索アルゴリズムを混同した誤り。

なぜエは間違いか

1回で見つかるのはハッシュ探索の理想ケースや、先頭に目的値がある幸運なケース。線形探索の一般的な平均ではない。

出典: AI生成問題（学習用）

← 前の問題

要素数 n の配列の先頭（インデックス0）に新しい要素を挿入するとき、既存要素の移動回数として正しいものはどれか。ただし配列のサイズは十分に確保されているものとする。

次の問題 →

C言語において、整数変数 x のアドレスが 0x1000 であり、x の値が 42 であるとする。ポインタ変数 p を `int *p = &x;` と宣言したとき、`*p` の値と `p` の値の組合せとして正しいものはどれか。