線形探索 【linear search】 リニアサーチ / 逐次探索 / 線型探索 / 単純前方探索

概要

線形探索（linear search）とは、データ探索アルゴリズムの一つで、配列などに格納されたデータ列の先頭から末尾まで順番に、探しているデータと一致するか比較していく手法。

最も単純なアルゴリズムで、配列などに格納されたデータ列の中から、まず先頭の要素を探しているデータと比較する。一致しなければ2番目の要素と比較する。これを末尾の要素まで繰り返し、途中でデータを発見したらそこで探索を終了する。

N個のデータ列の中から線形探索する場合、最良のケースは先頭の要素と一致する場合で比較回数は1回、最悪のケースは末尾まで探してもデータが見つからなかった場合で比較はN回、平均の比較回数はN/2回となる。比較回数の平均値は要素数に正比例して増大する。

仕組みが単純なため短いプログラムコードで記述でき、コードを読んだ人が処理を理解しやすく、探索対象のデータ列以外に余分な記憶領域を消費せず、事前にデータ列のソート（大きい/小さい順に並べ直す処理）などの前処理を行う必要がないという利点がある。より高度なアルゴリズムに比べると平均の比較回数は多く、性能の高いアルゴリズムとは言えない。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。