線形探索(リニアサーチ)とは

線形探索とは、サーチアルゴリズムの一種です。リストや配列に入ったデータに対して、先頭要素から順に比較して見るけるまで続けるという、単純なアルゴリズムです。

n個のデータから1つのデータを見つけ出すのにかかる、時間計算量は O(n) です。

アルゴリズムの解説

  1. データの先頭要素を取り出します。
  2. 取り出したデータが目的のデータかどうか一致判定します。
  3. 目的のデータに一致すれば探索完了です。
  4. 一致しなければ次のデータを取り出し 2. に戻ります。次のデータが存在しなければ終了します。
線形探索

特に難しいところのない、シンプルなアルゴリズムです。

サンプルコード

見つかった要素のあるインデックスを返します。データが存在しなければ -1 を返すようにしています。

C#のサンプルコードでは、IEquatableインタフェースを実装して入れば同じ値かどうかの判定ができるので、ジェネリックで対応しています。

C#

public static int LinearSearch<T>(T[] array, T target) where T : IEquatable<T>
{
    // 配列を先頭から走査し、見つかったらインデックスを返す
    for (int i = 0; i < array.Length; i++)
    {
        if (target.Equals(array[i])) return i;
    }

    // 見つからなかったら -1 を返す
    return -1;
}