データを探索するアルゴリズム

線形探索法

先頭から順に探索していく方法

2分探索法

あらかじめ探索対象のデータ群が「昇順に並んでいる」「降順に並んでいる」といった規則性を持つ場合は2分探索法という、より効率の良い方法を取ることができる

  1. データの真ん中の数字と見つけたい数字とを比較する
  2. それより大きい(小さい)で半分捨てて、半分残す
  3. 残した半分のデータの真ん中の数字と見つけたい数字を比較する
  4. 大きい(小さい)で残す、捨てるを判断する

ハッシュ法

ハッシュ関数と呼ばれる「一定の計算式」を用いて、データの格納位置をずばり算出する探索方法

  1. データをハッシュ関数に放り込む
  2. 放り込んだら計算結果が返ってくる
  3. その計算結果の数値の配列位置にデータを保管する

各アルゴリズムにおける探索回数

  • 線形探索法:(1+n)÷2 … 最少は1回、最大はN回で平均を取るのでこの計算式
  • 2分探索法:log2n
  • ハッシュ法:1回
タイトルとURLをコピーしました