最終更新日：2026年7月13日
fe fe-technology algorithm search
まず結論
ブロック探索の平均比較回数は、公式として丸暗記しなくても求められます。
1. 目的のデータがあるブロックを探す
2. 見つけたブロックの中を探す
データが全部で n個、1ブロックが m個なら、平均比較回数は、
[ \frac{n}{2m}+\frac{m}{2} ]
です。
大切なのは、外側を半分、内側も半分探すという考え方です。
直感的な説明
辞書をいくつかの束に分けて探す場面を考えます。
まず、各束の最後のページだけを見て、目的の言葉がどの束にあるかを探します。
次に、見つけた束の中を先頭から順に探します。
束を探す
→ 束の中を探す
この2段階がブロック探索です。
定義・仕組み
昇順に並んだ n個 のデータを、1ブロック m個 ずつに分けます。
ブロック数は、
[ \frac{n}{m} ]
個です。
各ブロックの最後尾を順番に比較し、目的のデータが含まれるブロックを特定します。その後、ブロック内を線形探索します。
科目Aでどう出る？
第1段階：ブロックを探す
ブロック数は n/m 個です。
線形探索の平均は、おおよそ半分まで調べると考えるので、
[ \frac{1}{2}\times\frac{n}{m}=\frac{n}{2m} ]
回です。
第2段階：ブロック内を探す
1ブロックには m個 のデータがあります。
その中を線形探索するので、平均比較回数は、
[ \frac{m}{2} ]
回です。
2つを足す
したがって、
[ \frac{n}{2m}+\frac{m}{2} ]
となります。
公式を覚えずに解く方法
次の順番で式を作ります。
1. 探索が何段階あるか確認する
2. 各段階の探索対象数を求める
3. 線形探索なら平均は約半分
4. 各段階の比較回数を足す
この条件では、
ブロック探索：n/(2m)
ブロック内探索：m/2
と復元できます。
よくある誤解・混同
ブロック数をm個と考える
1ブロックに m個 入るので、ブロック数は n/m 個です。
最大比較回数で考える
平均比較回数を問われているので、線形探索では約半分まで探すと考えます。
ブロック探索だけで終わる
ブロックを見つけたあと、目的のデータを特定するためにブロック内の探索が必要です。
二分探索と同じだと思う
ブロック探索は、比較のたびに探索範囲を半分にする方法ではありません。
まとめ（試験直前用）
- ブロック探索は2段階
- ブロック数は
n/m - 線形探索の平均は約半分
- 第1段階は
n/(2m) - 第2段階は
m/2 - 公式を忘れても「外側を半分、内側も半分」で復元できる