線型探索

線型探索（せんけいたんさく、）は、検索のアルゴリズムの一つ。
リストや配列に入ったデータに対する検索を行うにあたって、
先頭から順に比較を行い、それが見つかれば終了する。
formula_1個のデータからformula_2個のデータを検索する場合、時間計算量は formula_3 、空間計算量は formula_4 である。
アルゴリズムの流れ.
下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。
線形探索では、
最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。
プログラム例.
Common Lisp.
 (dolist (e list)
 (when (equal e x)
 (return-from linear-search T))) ;found
 NIL) ;not found
F#.
// For basic sequence:
let find value (vs: seq<_>) =
 use e = vs.GetEnumerator()
 let rec ifind index =
 if e.MoveNext() then
 if e.Current = value then Some index else ifind (index + 1)
 else None
 ifind 0
// For list:
let find2 value vl =
 let rec ifind2 index vl =
 if List.isEmpty vl then None
 else if (List.head vl) = value then Some index
 else ifind2 (index + 1) (List.tail vl)
 ifind2 0 vl
C.
/* for integer array: */
int
find(
 int array[],
 int array_size,
 int value)
 int i;
 for (i = 0; i < array_size; ++i)
 return -1;