探索アルゴリズム【search algorithm】

概要

探索アルゴリズム（search algorithm）とは、コンピュータプログラムなどに実装される計算手順(アルゴリズム)の一種で、データ集合などの中から指定の条件に合致する要素を見つけ出すもの。

何かを探し出す手順を定式化したもので、探す対象は単体の数値であったり、特定のパターンに一致する文字列であったり、目的地までの最短経路であったり、将棋の最も有利な一手であったりする。データ構造や問題の種類によって様々なアルゴリズムが考案されている。

リスト探索

最も基本的な探索問題はリスト探索で、配列などに一列に並べられた要素の中から指定されたものを探し出す手順を考えるというものである。最も単純な探索法は「線形探索」（linear search）で、端から順に要素を照合していく方法である。効率は最も悪いがどんなリストでも探索することができる。

大きい順または小さい順に要素が並んだリストであれば「二分探索」（binary search）を用いることができる。全体の半分の位置にある要素を探している値と比較し、値が含まれる側の半分に絞り込む。次に絞り込んだ半分のリストの中央の値と比較し、四分の一に絞り込む。この手順を候補が一つになるまで繰り返せばよい。

二分探索と同じ原理だが、常にリストの真ん中の要素と比較するのではなく、大きさとリスト内の位置がほぼ比例していると仮定して探索値に近い値が出現しそうな位置を予想する手法を「内装探索」という。他にも、リストからハッシュテーブルや平衡二分探索木などのデータ構造を作り出して探索を効率化する手法などが知られている。