応用情報技術者試験 令和7年度 秋期 午前 問6
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、mは十分に大きく、nはmの倍数とし、目的のデータは必ず表の中に存在するものとする。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】イ
この探索方法はブロック探索（インデックス付き順次探索）です。
【ステップ1：ブロックの特定】 n個のデータをm個ずつに分割すると、ブロック数は n/m 個です。各ブロックの最後尾を線形探索するので、平均比較回数は (n/m + 1) / 2 ≒ n/(2m) 回です（mが十分大きいので+1は無視できる）。
【ステップ2：ブロック内の探索】 ブロック内にはm個のデータがあり、これを線形探索するので、平均比較回数は (m + 1) / 2 ≒ m/2 回です。
【合計】 平均比較回数 = n/(2m) + m/2 = (m/2) + (n/2m)
したがって、イの (m/2) + (n/2m) が正解です。
アの m + n/m は、両段階とも最悪の場合の比較回数です。ウの n/m はブロック数であり比較回数ではありません。エの n/2m はブロック特定の平均比較回数のみです。
【ポイント】 線形探索の平均比較回数は（要素数＋1）/2です。ブロック探索では、ブロック数の最適値は m = √n のときに合計比較回数が最小（√n回）になることも覚えておくとよいでしょう。
出典：令和7年度 秋期 応用情報技術者試験 午前 問6
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の80問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる