探索【search】

概要

探索（search）とは、未知の物事を探し求めること。情報科学では、データ集合などの中から指定の条件に合致する要素を見つけ出す操作を探索という。

データの探索

何らかのデータ形式やデータ構造として集められたデータの集合に対して、一定の手順に基づいて指定の条件を満たすデータを探し出し、一致したデータやその位置を明らかにする（あるいは対象の中には存在しないことを確定させる）操作のことを「探索」（search）という。

探索アルゴリズム

コンピュータなどで実行できるよう定式化された探索手順のことを「探索アルゴリズム」（search algorithm）という。例えば、最も単純な方法として、一列に並べたデータ列に対して端から順に指定の条件に一致するか照合する方法がある。これを「線形探索」（linear search）という。

また、順位や大小が比較できるデータ群であれば、大きい順または小さい順に整列（並べ替え）して、目的のデータと半分の位置にあるデータを比較すれば、含まれる方の半分に絞り込むことができる。残ったデータ群の半分の位置と比較すれば、もう半分に絞り込める。これを繰り返して残りが一つになれば探索完了となる。この方法は「二分探索」（binary search）と呼ばれる。

線形探索では一回の比較で一つしか候補が減らないため、平均してデータの個数に比例した回数の比較が必要となる（これを $O (n)$ と表記する）が、二分探索ならば一回の比較で候補を半分に減らせるため、平均してデータの個数の2を底とした対数で済む（これを $O (\log n)$ と表記する）。

このように、探索する対象の特性に適したアルゴリズムを選択することで効率的に探索を行うことができる。文字列内の特定のパターンを探索するためのアルゴリズムや、木構造やグラフなどのデータ構造に格納された要素を探索するためのアルゴリズムなどがよく知られている。

検索との違い

ITの分野では「検索エンジン」「全文検索」のようにデータ群から条件に一致するものを探し出す操作を「検索」と呼ぶこともある。いずれも英語では “search” であり、意味や用法に明確な違いはないが、慣例として情報科学などの学問分野では「探索」の語が、探索法を応用した具体的なシステムやサービスなどでは「検索」の語が好まれる。

(2024.5.29更新)