線形探索

線形探索（リニアサーチ）とは

線形探索は、最も基本的な検索アルゴリズムの一つで、リストや配列に格納されたデータの中から特定の要素を探し出すために用いられます。このアルゴリズムは、データの先頭から順に目的の要素と一つずつ比較を行い、一致する要素が見つかるまで探索を続けます。もしリストの最後まで見つからなければ、その要素はリスト内に存在しないと判断します。

線形探索の仕組み

線形探索の基本的な流れは非常にシンプルです。

1. リストの最初の要素から順に、目的の要素と比較する。
2. もし要素が一致すれば、探索を終了し、その要素の位置を返す。
3. 一致しなければ、次の要素に進み、比較を繰り返す。
4. リストの最後まで比較しても一致する要素が見つからなければ、探索は失敗となる。

例えば、以下のような7つの要素を持つリストを考えてみましょう。

`[10, 7, 12, 6, 1, 3, 9]`

このリストから、例えば`1`という要素を探す場合、線形探索は以下のように動作します。

1. 最初の要素である`10`を`1`と比較します。一致しないため、次の要素に進みます。
2. 次の要素`7`を`1`と比較します。一致しないため、次の要素に進みます。
3. 同様に、`12`、`6`を比較し、一致しないため、次の要素に進みます。
4. `1`と比較し、一致したため、探索を終了します。

もしこのリストから`3`という要素を探す場合、`10`,`7`,`12`,`6`,`1`を比較した後に`3`と比較して見つけることができます。この場合、リストの全ての要素と比較する必要がありました。

線形探索の計算量

線形探索の効率を評価する上で重要なのが、時間計算量と空間計算量です。

時間計算量: n個のデータからm個のデータを検索する場合、時間計算量はO(nm)と表現されます。これは、最悪の場合、全てのデータを比較する必要があるため、データ数に比例して計算時間が長くなることを示しています。特にリストの要素数が増えるほど、検索にかかる時間も比例して増加します。
空間計算量: 線形探索は、データの格納に必要なスペース以外に、追加のメモリをほとんど必要としないため、空間計算量はO(1)となります。つまり、データ数が増えても、使用するメモリ量はほぼ一定です。

プログラム例

線形探索は、多くのプログラミング言語で簡単に実装できます。以下に、いくつかの言語での実装例を示します。

common lisp
(defun linear-search (target list)
(loop for i from 0 below (length list)
when (= (elt list i) target)
do (return i)
finally (return nil)))

fsharp
let linearSearch target list =
let rec search index =
if index >= List.length list then None
elif List.nth list index = target then Some index
else search (index+1)
search 0

c

include

int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Found
}
}
return -1; // Not found
}

haskell
linearSearch :: Eq a => a -> [a] -> Maybe Int
linearSearch target list =
let search index xs = case xs of
[] -> Nothing
(x:rest) -> if x == target then Just index else search (index+1) rest
in search 0 list

線形探索の活用と注意点

線形探索は、そのシンプルさから、小規模なデータセットや、データの並び順が予測できない場合に適しています。しかし、データ量が増加するにつれて効率が低下するため、大規模なデータセットに対しては、より効率的な二分探索などのアルゴリズムを選択する必要があります。また、事前にデータをソートしておくことで、二分探索など効率的な検索アルゴリズムが利用できる場合もあります。

関連事項

grep: ファイル内のテキストを検索するコマンドラインツール。内部では線形探索が用いられることがあります。
二分探索: ソート済みのデータに対して効率的な検索を可能にするアルゴリズム。線形探索よりも高速に検索できます。
* 情報検索: 大量の情報の中から特定の情報を見つけ出すための技術全般。線形探索はその基礎となるアルゴリズムの一つです。

もう一度検索