基本情報技術者試験(FE)

アルゴリズムとプログラミング

サーチ(探索)

サーチ(探索)
データ群の中から特定のデータが存在するかを調べる処理をサーチ(探索)といい、 サーチ(探索)する特定のデータのことをキーもしくはサーチキーという。
 

線形探索/リニアサーチ

データ群の先頭から順番に特定のデータが存在するかを調べるアルゴリズム。
データ群の量やキー(特定のデータ)の存在位置により、サーチ(探索)時間に大きく影響する可能性がある。

キー「3」を線形探索/リニアサーチした場合

キー

配列番号
データ群

比較1回目




比較2回目




比較3回目





キー「3」がデータ群に存在するかをデータ群の先頭から比較していく。
従って、サーチ(探索)時間はデータの3つ分(矢印の個数分)かかる。


キー「3」がデータ群に存在しなかった場合
キー

配列番号
データ群

比較1回目




比較2回目




比較3回目




比較4回目




比較5回目





キー「3」がデータ群に存在しない場合、データ群全てを比較することになる。
従って、サーチ(探索)時間は全データ分(矢印の個数分)かかる。

 

2分探索/バイナリーサーチ

データ群の中央の値と特定のデータを比較し、特定のデータが含まれるであろう前半もしくは後半のデータ群を対象にすることを繰り返して調べるアルゴリズム。

条件:データ群は、昇順または降順にソート(整列)されている必要がある。


キー「3」を2分探索/バイナリーサーチした場合
キー

配列番号
データ群

比較1回目




配列下限1、上限5
比較2回目

配列下限1、上限2

データ群の中央配列番号3の値「7」とキー「3」を比較し、同一であればサーチ(探索)終了。同一でなければ大小比較を行い、2回目の比較範囲を決める。以上だとキー「3」の方が小さいことから2回目の比較範囲は配列番号1~2となる。


データ群の中央は、比較範囲内配列の上限と下限の平均より算出する。
・比較1回目=(1+5)/2=配列番号3
・比較2回目=(1+2)/2=1.5※1=配列番号2
※1”切り上げ”,”切り捨て”のどちらで可能


キー「3」がデータ群に存在しなかった場合
キー

配列番号
データ群

比較1回目




配列下限1、上限5
比較2回目




配列下限1、上限2
比較3回目




配列下限1、上限1

キー「4」がデータ群に存在しなかった場合
キー

配列番号
データ群

比較1回目




配列下限1、上限8
比較2回目




配列下限1、上限4
比較3回目




配列下限4、上限4

いずれの場合も比較3回目で次の比較範囲が無くなり、サーチ(探索)終了となる。
※以上の例ではいずれも比較3回目で終了しているが、 n個の配列に対する平均比較回数はlog回となる。

比較回数

線形探索/
リニアサーチ
2分探索/
バイナリーサーチ
平均比較回数
 下段:n=100の場合
n/2 log
50回 6回(6.643…)
最大比較回数
 下段:n=100の場合
logn+1
100回 7回

※サーチ(探索)対象データの先頭の方にキーが存在する場合、2分探索/
バイナリーサーチより線形探索/リニアサーチの方がサーチ(探索)時間が短くなる場合がある。

※2分探索/バイナリーサーチを実装する場合、線形探索/リニアサーチには無い事前のソート時間や比較範囲を決める演算時間を考慮する必要がある。

関連資格
  • 公務員
  • 行政書士
  • 司法書士
  • 宅建
  • 不動産鑑定士
  • 公認会計士
  • 土地家屋調査士
  • ビジ法
  • FP
  • 中小企業診断士
  • マン管
  • 前のページに戻る
ページのトップへ戻る