令和7年度 秋期 応用情報技術者試験 午前 問6
異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、m は十分に大きく、n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
表を m 個ずつのブロックに分けると、ブロック数は n/m 個になります。
まず、各ブロックの最後尾のデータだけを線形探索して、目的のデータが含まれるブロックを探します。このとき、目的のデータはどのブロックにある可能性も同じなので、平均すると全ブロック数 n/m の半分程度を調べることになります。したがって、この段階での比較回数の平均はおおよそ n/(2m) 回になると考えられます。
次に、見つかったブロック内（要素数 m 個）を線形探索します。ブロック内のどの位置に目的のデータがある可能性も同じなので、平均するとブロック内の要素数 m 個の半分程度を調べればよいことになります。したがって、この段階での平均比較回数はおおよそ m/2 回になります。
以上より、全体の平均比較回数は
m/2 + n/(2m)
と表すことができます。
答え
イ: m/2 + n/(2m)
出典：令和7年度 秋期 応用情報技術者試験 午前 問6
