線形探索
整列されていない名簿から名前を探すとき、あなたがしているのが線形探索です。一番上から下へ読んでいき、見つかったら終わり。最も簡単な探索で、どんなリストにも使え、短いリストならたいていこれで十分です。
考え方
目標値をリストの最初の値と比べます。等しければ止まります。目標値は1番目にあります。そうでなければ2番目の値、3番目の値と比べていきます。最後の値も一致しなければ、目標値はリストにありません。リストについて前もって知っておくことは何もありません。整列されている必要はなく、値は等しいかどうか比べられるものなら何でも構いません。
例
5, 1, 4, 2, 8 から 4 を探します。5は4と等しい?いいえ。1は?いいえ。4は?はい。比較3回で3番目に見つかりました。次に同じリストから7を探します。5つの値をすべて調べても一致しないので、比較5回の結果、7はないとわかります。
比較回数
k番目の値を見つけるにはk回の比較が必要です。目標値がどの位置にも同じ確率であるなら、平均は(n + 1)/2回で、40個の値なら20.5回です。リストにない値は常にn回かかります。最後の比較が終わって初めて、一致する値がないと確定するからです。つまりコストはリストの長さに比例して増え、これをO(n)と書きます。
速い探索には順序が必要
線形探索は何も飛ばせません。整列されていないリストでは、どの値がどこにあってもおかしくないからです。リストが整列されていれば、比較から等しいかどうか以上のこと、つまり目標値がどちら側にあるかがわかります。二分探索はこれを使って毎回リストを半分にし、比較は約log₂ n回、40個の値なら最大6回です。ただし整列にも時間がかかるので、1回しか探さないリストなら線形探索の方がよいことも多いです。
ちょっとした改良
番兵を使う方法では、探索の前に目標値をリストの末尾に置きます。こうするとループでは一致だけを調べればよく、リストの終わりかどうかを調べる必要がなくなります。値が見つかるたびに1つ前、または先頭に移すと、よく探す値ほど次第に早く見つかるようになります。どちらも、最悪の場合のn回の比較は変わりません。
試してみよう
アプリを開き、「探す値」で値を選んで「ステップ」を押します。破線は目標値の高さを示し、各値は調べるときに強調され、除外されると薄くなり、一致すると緑になります。リストにない値を探すと、全体を1回調べる様子が見られます。また「最初の一致で停止」をオフにして重複の多い値を使うと、一致を複数見つけられます。
よくある質問
線形探索の時間計算量は?
最悪の場合と平均ではO(n)、最良の場合、つまり目標値が最初の値のときはO(1)です。追加のメモリは要りません。
線形探索と二分探索の違いは?
線形探索はすべての値を順に調べ、どんなリストにも使えます。二分探索は整列済みのリストにしか使えませんが、目標値がありうる範囲を毎回半分にするので、最大n回ではなく約log₂ n回の比較で済みます。
線形探索には整列済みのリストが必要ですか?
いいえ。それが一番の利点です。整列済みのリストなら、目標値があるはずの位置を過ぎた時点で止められますが、それでも二分探索より遅くなります。
線形探索はどこで使われていますか?
リストが短いか整列されていないところならどこでもです。小さな配列から要素を探す、順番にしか読めないファイルやストリームを走査する、すべての要素が条件を満たすか調べる、などです。JavaScript の indexOf や Python の list.index など、多くのライブラリ関数は線形探索です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
線形探索を試す