線形探索（せんけいたんさく、）は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。
個のデータから個のデータを検索する場合、時間計算量は 、空間計算量は である。
アルゴリズムの流れ 下のような7個のデータを持つリストがある。 107126143 線形探索では、 最初の要素である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 #include <stdio.h>
// 整数配列に対する線形探索関数 int find(int array[], int array_size, int key) { for (int i = 0; i < array_size; i++) { if (array[i] == key) { return i; // found
return -1; // not found }
// 使用例 int main(void) { int list = {12, 67, 87, 90, 125, 153, 214, 234, 653, 804}; int result = find(list, sizeof list / sizeof *list, 90);
if (result < 0) { printf("Not found.\n"); } else { printf("result = %d\n", result);
//=> result = 3
return 0; }
Haskell -- 線形探索関数 linearSearch :: Eq a => a -> [a] -> Maybe Int linearSearch _ [] = Nothing linearSearch x (y:ys) | x == y = Just 0 | otherwise = fmap (+1) (linearSearch x ys)
-- 使用例 main = do print $ linearSearch 3 [1, 2, 3, 4, 5] -- Just 2 print $ linearSearch 6 [1, 2, 3, 4, 5] -- Nothing
関連項目 grep 二分探索 情報検索