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

応用情報技術者試験／2018年度春期午前問6／アルゴリズムとプログラミング / 探索アルゴリズム

選択肢

正解：イ m/2 + n/2m

表はn÷m個のブロックに分かれる。まず各ブロック末尾のデータを線形探索するので、目的のブロックが見つかるまでの平均比較回数はブロック数の半分、すなわちn/2m回である。次に見つけたブロック内でm個のデータを線形探索するので平均m/2回かかる。両者を足したm/2＋n/2mが答えとなる。

出典：平成30年度春期応用情報技術者試験午前問6（IPA）原本の紙面を見る（IPA 問題冊子より）

出典・参考

最終更新：2026-10-06／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。