線形探索

線形探索は配列の先頭から要素を一つずつ調べ、目標と一致した時点で添字を返します。入力の整列は不要です。最悪の場合は n 要素すべてを調べるため、時間計算量は O(n) です。

順序のない名簿で名前を探すなら、先頭から読む必要があります。位置から値を推測できず、中央を調べても半分を除外できません。線形探索は入力の構造を前提にしない代わりに、最悪の場合は全要素を読みます。

線形探索の仕組み

カーソル i を 0 から n − 1 まで進め、nums[i] と目標を比べます。一致すれば i を返して終了します。一致しなければ、その位置を除外して右へ進みます。

末尾まで一致しなければ −1 を返します。早期リターンにより、最初の一致より後ろは読みません。また、返すのは最初に出現する位置です。

入力は昇順、降順、順不同のいずれでも検索できます。並べ替えると目標の位置や比較回数は変わりますが、正しく見つけられることは変わりません。

線形探索のステップ

初期入力は nums = [42, 17, 8, 91, 23, 4, 56, 30]、目標は target = 23 です。

1. i = 0：nums[0] = 42 は 23 と異なるので進みます。
2. i = 1：nums[1] = 17 は一致しないので進みます。
3. i = 2：nums[2] = 8 は一致しないので進みます。
4. i = 3：nums[3] = 91 は一致しないので進みます。
5. i = 4：nums[4] = 23 と一致し、添字 4 を返します。

比較は五回です。後ろの 4, 56, 30 は、一致した時点で処理を終えるため調べません。

アニメーションでは i が一セルずつ右へ進みます。比較中のセルは琥珀色、除外済みのセルは薄く表示されます。一致したセルは緑になり、その右側は未訪問の表示を保ちます。薄いセルの範囲が、今回調べた範囲です。

時間・空間計算量

最初の一致が添字 k なら比較は k + 1 回、一致がなければ n 回です。プレイヤーの比較回数もこの規則で増えます。追加領域は O(1) で、添字以外のデータ構造は作りません。

線形探索を使う場面

未整列データへの一度の問い合わせ、小さい集合、順にしか読めない構造に適しています。連結リストには配列のようなランダムアクセスがないため、配列の二分探索と同じ O(log n) の検索時間は得られません。

同じ集合を何度も検索するなら、O(n) の構築後に平均 O(1) で存在確認できるハッシュ集合を検討します。整列済み配列なら二分探索は O(log n) です。問い合わせ一回の時間だけでなく、前処理の費用も含めて選びます。

境界条件

• 空配列：ループを実行せず、比較なしで −1 を返します。コードはこの入力を扱えますが、プレイヤーは五要素以上を要求します。
• 先頭で一致：一回の比較で返す O(1) の最良の場合です。
• 末尾で一致・存在しない：どちらも n 回比較します。違いは最後に一致するかどうかです。
• 目標の重複：最初の出現位置を返し、それ以降の同値は調べません。

よくある間違い

• 一致しても返さない：位置の記録だけを更新して走査を続けると、最後の一致を返す場合があります。また、先頭で見つかっても n 回の比較が必要になります。
• 整列が必要だと思う：線形探索には不要です。一度の検索のための整列は仕事を増やします。データが整列済みなら、二分探索を選べます。
• 同じ集合を何度も走査する：問い合わせが増えると O(n) の費用が積み重なります。ハッシュ集合や、整列後の二分探索を検討します。
• 未発見の戻り値を省く：末尾まで読んでも目標がない場合があります。−1、None、オプション型などで、添字 0 との区別を付けます。