線形探索

探索 > 線形探索

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

$n$個のデータから$m$個のデータを検索する場合、 時間計算量は$O(nm)$、空間計算量は$O(1)$必要となる。

アルゴリズムの流れ

下のような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個のデータ全てを見ないと、見つけることができない。 つまり、n個のデータから1個のデータを検索する場合に最悪$O(n)$の計算時間を要することとなる。

プログラム例

Common Lisp

(defun linear-search (list x)
  (labels ((spam (ls)
                 (and (consp ls)
                      (or (zerop (- (car ls) x))
                          (spam (cdr ls))))))
          (spam list)))

C#

public static int Find<T>(this IEnumerable<T> enumerable, T value)
{
    var index = 0;
    foreach (var v in enumerable)
    {
        if (v == value)
        {
            return index;
        }
        index++;
    }
    return -1;
}

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;
}

関連項目

• grep
• 二分探索
• 情報検索