問6 ブロックに分けた探索の比較回数

ほかの選択肢が違う理由

• アブロックの中を最後まで見る m 回と、ブロック探しで全ブロックを見る n/m 回を足した、最悪に近い回数です。平均ではそれぞれ半分になります。
• ウブロックを探す 1 段目だけを、しかも全ブロック分数えた回数です。ブロックの中を探す回数が入っていません。
• エブロックを探す 1 段目の平均の回数だけです。ブロックの中を探す m/2 回が抜けています。

仕組み

線形探索は、前から 1 つずつ比べる探し方です。目的の物がどこにでも同じ確率でありうるなら、平均で全体の半分を見たところで見つかります。

表を区切って 2 段で探すと、全体を 1 段で探すより比較を大きく減らせます。辞書の見出しの「つめ」でページの範囲を決めてから、そのページの中を探すのと同じ考え方です。