線形探索（linear search）

• テクノロジ系
• アルゴリズムとプログラミング
• 基本情報
• 応用情報
• 重要度 ★★★☆☆

もう少し詳しい説明

線形探索は、データを端から1件ずつ順に見ていく探し方です。順次探索とも呼びます。

やり方は単純で、先頭から順に「これか？」と確かめ、当たったら終わり。最後まで当たらなければ「無い」と分かります。

弱点と、強み

比較回数は、運に左右されます。

件数に比例して増えるので、計算量は O(n) です。100万件なら最大100万回で、速いとは言えません。

なお、この「最大」のことを、試験の問題文や参考書では最悪の場合と書きます。いちばん運が悪かったときの回数、という意味です。

それでも線形探索には、ほかの方法にはない強みがあります。

• 並んでいなくても使える。 二分探索は「整列済み」が前提ですが、線形探索はどんな並びでも動きます
• 手順が単純。 書き間違えにくく、データが少ないときはかえって速いこともあります

二分探索は速いかわりに、先に並べ替えておく手間がかかります。1回しか探さないなら、並べ替える時間で線形探索が終わってしまうこともあります。

二分探索との使い分け

「整列済みの」という言葉が問題文にあるかどうかが、最初の手がかりになります。

番兵法：判定を1つ減らす工夫

基本情報の科目B（旧・午後）でも出てくる工夫です。

ふつうに線形探索を書くと、1件ごとに2つの判定をしています。

1. まだ範囲の中か（終わりに来ていないか）
2. 探している値と一致するか

ここで、データの最後の次の位置に、探している値そのものを置いておきます（配列は n ＋ 1 個ぶん用意します）。こうすると必ずどこかで一致するので、「範囲の中か」の判定が要らなくなります。止まった位置がその余分な場所なら、「元のデータには無かった」と判断できます。

この、置いておく値を番兵（sentinel）と呼びます。

効果は判定の数に出ます。探している値との比較そのものは減らず、見つからなかった場合はむしろ番兵との1回が増えます。減るのは範囲の判定のほうで、1件あたり2つだった判定が1つになるため、全体の判定回数がおよそ半分になります。

覚え方：端から順に、それだけ

線形探索は、やり方が名前のとおりです。線のように、端から順にたどるだけ。

押さえるのは3つの数字です。最小1回、平均 n/2 回、最大 n 回。 そして計算量は O(n)。この並びを覚えておけば、計算問題はそのまま解けます。

試験ではこう出る

科目A（旧・午前）のアルゴリズム分野で出ます。多いのは、平均の比較回数や、最大の比較回数を答えさせる問題と、二分探索と並べて計算量を選ばせる問題です。応用情報では、番兵法の効果を問う形や、探索方法をどう選ぶかを判断させる形になります。

平均回数の問題は、(n ＋ 1) ÷ 2 が正確な値で、選択肢では n / 2 と書かれることが多くなります。どちらも同じ考え方なので、迷ったら「先頭から最後までの平均だから真ん中あたり」と考えてください。最大は n 回で、これは「無かったとき」も同じ回数になります。

関連する用語

二分探索

並んでいるデータの真ん中と比べ、範囲を半分ずつ捨てる探し方。速いが並び順が前提

計算量

件数が増えたときの処理時間の伸び方。線形探索は O(n)

整列（ソート）

データを順番に並べ替えること。並べてから探すかどうかが、方法の分かれ目になる

番兵法

データの末尾に探す値を置いて、範囲外かどうかの判定を1つ減らす工夫

ハッシュ表

値から置き場所を直接計算する方法。うまくいけば1回で見つかる

ミニクイズ

最終更新：2026-09-23