線形探索

配列に格納されたデータを先頭から順番に探していく方法です。先頭から順にノードをたどりながら、

   1. データが同じであるかの比較処理
   2. 配列の終端まで検索したかの検査処理

の2つの処理を絶えず行なうことで実現します。

もし、その配列がソーティングされているのであれば、2分探索アルゴリズムを用いることができます。

線形探索アルゴリズムの改良
線形探索についても工夫をすることで、処理を削減することができます。

番兵法アルゴリズム
    線形探索アルゴリズムを高速にするための工夫をしたアルゴリズムです
  • 配列の末尾に検索結果(ダミーデータ)をおく
この方法により、データが同じかという比較と、終端まできたかの検査を同一にできます。つまり、
  • (本物かダミーか関わらず)データが見つかったら、ループから抜ける
  • 本物かダミーかの判定は、ループから抜けた後に確認する
といった方法をとります。これにより、ループ内のステップが1つ削減できますので、探索スピードを向上することができます。

Comments