基本情報技術者試験 - 令和5年1月修了 - 問9

異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。

ア	$m + \frac{n}{m}$
イ	$\frac{m}{2} + \frac{n}{2 m}$
ウ	$\frac{n}{m}$
エ	$\frac{n}{2 m}$

◀ 問8　|　▲ 令和5年1月修了問題一覧　|　問10 ▶

答え：イ
分野：テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム
解説：
この探索方法は，n個のデータをm個ごとのブロックに分割し，まず各ブロックの末尾のデータだけを線形探索してブロックを特定し，その後ブロック内を線形探索するという二段階の方式です。

ブロックの数はnをmで割った値になります。ブロックを特定するための平均比較回数は，線形探索の性質上，ブロック数の半分程度になるため，（n/m）を2で割った値，すなわちn÷（2m）となります。

次に，目的のブロックが見つかった後，そのブロック内をさらに線形探索するため，平均してブロックサイズmの半分の比較回数，すなわちm/2が必要になります。この二つを足し合わせることで，全体の平均比較回数はm/2にn/（2m）を加えた式で表されます。これが選択肢「イ」の内容と一致します。

他の選択肢は，線形探索の平均比較回数を求める際に半分にする処理を忘れていたり，片方の探索段階の計算を省いていたりする誤りが含まれています。