C/C++による線形探索プログラムの実装方法を解説

線形探索とは

線形探索（リニアサーチ）アルゴリズムでは、目的の要素を配列の各要素と先頭から順番に比較していきます。該当する要素が見つかれば、その位置を出力します。

線形探索の最悪計算量は O(n) です。

入力: arr[] = { 12, 35, 69, 74, 165, 54}
探索値 = 165
出力: 165 は位置 5 に存在します。

アルゴリズムの解説

線形探索は、指定された数値が配列内に存在するかどうか、存在する場合にはどの位置にあるのかを調べるための基本的な探索アルゴリズムです。「逐次探索」と呼ばれることもあります。

その動作は非常にシンプルで、以下の手順で行われます。

• 配列の先頭要素から順に、探索対象の値と1つずつ比較します。
• 一致する要素が見つかれば、その時点で探索を終了し、位置を返します。
• 配列の末尾まで比較しても見つからなければ、「存在しない」と判断します。

データがソートされている必要がないため、小規模なデータや整列されていない配列に対して手軽に使えるのが特徴です。ただし、要素数が多い場合には二分探索（O(log n)）などの方が効率的になります。

サンプルコード

以下は、C++で線形探索を実装した例です。配列の中から値「165」を探し出します。

#include <iostream>
using namespace std;

int main() {
   int sea, c, n = 6;
   int arr[] = { 12, 35, 69, 74, 165, 54 };

   sea = 165;

   for (c = 0; c < n; c++) {
      if (arr[c] == sea) {
         cout << sea << " は位置 " << c + 1 << " に存在します。\n";
         break;
      }
   }

   if (c == n)
      cout << sea << " は配列内に存在しません。\n";

   return 0;
}

コードのポイント

• forループで配列の各要素を走査し、if文で探索値との一致を判定しています。
• 一致した場合は break 文でループを抜け、無駄な比較を省きます。
• ループ変数 c が n と等しいまま終了した場合は、配列全体を調べても見つからなかったことを意味します。

実行結果

165 は位置 5 に存在します。