概要
探索アルゴリズムについて、何度勉強しても忘れてしまうので、自分の学習用として、各探索の概要と、理解するためのyoutubeのリンク集を纏めました。
目次
線形探索
データ群の端から順に、探しているデータかあるか確認していく手法。
名前は、データ群の左から右に一直線 (線形) に探索するというやり方から。
「逐次探索」や「リニアサーチ」ともいわれる。
二分探索
検索したい値がデータ群の中央の値より右にあるか、左にあるかを判断し、片方には存在しないことを確かめながら検索していく手法。
ランダムなデータ群だと、中央の値より右にあるか左にあるかの判断ができないため、二分探索を行う前は、ソートアルゴリズムを使用して、データ群を整列させておく必要がある。
ハッシュ探索
「ハッシュ関数」と言われる関数を使用する。
ハッシュ関数とは、同じ入力からは必ず同じ値を得ることができる関数。得られたデータはハッシュ値という。
ハッシュ探索は、最初にデータひとつひとつのハッシュ値を算出しておいて (ハッシュテーブルを作成しておいて) 、探索の対象となるデータをハッシュ値に変換し、ハッシュテーブルを元に探索を行う方法。