Pythonの線形探索
線形探索は未ソートのデータでも利用できます。
線形探索とは？
線形探索は先頭から順に各要素を調べ、目的の値が見つかるか末尾に達するまで続けます。事前の並べ替えは不要です。
アルゴリズムの動作
- インデックス0から開始します。
- 現在の要素と目的の値を比較します。
- 一致したらインデックスを返し、一致しなければ次へ進みます。
- 最後まで一致しなければ-1を返します。
計算量： 平均・最悪ともに時間計算量はO(n)、追加の空間計算量はO(1)です。
Pythonの線形探索のビジュアライザー
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仕組み
各値を最大1回比較するため、時間O(n)、追加メモリO(1)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。