線形探索シミュレーター

ALGORITHM

線形探索とは何をしているか

線形探索は、配列の先頭（添字 0）から末尾まで順番に進みながら、それぞれの要素を探したい値 target と比べていくアルゴリズムです。 「逐次探索」「順次探索」とも呼ばれます。やっていることは、机の上に並んだカードを左から1枚ずつめくって目的のカードを探す作業とまったく同じです。

処理に必要な部品は3つだけです。どこを見ているかを表す添字 i、見つかった位置を覚えておく変数 pos、そして要素と target を比べる条件式です。 上のシミュレーターで「次へ」を押していくと、この3つがどう変化していくかを1ステップずつ確認できます。

考え方は単純ですが、共通テスト「情報Ⅰ」では 添字 i の進み方・見つからなかったときの値・同じ値が複数あるときの扱い・比較回数が繰り返し問われます。 つまり「なんとなく分かる」では足りず、1行ずつ値を追える状態にしておく必要があります。

なぜ pos の初期値は -1 なのか

配列の添字は 0 から始まります。そのため pos = 0 を初期値にしてしまうと、「先頭の要素が見つかった」場合と「まだ何も見つかっていない」場合を区別できなくなります。 添字としては絶対にあり得ない値である -1 を初期値にしておけば、最後まで pos が -1 のままなら「配列の中に target は存在しなかった」と判断できます。 シミュレーターの「見つからない」プリセットを試すと、最後まで -1 が残る様子が確認できます。

整列されていなくても使える

線形探索の大きな特徴は、配列が小さい順に並んでいなくても正しく動くことです。先頭から全部見ていくのだから、並び方は結果に影響しません。 「整列済みでなければ使えない」という制約があるのは二分探索のほうです。この2つはセットで問われやすいので、前提条件の違いをはっきり区別しておきましょう。

同じ値が複数あるときの扱い

配列に target と同じ値が2つ以上あるとき、「どの位置を答えとするか」は条件の書き方で決まります。シミュレーターの「条件の書き方」を切り替えると、この違いをそのまま比較できます。

CODE

3つの書き方で見る線形探索

同じアルゴリズムを、共通テストの擬似言語（DNCL風）・Python・JavaScript で並べました。 変数名と処理の順番はすべて揃えてあるので、言語が変わってもやっていることは同じだと確認できます。

Nums = [4, 9, 2, 9, 6]
target = 9
pos = -1

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし Nums[i] == target かつ pos == -1 ならば:
⎿⎿ pos = i

表示する(pos)

nums = [4, 9, 2, 9, 6]
target = 9
pos = -1

for i in range(len(nums)):
    if nums[i] == target and pos == -1:
        pos = i

print(pos)

const nums = [4, 9, 2, 9, 6];
const target = 9;
let pos = -1;

for (let i = 0; i < nums.length; i++) {
  if (nums[i] === target && pos === -1) {
    pos = i;
  }
}

console.log(pos);

COST

比較回数と計算量

線形探索の手間は「何回比較したか」で測ります。要素数を n として整理すると次のようになります。 シミュレーターで「先頭にある（最良）」と「末尾にある（最悪）」を切り替え、変数「比較回数」の最終値を見比べてみてください。

要素数を変えて確かめる：シミュレーターの「要素数を選ぶ」で 4個 → 10個 と増やしながら「末尾にある（最悪）」を試すと、 最終的な比較回数が 4回 → 10回 と、要素数とぴったり同じだけ増えていくことが確認できます。 「見つからない」を選んだ場合も同じで、要素数と等しい回数になります。この2つが最悪の場合です。

要素数が2倍になれば、かかる手間もおよそ2倍になります。これが O(n)（要素数に比例する）という意味です。 1000個の配列なら最悪1000回、100万個なら最悪100万回の比較が必要です。 一方、整列済みの配列に対して使える二分探索は、1回の比較で候補を半分に減らせるため、100万個でも約20回で済みます。 この差が「整列してから探す」意味につながります。

EXAM POINT

共通テスト「情報Ⅰ」での出題ポイント

線形探索そのものを一から書かせる問題より、穴埋めやトレース（値の追跡）として出るほうが多いです。狙われやすいのは次の5点です。

1. 繰り返しの終了値：「0 から 要素数 - 1 まで」の - 1 が空欄になる形。0 から数え始めるので、最後の添字は n ではなく n-1 です。
2. 見つからなかったときの値：pos = -1 の初期化や、「-1 のとき何を表示するか」を問う形。
3. 条件式の空欄：Nums[i] == target の比較演算子や、かつ pos == -1 の部分。ここが変わると答えが「最初の位置」か「最後の位置」かで変わります。
4. 比較回数を数える：変数 count を増やす行を追加した形。繰り返しを抜ける処理があるかどうかで答えが変わります。
5. 添字が1始まりの問題文：「1番目の商品」のように日常の言い方と添字がずれる形。問題文の「〇番目」と配列の添字 i の対応を必ず確認します。

MISTAKES

よくある間違い

CHECK

理解度チェック

まず自分で考え、答えを開く前に上のシミュレーターで確かめてみてください。