線形探索とは
線形探索（Linear Search / リニアサーチ）とは、データ群の中から目的のデータを探し出すための、最もシンプルで原始的な検索アルゴリズムです。配列やリストの端（先頭など）から順に、1つずつ目的の値と一致するかどうかを比較していきます。データが事前に並べ替えられていなくても探索できる利点がありますが、データ数が多くなると比較回数が増えて時間がかかる欠点もあります。
具体例
裏向きに並べられたトランプの山から「ハートのA」を見つけるために、左端から順に1枚ずつめくって、ハートのAが出るまで確認していく手法がこれにあたります。
# 線形探索のプログラム例
def linear_search(data_list, target):
for index, value in enumerate(data_list):
if value == target:
return index # 見つかった位置を返す
return -1 # 見つからなかったもう少し詳しく
線形探索（Linear Search / リニアサーチ）は、データ構造（配列や連結リストなど）の先頭から末尾に向かって、順番に目的の値と一致するデータを比較していく最も基本的な探索アルゴリズムです。この手法の最大の利点は、探索対象のデータが事前にソート（並べ替え）されている必要がない点、およびデータ構造がランダムアクセスをサポートしていない（連結リストのようにポインタで順に辿るしかない）場合でも適用できるという汎用性の高さにあります。実装も非常にシンプルで容易です。しかし、データの個数をN個としたとき、目的のデータが最悪の場合（末尾にある、または存在しない場合）にはN回の比較が必要となるため、最大ステップ数はNに比例します（時間計算量はO(N)）。データ数が10倍、100倍と増えれば探索にかかる時間も10倍、100倍と増えてしまうため、大規模なデータ群に対する探索処理には適していません。
試験でのポイント
試験では、線形探索の時間計算量（平均比較回数は (N+1)/2 回、最悪比較回数は N 回であり、オーダー記法では O(N) と表されること）がよく問われます。また、ループ内の終了条件判定を減らして探索を効率化するテクニックである「番兵法（Sentinel Method）」のアルゴリズムを読み解く問題が頻出です。番兵法とは、配列の末尾に探したいターゲット値（番兵）をあらかじめ挿入しておくことで、「配列の境界チェック」を省略し、ループ内の比較処理を高速化する手法です。
関連する用語
時間計算量（アルゴリズムの実行に必要な手数を表す指標）、番兵法（探索アルゴリズムにおいてデータ末尾にダミーデータを置いて判定を簡略化する技法）、二分探索（ソート済みデータに対して高速に検索を行うアルゴリズム）。