線形探索｜科目A-1 令和7年 秋期午前試験 問6
出典：令和7年秋期 午前 問6
分野：アルゴリズムとプログラミング ／ アルゴリズム
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。
- ア：m＋n/m
- イ：m/2＋n/2m
- ウ：n/m
- エ：n/2m
TSUNAGARU-ADVICE
まず押さえたいこと
この探索方法は、表全体をいきなり線形探索するのではなく、まず各ブロックの最後尾だけを見て、目的データがあるブロックを絞り込む方法です。その後、見つけたブロック内を線形探索します。平均比較回数は、ブロックを探す比較回数とブロック内を探す比較回数を足すと考えます。
迷ったときの判断軸
ブロック数はn/m個なので、目的のブロックを見つけるまでの平均比較回数はその半分程度です。また、ブロック内にはm個のデータがあるため、目的データを見つけるまでの平均比較回数もその半分程度です。「全体の半分を探す」のではなく、「ブロック数の半分」と「ブロック内データ数の半分」に分けて考えると判断しやすくなります。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、探索アルゴリズムを単なる公式暗記ではなく、データ構造をどう分割すると処理回数を減らせるかという観点で理解しておくと有効です。科目Bでは、性能見積りや処理効率の改善案を考える問題につながります。
表全体のデータ数はn個で、1ブロック当たりm個のデータに分けるので、ブロック数はn/m個です。
まず、各ブロックの最後尾のデータだけを線形探索して、目的のデータが含まれるブロックを探します。ブロック数がn/m個あるので、平均比較回数はおよそ次のようになります。
ブロック探索の平均比較回数 ＝ n/2m
次に、見つけたブロック内を線形探索します。1ブロックにはm個のデータがあるので、ブロック内探索の平均比較回数はおよそ次のようになります。
ブロック内探索の平均比較回数 ＝ m/2
したがって、全体の平均比較回数は、次の式で表せます。
m/2＋n/2m
したがって、イが適切です。