線型探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
個のデータから個のデータを検索する場合、時間計算量は 、空間計算量は である。
アルゴリズムの流れ
下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。
| 10 | 7 | 12 | 6 | 1 | 4 | 3 |
線形探索では、
- 最初の要素である10を見る。
- 10は1ではないので、次の要素7を見る。
- 7は1ではないので、次の要素12を見る。
- 12は1ではないので、次の要素6を見る。
- 6は1ではないので、次の要素1を見る。1を見つけることができた。
最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。
プログラム例
Common Lisp
(defun linear-search (list x) (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) { if (array[i] == value) { return i; } } return -1; }