はじめに
エンジニアであれば最低限知っておきたいアルゴリズムの知識のうち、探索に関してまとめました。
以下の記事も参考にしてください。
アルゴリズム入門①計算量とソートの基本
アルゴリズム入門②実用的なソート
探索とは
探索(あるいは検索)とは、データの集合の中から目的の要素を探し出す処理
です。基本的な探索のアルゴリズムは以下の三つです。
- 線形探索
- 二分探索
- ハッシュ法
1. 線形探索(linear search, sequential search)とは
配列の先頭から各要素を目的の値と等しいかどうか調べていく方法です。
効率は悪いですが、データの並び方に関係なく適用することができます。
計算量は$O(n)$になります。
練習問題
Linear search | Aizu Online Judge
2. 二分探索(binary search)とは
ソート済みの配列から、データの大小関係を利用して高速に探索を行う方法です。
以下のように探索を行います。
- 配列の中央の要素を取り出す。
- 目的のキーが中央の要素のキーと一致すれば、探索を終了する。
- 目的のキーが中央の要素のキーより小さければ前半を、大きければ後半を探索の範囲として1へ戻ります。
以上のような形で探索を行うことで、毎回探索の範囲が半分になっていくので、高速に探索を行うことができます。
計算量は$O(logn)$になります。
練習問題
Binary Search | Aizu Online Judge
3. ハッシュ法とは
ハッシュテーブルと呼ばれる表を用いたアルゴリズムで、ハッシュ関数(hash function)によって、要素の格納場所を調べるため、$O(1)$で探索することができます。
- 要素のキーを引数とし、ハッシュ関数の呼び出しを行う。
- 1で得た値で位置を特定する。