目次（まとめ）
◾️ 線形探索法では、配列の先頭から順番に探し出す
◾️ 2分探索法では、整列済み配列を2つに分けながら探し出す
◾️ ハッシュ法では、ハッシュ関数で決められた位置にあるデータを取り出す
◾️ 参考文献
こんにちは、みっちゃんです。
今回の記事では、配列の中から目的のデータを探し出す基本的な方法の仕組みを紹介します。
ここでは、例えば、以下のような数字の配列が与えられているとして、「4」という数字を探し出す方法を考えます。
| 5 | 6 | 2 | 9 | 4 | 5 | 1 | 4 | 10 | 3 |
線形探索法では、配列の先頭から順番に探し出す
目的のデータを探し出す方法の中で、一番シンプルな方法は「線形探索法」です。
この方法では、与えられた配列の左端から順番に、目的のデータ（ここでは "4"）を探していきます。
配列の中のすべての数字を俯瞰して見える状態であれば、「"4" は左から5番目にある」と一瞬でわかりますが、俯瞰してみることができないコンピュータにとっては、難しい問題になります。
そこで、配列の先頭の数字を見て「"5" は "4" ではない」「"6" は "4" ではない」という判断を繰り返して、目的のデータを探し出します。
この方法では、目的のデータが左端にあれば、1回の探索で見つけ出せる一方、もし右端にあれば、10回の探索で見つけ出すことになります。
したがって、配列の長さが \(n\) であれば、平均 \(\frac{1+n}{2}\) 回で探し出すことができる方法です。
2分探索法では、整列済み配列を2つに分けながら探し出す
「2分探索法」と呼ばれる手法では、あらかじめ以下のように数字の大小にしたがって並び替えた配列を使って、目的のデータ（ここでは "4"）を探し出します。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
"2分" 探索法なので、"2つに分けて" 探索していきます。
2つに分けるとき、分けられる点は "5.5" になりますが、この値を "4" と比較すると、"5.5" より小さいので、2つに分けた配列のうち、左半分に目的のデータが存在することになります。
この操作を繰り返すことで、目的のデータを探し出します。
2分探索法では、配列の長さが \(n\) のとき、\({\rm log}_2 n\) 回で目的のデータを探すことができます。
したがって、配列の長さが "2" であれば1回、"4" であれば2回、"8" であれば3回となります。
ハッシュ法では、ハッシュ関数で決められた位置にあるデータを取り出す
「ハッシュ法」は、目的のデータを探しやすいように、あらかじめ決められた位置にデータを保存しておく手法です。
データを保存する "位置" を決めるために用いられるのが「ハッシュ関数」と呼ばれるもので、よく "mod" 関数を例に説明されます。
"mod" 関数は、与えられたデータを決められた数字で割ったときの "余り" の値を計算します。
得られた "余り" の値に対応する位置に、データを保存します。
このように保存しておくと、目的のデータを探す場合には、そのデータを決められた数字で割ったときの "余り" を計算して、その位置を見れば、簡単にデータを探し出すことができるという仕組みです。
この方法では、原理的に、1回で目的のデータを探し出すことができます。
参考文献
きたみりゅうじ「キタミ式イラストIT塾 応用情報技術者」技術評論社
