過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

線形探索

一つずつ確かめる探索

線形探索は、配列やリストの要素を順に調べ、目的の値と一致するものを探す方法です。逐次探索とも呼びます。データが整列されていなくても利用でき、実装が単純です。目的の要素が見つかったら終了する方法も、全ての一致を集める方法もあります。何を返すかに応じて終了条件を定めます。

Pythonによる例

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

values = [18, 7, 25, 11, 7]
first_index = linear_search(values, 7)
missing_index = linear_search(values, 99)

この例では最初に見つかった位置を返します。7は二か所にありますが、返るのは最初の位置です。存在しない99については最後まで調べてから-1を返します。

比較回数

先頭で見つかれば一回、最後にある場合や存在しない場合は、最大で要素数分の比較が必要です。要素数をnとすると最悪時の時間計算量はO(n)です。見つかる位置が均等という前提なら平均の比較回数を計算できますが、よく使う値が先頭に偏るようなデータでは前提が異なります。

番兵の考え方

探索対象の末尾に目的の値を一時的に置く番兵法では、ループ内の境界確認を簡略化できる場合があります。ただし、見つかった位置が本来のデータか番兵かを最後に判断する必要があります。追加領域や元の値の復元なども考慮します。比較回数の増え方そのものが対数的になるわけではありません。

二分探索との使い分け

二分探索は整列が必要ですが、線形探索はその準備を省けます。小さなデータ、更新が多いデータ、一度しか探さない状況では、単純さが利点になることがあります。試験では、探索成功と失敗、最初の一致と全一致、整列の有無を分けて読みます。計算量の記号だけで常に劣る方法と決めつけず、前処理やアクセス方法を含む全体の費用を考えましょう。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

6件