線形探索で位置を返す
線形探索で位置を返す
このレッスンで分かること
- 探索は「見つけたら即終了」が鉄則です
- 配列の長さを
nとすると、最悪計算量はO(n)、最良計算量はO(1)です線形探索は配列の先頭から末尾までを順番に見ていき、目的の値が見つかった瞬間にそのindexを返すアルゴリズムです
線形探索で位置を返す とは
配列を先頭から走査し、目的の値が最初に現れた位置 (index) を返す線形探索を実装します。本レッスンでは、線形探索で位置を返す の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
線形探索 は配列の先頭から末尾までを順番に見ていき、目的の値が見つかった瞬間にその index を返すアルゴリズムです。コードがとても短く、ソート されていない配列でもそのまま使えるのが強みです。
探索アルゴリズムの中で最もシンプルかつ汎用性が高いのが線形探索です。
配列の長さを n とすると、最悪計算量は O(n)、最良計算量は O(1) です。平均的には半分くらい走査することが多いので O(n/2) のオーダーになります。定数倍 を無視するとオーダーはやはり O(n) です。
コードイメージ
Python
def linearSearchIndex(arr, target):
for i, v in enumerate(arr):
if v == target:
return i
return -1JavaScript
function linearSearchIndex(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}見つからない場合の 戻り値 をどう設計するかが大事です。本レッスンでは -1 で表すルールにします。null や例外を使う流派もありますが、競技プログラミングや LeetCode 系の慣習では -1 が一般的です。-1 を返す API のことを センチネル値 パターンと呼びます。
二分探索との違い
後半の章で扱う 二分探索 は O(log n) ですが、配列が 昇順 に並んでいる必要があります。一方、線形探索は ソート の前提が要らないので、未整列のデータや要素数が少ない場合 (n < 30 程度) にはむしろ線形の方が速いこともあります。キャッシュ ヒット率も 連続アクセス で良くなるため、現代の CPU では小規模配列で特に有利です。
比較表
| 観点 | 線形探索 | 二分探索 |
|---|---|---|
| 計算量 | O(n) | O(log n) |
| 必要な前提 | なし | 配列が ソート 済み |
| 実装の容易さ | とても簡単 | やや難しい |
小さな n での速さ | 速い | オーバーヘッドあり |
| メモリアクセス | 連続的でキャッシュに優しい | ランダムアクセス気味 |
早期 return が重要
線形探索で最も注意すべきは「見つかった瞬間に処理を抜ける」ことです。break や return を入れ忘れると、すべての要素を走査し続けてしまい、O(n) のはずが体感ではもう少し遅くなります。平均 ケースで考えると、ランダムな位置にデータがある場合、早期 return ありなら平均 n/2 回、なしなら毎回 n 回の比較になります。
探索は「見つけたら即終了」が鉄則です。
また、重複 が含まれる配列で「最初に出現した位置」を求める場合と「最後に出現した位置」を求める場合では、ループの方向や条件が変わります。本問題では 最初 に出現した index を返します。最後の出現位置が欲しいなら、ループを後ろから回すか、while で進めながら更新する方法があります。
線形探索の応用
線形探索の基本骨格は次のように発展していきます。
Python
# 条件にマッチする最初の要素を探す (述語ベース)
def findIndex(arr, pred):
for i, v in enumerate(arr):
if pred(v):
return i
return -1predを関数として渡せば、汎用的なfindIndexになるJavaScriptのArray.prototype.findIndexは同じ考え方Pythonのnext((i for i, v in enumerate(arr) if v == t), -1)でも書ける
この抽象化を覚えておくと、特定の条件にマッチする要素の位置を取り出すコードがすっきり書けます。バリデーション 中の 最初のエラー を探す、配列 の中で 重複の最初の位置 を探すなど、現場でも頻繁に登場します。
よくある間違い
- 見つかった後も
forを回し続けてしまい、最終的に間違ったindexを返す ==のはずが=(代入) になっている (JavaScript/Javaの場合)- 戻り値の型を統一していない (たとえば
nullと-1が混ざる) indexではなく要素そのものを返してしまう- 比較対象が浮動小数の場合に
==で比較してしまう (イプシロンでの比較が必要なことがある)
やってみよう
配列 [3, 7, 1, 9, 4] から 9 を探すと、index = 3 が返ります。100 を探すと -1 です。空配列 [] の場合も必ず -1 を返してください。
例外を投げる設計ではなく、
-1センチネルで「ない」を表す API を作ります。
線形探索は単体で使うより、複数の処理 (フィルタ カウント 等) と組み合わせて使われることが多いです。Python の list.index()、JavaScript の Array.prototype.indexOf() も内部的にはほぼ線形探索で実装されています。シンプルですが応用範囲は広い、まさに アルゴリズムの入り口 といえる重要なテクニックです。
よくある質問
Q. 線形探索と二分探索はどう違う？
A. 線形探索は配列の先頭から順に O(n) で見ます。二分探索はソート済み配列を半分ずつに絞って O(log n) で見つけます。少数の検索なら線形でも問題ありませんが、検索が頻繁ならソート + 二分探索が圧倒的に高速です。
Q. 線形探索の利点は何ですか？
A. ソート不要・実装が単純・追加コスト無しで動く点です。要素数が数十程度なら二分探索より速いこともあります（定数倍の差）。データ構造の選択でメリットが小さい場合、無理に二分探索や hash を使う必要はありません。
Q. 見つからなかったときの返し方は？
A. 言語慣習に従い -1（インデックス）/ null / undefined / None / Optional.empty などを返します。例外を投げる設計も可能ですが、「見つからない」が想定内なら戻り値で表現する方が呼び出し側で扱いやすいです。
次のレッスン
次は 二分探索 (反復版) で、ソート済み配列を半分ずつ絞り込んで O(log n) で目的の値を探す手法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 線形探索 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 線形探索 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 見つかったら即座にその index を return する
- 見つからない場合は -1 を返す
- ソートを前提にしないこと (線形探索のまま実装する)
入出力例
test-cases.txt
linearSearchIndex([3,7,1,9,4], 9) → 3
linearSearchIndex([5,2,8], 5) → 0
linearSearchIndex([1,2,3,4], 4) → 3
linearSearchIndex([1,2,3], 99) → -1
linearSearchIndex([4,2,4,4], 4) → 0