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

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

解答：イ

＜解説＞

各ブロックを表中の1つの要素とすれば、表にはm/m個の要素がある。

これを順次検索する場合、目的のブロックが見つかるまでには最短で1回，最長でn/m回の系ン作が必要になる。平均すると(n/m+1)÷2≒n/2mである。

このブロック内を順次探索するので平均m/2解の検索で当該ブロック中に存在する検索値が発見できる。

よってイが正解である。