女性向けエンジニアスクール
3秒でわかる
先頭から順に1件ずつ照合して目的の要素を探す方法。並び替えも準備も要らないため、少ない件数や整列できないデータでは今でも最適な選択になります。
もう少し詳しく
どういうものか
線形探索は、データの先頭から末尾に向かって 1 つずつ値を比べ、目的のものが見つかったらそこで止める探索方法です。逐次探索とも呼びます。
最良の場合は 1 回の比較で終わり、最悪の場合は全件を比べます。要素数を n とすると、平均でおよそ n/2 回、最悪で n 回の比較となり、計算量は O(n) です。
なぜ必要か
二分探索のほうが速いと知っていても、線形探索が残るのには理由があります。二分探索はデータが整列されていることを前提としますが、整列そのものに O(n log n) かかります。1 回だけ探すなら、並べ替えてから二分探索するより、そのまま線形に探すほうが速く済みます。
さらに、連結リストのように途中へ直接飛べない構造では二分探索が使えません。「値が範囲に入っているか」「条件を満たす最初の要素」といった、大小関係で絞れない条件も線形探索の領分です。
具体例
def linear_search(items, target):
for i, value in enumerate(items):
if value == target:
return i # 見つかった位置
return -1 # 最後まで無かった
data = [42, 7, 19, 3, 88]
print(linear_search(data, 19)) # 2
print(linear_search(data, 5)) # -1
# 条件で探す場合も線形探索
first_over = next((v for v in data if v > 50), <a href="/glossary/none" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">None</a>)
print(first_over) # 88探索対象 [42, 7, 19, 3, 88] から 19 を探す
42 と比較 -> 違う
7 と比較 -> 違う
19 と比較 -> 一致。位置 2 を返して終了つまずきやすいところ
-1 か None を使いますO(1) で引くほうが効きます似た用語との違い
| 手法 | 前提 | 計算量 |
|---|---|---|
| 線形探索 | 何も要らない | O(n) |
| 二分探索 | 整列済みで添字アクセスできる | O(log n) |
| ハッシュ探索 | ハッシュ表を構築済み | 平均 O(1) |
覚え方
本棚の端から 1 冊ずつ背表紙を見ていく探し方です。整理されていない棚では、これが一番確実で速い方法になります。
