Hayato式！！　　応用情報技術者試験　　　　　　　　　～～アルゴリズム編その１～～

1⃣　探索アルゴリズム

～そもそも探索とは？～
探索とは言葉の通り、ある要素の内容を調べていくってこと！！
探索には以下のような種類がある…..

①　線形探索

線形探索とは、ある要素の先頭から1つずつ探索したいものに合致しているかどうかを調べていく方法のこと。
簡単に言えば、先頭から調べていくってこと！！

②　2分探索

２分探索とは、ある要素の中央の要素から探索したいものに合致しているかどうかを調べていく方法のこと。
簡単に言えば、中央から調べていくってこと！！

③　ハッシュ探索

ハッシュ探索とは、探索したいものを予めハッシュ関数でおき、その関数を演算して変更した結果を添えて調べていく方法のこと。
簡単に言えば、要素を数字でおいておくってこと。

～ハッシュ探索の問題点と対策～

・問題点

ハッシュ関数によって演算するとたまに異なるものが演算結果を同じとみなすことがあります。われわれはそれを衝突と呼び、基本的に衝突さえ起こらなければ計算は一定です。

・対策

衝突が発生すると、自分の欲しいデータが手に入れられなかったり、そもそも調べることができないという事態に陥ります。
そんな衝突が起きた際の対策法の代表例にオープンアドレス法とチェイン法って呼ばれるものがあります。

①　オープンアドレス法

オープンアドレス法とは、衝突が発生したとき調べたい要素のハッシュ値を再び計算する再ハッシュという手法で対処する方法です。
オープンアドレス法は別名、クローズドハッシュ法とも呼びます。

②　チェイン法

チェイン法とは、同じハッシュ値の要素をリストと呼ばれるものに入れることである。衝突が発生した要素を、ポインタでつないでいきます。

～それぞれの探索法の比較～

今まで３つの探索法を紹介してきたが、それぞれの探索法の有効性を説明していく。

2分探索では、要素の値が昇順か降順になっている配列の探索に有効です。
それ以外（要素の値の並びがぐちゃぐちゃ）の時には線形探索が有効です。
ハッシュ探索では、高速な探索を行えとても便利なのですが、衝突が発生したときには、対策を考える必要がある。

これで探索アルゴリズムの内容は終了です！
これを理解したら過去問道場などで演習しましょう！
次回は整列アルゴリズムになります。