比較
一致
未確認

  • 目標値
  • 比較中
  • 除外
  • 発見

線形探索の詳細

線形探索

線形探索は値を見つける最も簡単な方法です。先頭から始めて、見つかるまで値を順に1つずつ調べます。整列済みかどうかに関係なく、どんなリストにも使えます。探す値を選び、探索を再生するか比較を1回ずつ進めて、コストが値の位置や、値があるかどうかでどう変わるかを見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。破線は探す値を示します。探す値、棒の数、初期の並びを選ぶか、数値を自分で入力できます。「最初の一致で停止」をオフにすると、一致をすべて見つけます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 探す値、棒の数、初期の並びを選びます。数値を自分で入力することもできます。
  2. 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、探索の好きな位置に移動できます。
  3. 「最初の一致で停止」をオフにすると、すべての値を調べて一致をすべて見つけます。

線形探索の仕組み

最初の値を目標値と比べます。等しければ終わりです。そうでなければ2番目の値、3番目の値と順に進みます。一致がないままリストの最後に達したら、目標値はリストにありません。準備は何も要らず、リストを整列しておく必要もありません。

比較回数

k番目の値はk回の比較で見つかります。最良の場合は目標値が先頭にあるときで、比較は1回です。最悪の場合は目標値が最後にあるかリストにないときでn回です。すべての値を調べて初めて、ないと確信できるからです。リストにある値なら、平均で約(n + 1)/2回です。整列済みのリストなら二分探索の方がずっと優れていて、比較は約log₂ n回、40個の値なら最大40回ではなく6回で済みます。

よくある質問

線形探索はどのように動きますか?

リストの値を最初から最後まで1つずつ調べ、目標値が見つかるか値がなくなるまで続けます。逐次探索とも呼ばれます。

線形探索の時間計算量は?

O(n)です。最悪の場合、つまり目標値が最後にあるかリストにないとき、目標値をn個すべての値と比較します。リストにある目標値なら、平均で約(n + 1)/2回の比較です。

線形探索が向いているのはどんなときですか?

短いリスト、整列されておらず1〜2回しか探さないリスト、そしてストリームのように順番にしか読めないデータです。先に整列して二分探索を使うのは、何度も探す場合にだけ割に合います。

リストにない値が一番コストがかかるのはなぜですか?

線形探索には途中で止める手がかりがないからです。一致がないと言い切るにはすべての値を調べるしかないので、リストにない値は常にn回の比較がかかります。

入力した数値はどこかに送信されますか?

いいえ。探索はブラウザ内で動き、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ