読み方 ： せんけいたんさく

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

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

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

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

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

(2020.2.1更新)

他の用語辞典による「線形探索」の解説 （外部サイト）

資格試験などの「線形探索」の出題履歴

▼ ITパスポート試験
【令5 問69】 配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述のうち、適切なものはどれか。

▼ 基本情報技術者試験
【令5修1 問9】 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。
【令4修12 問9】 配列Aの1番目からN番目の要素に整数が格納されている（N>1）。次の図は，Xと同じ値が何番目の要素に格納されているかを調べる流れ図である。
【令3修12 問5】 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。
【令3修7 問9】 探索表の構成法を例とともに a〜c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
【平29修7 問4】 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。
【平28修1 問4】 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。
【平25修6 問7】 配列Aの1番目からN番目の要素に整数が格納されている（N>1）。次の図は，Xと同じ値が何番目の要素に格納されているかを調べる流れ図である。
【平24秋 問3】 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。