線形探索
最終更新
線形探索（逐次探索とも呼ばれます）は最も単純な探索アルゴリズムです。最初の要素から始めて、一致が見つかるか要素がなくなるまで、各要素を目的の値と比較していきます。データについて何の前提も置きません — 配列は未ソートでもよく、要素は等しいかどうかを比較できるものなら何でも構いません。
上のアニメーションは、走査が左から右へ進むにつれて各比較をハイライトし、目的の値が現れた瞬間に停止します。その単純さの代償は速度です。最悪の場合はすべての要素が確認されるため、実行時間は O(n) になります。データがソート済みなら、二分探索が同じ答えを O(log n) で見つけます — 先にソート済みのデータが必要ならマージソートを参照してください。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良ケース | O(1) | 最初の要素が目的の値である場合。 |
| 平均ケース | O(n) | 平均すると、ヒットするまでに要素の半分が確認される。 |
| 最悪ケース | O(n) | 目的の値が最後にある — またはまったく存在しない。 |
| 空間 | O(1) | 現在のインデックスだけを保持する。 |
ステップごとの説明
| ステップ | 何が起こるか |
|---|---|
| 1 | 配列の最初の要素であるインデックス0から始める。 |
| 2 | 現在の要素を目的の値と比較する。 |
| 3 | 等しければ現在のインデックスを返す — 発見。 |
| 4 | そうでなければ1つ右へ進み、繰り返す。 |
| 5 | 一致がないまま配列の末尾に達したら、目的の値は存在しない（-1 を返す）。 |
具体例
[7, 3, 9, 1, 5, 8, 2] から 5 を探索する場合：
| 比較 | インデックス | 要素 | 結果 |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — 走査を続ける。 |
| 2 | 1 | 3 | 3 ≠ 5 — 走査を続ける。 |
| 3 | 2 | 9 | 9 ≠ 5 — 走査を続ける。 |
| 4 | 3 | 1 | 1 ≠ 5 — 走査を続ける。 |
| 5 | 4 | 5 | 5 = 5 — インデックス4で発見。 |
線形探索を使うべき場面
| 使うべきとき | 避けるべきとき |
|---|---|
| データが未ソート、または絶えず変化しているとき | データがソート済みのとき — 二分探索の方が指数関数的に速い |
| コレクションが小さく、単純さが勝るとき | データセットが大きく、繰り返し探索されるとき |
| 順次アクセスしかできないとき（ストリーム、連結リスト） | O(1) の検索のためにインデックスやハッシュテーブルを用意できるとき |
Linear Searchのコード
Python, JavaScript, Java, C++, C, Pseudocodeによるクリーンで実行可能なLinear Searchの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのLinear Searchのコード
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))JavaScriptでのLinear Searchのコード
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));JavaでのLinear Searchのコード
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}C++でのLinear Searchのコード
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}CでのLinear Searchのコード
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}PseudocodeでのLinear Searchのコード
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)線形探索のよくある質問
線形探索の時間計算量はどのくらいですか？
平均ケースと最悪ケースで
O(n) です。走査がすべての要素を訪れる必要があるかもしれないためです。最初の要素が目的の値だった場合の最良ケースは O(1) です。追加空間は O(1) です。線形探索にはソート済みのデータが必要ですか？
いいえ — それこそが最大の利点です。線形探索は各要素を等しいかどうかで確認するため、完全に未ソートのデータでも動作します。順序は一切関係ありません。対照的に、二分探索はソート済みの配列でしか動作しません。
線形探索が二分探索より優れているのはどんなときですか？
データが未ソートで1回しか探索しないとき（先にソートすると
O(n log n) かかります）、コレクションがごく小さいとき、あるいはストリームや連結リストのように順次アクセスしかできないときです。ソート済み配列での繰り返しの検索なら二分探索が勝ちます。線形探索と逐次探索は同じものですか？
はい — 2つの名前は同じアルゴリズムを指します。目的の値が見つかるか、コレクションが終わるまで、要素を順番に走査します。
線形探索は平均で何回比較しますか？
目的の値が存在し、どの位置にも同じ確率であるなら、平均で約
n/2 回の比較になります。存在しない場合はちょうど n 回です。この線形の増加こそが「線形探索」と呼ばれる理由です。関連リソース
その他の可視化
