[0140] 線形探索,平均探索回数

平成12年度秋期 (旧)第2情報処理技術者試験より
相異なるn個のデータが昇順に整列された表がある。この表を1ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、 m<nとし、目的のデータは必ず表の中に存在するものとする。

正解

解説

 線形探索に関する問題です。

 線形探索とは、検索アルゴリズムのひとつで、あるデータ配列から、特定の要素を検索する場合に利用されます。

■ 線形探索(linear search)

 線形探索では、データ要素を先頭から1つずつ比較して、目的のデータを探索する方法です。下図のデータであれば、“山田”、“佐藤”、“鈴木”、“高橋” の順に、データ要素と目的の文字列を比較しながら探索します。



 また、平均探索回数、つまり、目的のデータにたどり着くまでの平均比較回数は、以下のようにして求めることができます。



※ 平均探索回数は、計算式を単純にするために、n ÷ 2 とする場合があります。


 この問題の場合は、線形探索を (1) 各ブロック最後尾のデータ(2) (1)に該当するブロック内の全データ の 2回行うことになります。(1) (2) について、順に求めていきましょう。なお、平均探索回数については、 n ÷ 2 としている点に注意してください。


(1) 各ブロック最後尾のデータ に対する探索

 探索するデータの範囲を小さくするために、目的のデータがどのブロックにあるかを線形探索を行います。ブロック数は n/m なので、平均探索回数は、



となります。


(2) (1)に該当するブロック内の全データ に対する探索

 最終的に目的のデータを探索するため、(1)で該当したブロックに含まれる全データに対して線形検索を行います。1ブロックに含まれるデータ数は m なので、



となります。


 したがって、(1) (2) と2回、線形探索を行い、最終的に目的のデータにたどり着くためには、それぞれの平均探索回数を加えた、



つまり、選択肢のエが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題