解説

ブロック探索法（索引付き逐次探索）の平均比較回数を求めます。n個のデータをmブロックに分割（各ブロックm個）。手順：①各ブロックの最後尾を線形探索してブロック特定→n/mブロックを線形探索する平均比較回数は(n/m)/2＋1/2≒n/(2m)（目的ブロック到達の期待比較回数は(n/m＋1)/2≒n/(2m)）②特定したブロック内を線形探索→m個の中から線形探索の平均比較回数はm/2＋1/2≒m/2（mが十分大きい）。合計平均比較回数＝m/2＋n/(2m)（選択肢b）。これをm＝√nと設定すると最小化でき、最適値は√nとなります。

なぜ他の選択肢は違うのか

選択肢 ア

m＋n/mはブロック探索と内部探索を平均ではなく最大比較回数で計算した場合に相当します。線形探索の平均は1/2を掛ける必要があります。

選択肢 ウ

n/mはブロック数のみを数えた値であり、ブロック内の線形探索回数（m/2）が含まれていません。

選択肢 エ

n/(2m)はブロック特定の平均比較回数のみでブロック内探索分（m/2）が抜けています。

解くときのポイント

ブロック探索の平均比較回数＝「ブロック特定（n/2m）＋ブロック内探索（m/2）」＝m/2＋n/(2m)。最適なmは微分してm＝√nで求まり、最小比較回数はO(√n)。線形探索の平均は(最大値+1)/2≒最大値/2を使う。