1 歩ずつ動かす
配列 [3, 8, 12, 17, 23, 31, 42, 56] から 42 を探す
- 30
- 81
- 122
- 173
- 234
- 315
- 426
- 567
- 比較中
- 発見
- 違う
- 箱の下の数字は添字
1 歩目 / 全 9 歩比べた回数 0 回
探す値は 42 です。左端の添字 0 から順に見ていきます。
いま動いている疑似コードの行
- 1i を 0 から n - 1 まで 1 つずつ増やす
- 2もし a[i] == x なら
- 3i を返す (見つかった)
- 4-1 を返す (見つからない)
見本を変える
予想してみる
いまは 1 歩目です。
次に比べるのは、どの添字でしょう。
今回わかること
- 配列を左端から 1 つずつ比べて探す流れ
- 比べる回数が、配列の長さに比例して増える理由
前提
- 配列と添字 (0 から数える番号)
- for 文で 1 つずつ取り出す書き方
どんな探し方か
線形探索は、配列の左端から順に値を比べ、目当ての値と同じものが出たら止まる探し方です。
並び順を問わず使えます。そのかわり、運が悪いと最後まで全部を比べます。
手順と具体例
- 1添字 0 の値と、探す値を比べる
- 2同じなら、その添字を答えにして終わる
- 3違えば、右隣へ 1 つ進んで同じことをする
- 4右端まで比べても無ければ「見つからない」で終わる
| 回 | 比べた場所 | 結果 |
|---|---|---|
| 1 | 添字 0 の 3 | 違う。右へ進む |
| 2 | 添字 1 の 8 | 違う。右へ進む |
| 3 | 添字 2 の 12 | 違う。右へ進む |
| 4 | 添字 3 の 17 | 違う。右へ進む |
| 5 | 添字 4 の 23 | 違う。右へ進む |
| 6 | 添字 5 の 31 | 違う。右へ進む |
| 7 | 添字 6 の 42 | 同じ。見つかった |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | 1 回 (左端にある) | O(1) |
| 平均 | およそ n ÷ 2 回 | O(n) |
| いちばん遅い | n 回 (右端か、無いとき) | O(n) |
n は配列の長さです。8 個なら最悪 8 回、100 万個なら最悪 100 万回比べます。
| 探す値 | 線形探索 | 二分探索 |
|---|---|---|
| 42 | 7 回 | 3 回 |
| 20 | 8 回 | 3 回 |
| 3 | 1 回 | 3 回 |
| 56 | 8 回 | 4 回 |
使いどころ
向いているとき
- 配列が並んでいないとき
- 要素が数十個までの、小さい配列のとき
- 1 回だけ探すので、並べ替える手間のほうが大きいとき
向いていないとき
- 何度も探す大きい配列 (二分探索を使う)
- 値で直接引きたいとき (辞書やハッシュ表を使う)
コード
疑似コード
- 1i を 0 から n - 1 まで 1 つずつ増やす
- 2もし a[i] == x なら
- 3i を返す (見つかった)
- 4-1 を返す (見つからない)
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- Python の in や index と何が違いますか？
- x in a も a.index(x) も、中では左から順に比べています。線形探索を自分で書くと、その手間が見えるようになります。
- 同じ値が 2 つあるときは、どちらが返りますか？
- 左から比べるので、先に出てくる左側の添字が返ります。
- 見つからないとき、なぜ -1 を返すのですか？
- 添字は 0 以上なので、ありえない値の -1 を「無い」の印に使います。言語によっては None や null を返す書き方もあります。
