100個のデータが格納された配列から、線形探索で目的のデータを探す。目的のデータは配列のどの位置にも等しい確率で存在するとき、探索が成功するまでの平均比較回数はいくつか。

解説

正解は「50.5」です。線形探索は先頭から順に比較するので、目的のデータが k 番目にあれば比較回数は k 回です。どの位置にも等しい確率で存在するとき、平均比較回数は1から100までの合計5050を100で割った $5050÷100=50.5$ 回で、一般には $\frac{n+1}{2}$ 回です。「100」は、目的のデータが末尾にある場合や存在しない場合の最大の比較回数です。「50」は n/2 と近似した値で、正確な平均ではありません。「約7」は、ソート済みのデータに対する2分探索の比較回数（${\log }_{2}100$ は約6.6）に近い値で、線形探索の値ではありません。