線形探索（リニアサーチ）とは？アルゴリズムの仕組みとC++実装例を解説

線形探索（Linear Search）は、データ検索手法の中で最もシンプルなアルゴリズムです。この手法では、先頭から順に要素を一つずつ比較しながら目的の値を探していきます。最大の特徴は、ソートされていないデータにも適用できるという点です。線形探索は「逐次探索（Sequential Search）」とも呼ばれます。「線形」という名前は、計算時間がデータ数 n に比例する O(n) のオーダーであることに由来しています。

一方で、二分探索などの高速なアルゴリズムと異なり、大規模なデータセットでは効率が劣るため、小規模なデータやソートされていない配列を扱う場面で主に活用されます。

線形探索の計算量

• 時間計算量： O(n) ― 最悪の場合、全ての要素を確認する必要があるため
• 空間計算量： O(1) ― 追加のメモリをほとんど必要としないため

入力と出力の例

Input:
A list of data:
20 4 89 75 10 23 45 69
the search key 10
Output:
Item found at location: 4

この例では、8個の要素を持つ配列から値「10」を探索し、インデックス4（5番目の要素）で見つかっています。

アルゴリズム（擬似コード）

linearSearch(array, size, key)

入力 − 配列、配列のサイズ、探索キー（対象の値）

出力 − キーが見つかった場合はその位置（インデックス）、見つからない場合は無効な位置（例：-1）

Begin
    for i := 0 to size -1 do
        if array[i] = key then
            return i
    done
    return invalid location
End

処理の流れは非常に単純です。ループで配列を走査し、各要素が探索キーと一致した時点でそのインデックスを返します。最後まで一致する要素が存在しなければ、「見つからなかった」ことを示す値（通常は -1 など）を返します。

C++による実装例

#include<iostream>
using namespace std;

int linSearch(int array[], int size, int key) {
    for(int i = 0; i<size; i++) {
        if(array[i] == key) // 配列の各要素とキーを比較
            return i;       // 最初にキーが見つかった位置を返す
    }
    return -1; // キーがリスト内に存在しない場合
}

int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n]; // サイズnの配列を作成
    cout << "Enter items: " << endl;

    for(int i = 0; i< n; i++) {
        cin >> arr[i];
    }

    cout << "Enter search key to search in the list: ";
    cin >> searchKey;

    if((loc = linSearch(arr, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

コードのポイント

linSearch 関数は、for ループを使って配列の先頭から順に各要素と探索キーを比較します。一致する要素が見つかればその時点でインデックスを返し、関数を終了します。これにより、不要な比較を省くことができます。ループが完了しても見つからない場合は -1 を返すことで、呼び出し元に「該当なし」を伝えます。

実行結果

Enter number of items: 8
Enter items:
20 4 89 75 10 23 45 69
Enter search key to search in the list: 10
Item found at location: 4

このプログラムでは、8個の数値からなる配列の中から値「10」を探索し、位置4（インデックス番号4）で発見できたことが出力されています。

まとめ

線形探索は実装が簡単で、ソート不要・追加メモリ不要という利点があります。ただし計算量が O(n) となるため、大量のデータを扱う場合には二分探索（O(log n)）などとの使い分けが重要になります。アルゴリズムの基礎として、まず確実に理解しておきたい探索手法の一つと言えるでしょう。