BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
線形探索
一つずつ確かめる探索
線形探索は、配列やリストの要素を順に調べ、目的の値と一致するものを探す方法です。逐次探索とも呼びます。データが整列されていなくても利用でき、実装が単純です。目的の要素が見つかったら終了する方法も、全ての一致を集める方法もあります。何を返すかに応じて終了条件を定めます。
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件ゼロトラスト
所在地だけで信頼を決めない ゼロトラストは、社内ネットワークにいるという理由だけで暗黙に信頼せず、資源へのアクセスをその都度の条件に基づいて判断する考...
成長マトリクス
アンゾフの成長マトリクスとして知られ、商品・サービスの成長の種類を大きく4つの分類に分けたものを指す。 既存製品・既存市場:市場浸透 既存製品・新規市場...
生産者危険
商品を製造する際、商品に異常がないか調べるためにロット毎に検査をすることが多くあります。 その際、ロットすべて検査するわけにいかないので、一部取り出し...
線形探索
一つずつ確かめる探索 線形探索は、配列やリストの要素を順に調べ、目的の値と一致するものを探す方法です。逐次探索とも呼びます。データが整列されていなくて...
製品ライフサイクル
一つの製品が、開発され市場に投入された時から、販売を終了するまでの流れを現したもの。分析対象となる商品・サービスが現状どこに位置づけされるかを見極め、...
選択ソート
残りの最小値を選ぶ 選択ソートは、未整列の部分から最小値などを選び、順に確定位置へ移す整列方法です。昇順なら、最初に全体の最小値を先頭へ、次に残りの最...