線型探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

プログラム例[編集]

Perl[編集]

grep /REGEXP/, @list;

Python[編集]

def search(list, x):
    return x in list

Common Lisp[編集]

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

関連項目[編集]