線形探索

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

${\displaystyle n}$個のデータから${\displaystyle m}$個のデータを検索する場合、時間計算量は ${\displaystyle O(nm)}$ 、空間計算量は ${\displaystyle O(1)}$ である。。

アルゴリズムの流れ[編集]

下のような7個のデータを持つリストがある。

線形探索では、

• 最初の要素である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[10] = {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
• 二分探索
• 情報検索