線形探索 (O(n))
線形探索 (O(n))
このレッスンで分かること
- 計算量は
O(n)- 配列の中に「指定の値が含まれているか」「含まれているなら何番目か」を調べたいとき、最もシンプルなアプローチが 線形探索 (linear search) です
- 図のポイント (テキスト併記)
線形探索 (O(n)) とは
配列の先頭から順に target を探す線形探索を実装し、O(n) の挙動と最悪計算量を理解する。本レッスンでは、線形探索 (O(n)) の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列の中に「指定の値が含まれているか」「含まれているなら何番目か」を調べたいとき、最もシンプルなアプローチが 線形探索 (linear search) です。先頭から末尾まで 1 つずつ順番に見て、一致するものが見つかればその位置を返し、見つからなければ -1 を返します。
計算量は O(n) 。配列の長さ n に比例して時間がかかります。n が 100 でも 100 万でも、最悪の場合は全要素を見ることになる、というのがポイントです。
線形探索は「総当たり」の最たる例。シンプルで、ソートされていない配列でも使える万能戦法。
アルゴリズムの流れ
図のポイント (テキスト併記)
- 図のとおり、配列を先頭から末尾までスキャンし、見つかった瞬間にループを抜けて位置を返します
図のとおり、配列を先頭から末尾までスキャンし、見つかった瞬間にループを抜けて位置を返します。最後まで見つからなければ -1 を返します。
最悪 / 最良 / 平均
線形探索の計算量を整理すると、最良の場合は配列の先頭にあるケースで O(1) 、最悪の場合は末尾にあるか存在しないケースで O(n) 、平均的にはおよそ n/2 回の比較なので O(n) です。
O(n)の意味は「nに比例する」で、定数倍の違い (nかn/2か2nか) は無視する。これが Big-O の特徴。
Python での実装例
Python
def linearSearch(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1for i in range(len(arr)) で先頭から末尾までインデックスを順に取り、一致したら return i で即座にループを抜けます。
JavaScript での実装例
JavaScript
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}比較は === (厳密等価) を使うのが鉄則です。== を使うと "5" == 5 のような型変換が走るため、思わぬバグになります。
よくある間違い
1 つ目は 見つかった瞬間に return せず、ループを最後までまわしてしまう こと。これだと無駄に時間がかかり、複数回マッチした場合に「最後の出現位置」を返してしまいます。本問では「最初に見つけた位置」を返す仕様なので、見つけたら 即座に return します。
2 つ目は 見つからなかったときの -1 を返し忘れること。return None や return undefined ではなく、明示的に -1 を返すのが慣例です。
3 つ目は オフバイワン 。i <= len(arr) と書いてしまうと IndexError (Python) や undefined (JS) を踏みます。配列のインデックスは 0..len-1 までであることを忘れずに。
やってみよう
arr = [3, 1, 4, 1, 5, 9, 2, 6]でtarget = 5を探すと4(0-indexed) が返る。target = 7のように 存在しない値 で-1が返ることを確認する。- 配列が
n = 1000000件あるとき、末尾の値を探すと当然n回比較する。これがO(n)の最悪ケース。
線形探索は O(n) 。ソートされた配列なら次レッスンの 二分探索 O(log n) を使うのが定石。
Java と Go での実装
Java
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}Go
func linearSearch(arr []int, target int) int {
for i := 0; i < len(arr); i++ {
if arr[i] == target {
return i
}
}
return -1
}線形探索が活きる場面
計算量が O(n) と聞くと「遅い」印象を持ちますが、線形探索が向いている場面はたくさんあります。たとえば配列が 小さい とき (n が 10 以下程度) は、二分探索のために事前にソートする手間の方が高くつきます。また配列が 未ソート で 1 回しか探索しないなら、ソート (O(n log n)) + 二分探索 (O(log n)) より線形探索 (O(n)) の方が速いことすらあります。
アルゴリズム選びは「データのサイズ」「ソート済みか」「何回探索するか」の 3 点で決まる。線形探索を即否定せず、状況で使い分ける感覚を持とう。
Python の in 演算子
Python では target in arr で要素の有無を判定できます。内部では線形探索が走っており、計算量は同じく O(n) です。組み込みなので C で書かれていて定数倍は速いですが、オーダーは変わらないことを意識しましょう。arr.index(target) も同様に O(n) で、見つからない場合は例外を投げます (本問の -1 を返す挙動とは異なる)。
よくある質問
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 セクションを読み返してみましょう。
関連レッスン
要件
- 先頭から末尾まで順に比較する線形探索で実装すること
- 見つかった場合は最初に一致した位置 (0-indexed) を返す
- 見つからない場合は -1 を返す
入出力例
test-cases.txt
linearSearch([3,1,4,1,5,9,2,6], 5) → 4
linearSearch([7,1,2,3], 7) → 0
linearSearch([1,2,3,4], 4) → 3
linearSearch([1,2,3,4], 99) → -1
linearSearch([1,2,3,2,1], 2) → 1
linearSearch([42], 42) → 0