探索アルゴリズム
●線形探索法
先頭から順番に目的のデータと比較し、一致するデータを探すアルゴリズム。
整列されていない状態で目的のデータを探索するには向いているが、大量のデータを探索するには不向き。
線形探索法では、 n個のデータの中から目的のデータを見つけるまでに、最小で1回、最大でn回、データの比較を行う必要がある。したがって、平均比較回数は(n+1)/2回となる。
番兵
線形探索法で配列構造のデータを探索する場合、探索する前にあらかじめ最後のデータの後ろに目的のデータを入れておくこと
●2分探索法
あらかじめデータが大きい順もしくは小さい順に整列されている場合に使う。まずデータを2等分し、探索範囲の中央の値と探索データを比較する。探索データの方が小さければ、目的データの場所を前半に絞り込む。これを繰り返す。
平均比較回数はlog2n
●ハッシュ探索法
データ格納場所のアドレス値を、あらかじめ関数を使った計算で決めておくアルゴリズム。
格納先を決めるために用いられる関数をハッシュ関数、ハッシュ関数によって求められるアドレス値をハッシュ値と言う。データを探索する際には、ハッシュ関数を計算してハッシュ値を求めることで、格納場所を割り出す。衝突が発生しない限り、必ず1回でデータを見つけることができる。
衝突が起こった場合には、配列の各要素をリスト構造にして、新しい場所にデータを格納する。
一様分布
ハッシュ探索法において、衝突の確率が最も低くなるのは、ハッシュ値が一様分布にある時である。一様分布とは、サイコロの目の出る確率など、全ての事象が起こる確率が等しい現象である。