線形探索とは?
どんな問題を解決するか
データが並べ替えられていなかったり、1回しか探さなかったりすることがあります。短い名前の一覧、今日の注文、ログの最初のエラーなどです。こういうときに必要なのは、どんなデータにも必ず使える、いちばん単純な探し方です。
身近なたとえ
線形探索は、コートのポケットを順に探して鍵を見つけるようなものです。最初のポケット、次のポケットと1つずつ調べ、見つかったらすぐにやめます。最後のポケットまで調べても見つからなければ、鍵はどのポケットにもないということです。
ポケット探しからコードへ
for index, value in enumerate(values):🧥 ポケットを順に調べるif value == target:🔑 鍵はここにある?return index✅ 見つかった:探すのをやめるreturn -1❌ 全部調べた:見つからないひと言でいうと
線形探索は、コレクションの要素を先頭から順に調べて目的の値を探す方法です。最大で O(n) 回の手順がかかりますが、並べ替えは必要ありません。
線形探索は先頭から順に各要素を調べ、目的の値が見つかるか末尾に達するまで続けます。事前の並べ替えは不要です。
アルゴリズムの動作
- インデックス0から開始します。
- 現在の要素と目的の値を比較します。
- 一致したらインデックスを返し、一致しなければ次へ進みます。
- 最後まで一致しなければ-1を返します。
計算量: 平均・最悪ともに時間計算量はO(n)、追加の空間計算量はO(1)です。
どんな場面で使う?
- 並べ替えられていない、または小さなコレクション。
- 1回しか探さない場合。先に並べ替えるほうが、かえって手間がかかります。
- 完全一致だけでなく、条件に合う最初の要素を見つける。
使わなくてよいとき
- 同じ大きなデータを何度も探す場合:一度並べ替えて二分探索を使うか、set や辞書を作ります。
- 値があるかどうかだけを知りたい場合:
target in valuesなら少ないコードで同じことができます。
Pythonの線形探索(linear search)のビジュアライザー
O(n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))
実行結果
3
コードの解説
enumerate()関数は各要素の位置と値を返します。探す値が見つかった時点で関数はその位置を返し、ここでは3になります。最後まで調べても見つからなければ-1を返します。最悪の場合はすべての要素を調べるので、計算量はO(n)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
ループの中で -1 を返す
最初の要素が一致しなかっただけで、探索をやめてしまいます。
問題
for index, value in enumerate(values):
if value == target:
return index
return -1
修正
for index, value in enumerate(values):
if value == target:
return index
return -1
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ