ITパスポート試験 テクノロジ系 練習問題 第45問: 異なる整数が入った要素数200の配列から、ある値を線形探索で探す。探す値は配列の中に必ず一つあり、どの要素番号にある確率も等しいものとする。見つかるまでに値を比

正解: 2. 100.5回

線形探索は、配列の先頭の要素から順に探す値と比較し、一致した時点で終了する方法です。探す値がk番目にあればk回比較するので、どの位置にある確率も等しいときの平均は、（1＋2＋…＋200）÷200＝（200＋1）÷2＝100.5回です（2が正しい）。1の100回は要素数を2で割っただけの値で、正しい平均より0.5回少なくなっています。3の200回は、探す値が最後の要素にある場合の比較回数です。4の8回は、整列済みの200個のデータを2分探索で探すときの最大の比較回数で、線形探索の回数ではありません。

関連キーワード: 線形探索・配列・比較回数・2分探索