線形探索

線型探索（せんけいたんさく）は、検索のアルゴリズムの一つ。

リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

$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)$の計算時間を要することとなる。

Pythonによるプログラム例

def search(list, x):
    found = 0
    for item in list:
        if item == x:
            found = 1
            break
    return found

Common Lispによるプログラム例

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