平成21年度 春期 応用情報技術者試験 午前 問8
相異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，m は十分大きく，n は m の倍数とし，目的のデータは必ず表の中に存在するものとする。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
-
ア: m ＋ n／m
誤り。ブロック数は n／m 個です。ブロックを探す線形探索の平均比較回数はブロック数の約半分，ブロック内の線形探索の平均比較回数は m の約半分になるので，m ＋ n／m は平均ではなく最大比較回数に近い式です。 -
イ: m／2 ＋ n／(2m)
正しい。ブロックは n／m 個あり，各ブロックの最後尾を線形探索して目的のブロックを見つけるまでの平均比較回数は約 (n／m)／2 ＝ n／(2m) 回です。次にブロック内（m 個）を線形探索する平均比較回数は約 m／2 回です。m が十分大きいので端数を無視すると，合計は m／2 ＋ n／(2m) になります。 -
ウ: n／m
誤り。ブロック数そのものであり，ブロック内の探索回数が含まれていません。 -
エ: n／(2m)
誤り。ブロックを探す部分の平均比較回数だけで，ブロック内の探索回数（約 m／2）が含まれていません。
答え
イ: m／2 ＋ n／(2m)
出典：平成21年度 春期 応用情報技術者試験 午前 問8
