線形探索のソースを表示

{{pathnav|探索|frame=1}}
'''線形探索'''（せんけいたんさく、{{lang-en-short|linear search, sequential search}}）は、[[検索]]の[[アルゴリズム]]の一つ。[[リスト (抽象データ型)|リスト]]や[[配列]]に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。

<math>n</math>個のデータから<math>m</math>個のデータを検索する場合、時間計算量は <math>O(nm)</math> 、空間計算量は <math>O(1)</math> である。

==アルゴリズムの流れ==
下のような7個のデータを持つリストがある。
{|class=wikitable
|style="min-width:1.5em;text-align:center"|10
|style="min-width:1.5em;text-align:center"|7
|style="min-width:1.5em;text-align:center"|12
|style="min-width:1.5em;text-align:center"|6
|style="min-width:1.5em;text-align:center"|1
|style="min-width:1.5em;text-align:center"|4
|style="min-width:1.5em;text-align:center"|3
|}
線形探索では、
*最初の要素である10を見る。
*10は1ではないので、次の要素7を見る。
*7は1ではないので、次の要素12を見る。
*12は1ではないので、次の要素6を見る。
*6は1ではないので、次の要素1を見る。1を見つけることができた。
なお、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。

==プログラム例==
===Common Lisp===
<syntaxhighlight lang="lisp">
(defun linear-search (list x)
  (dolist (e list)
    (when (equal e x)
      (return-from linear-search T))) ;found
  NIL) ;not found
</syntaxhighlight>

===F#===
<syntaxhighlight lang="fsharp">
// 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
</syntaxhighlight>

===C===
<syntaxhighlight lang="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;
}
</syntaxhighlight>

===Haskell===
<syntaxhighlight lang="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
</syntaxhighlight>

==関連項目==
* [[grep]]
* [[二分探索]]
* [[情報検索]]

{{アルゴリズム}}
{{デフォルトソート:せんけいたんさく}}
[[Category:検索アルゴリズム]]