線形探索

1. 線形探索アルゴリズム
2. 線形探索の例
3. 線形探索アルゴリズムの実装
4. 線形探索アルゴリズムの複雑さ

線形探索は最もシンプルな探索アルゴリズムです。このアルゴリズムでは、配列全体を横断して要素を探索し、各要素を目的の項目と比較して一致するものを見つけるので、逐次探索とも呼ばれます。目的の要素が見つかった場合は、インデックスまたはその要素が返されます。また、配列の中にある項目の複数回の出現を探すこともできます。これは、主にソートされていない配列内の項目を探索するために使用されます。バイナリ探索よりもずっと遅いので、実用的には使われません。

線形探索アルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。

線形探索の例

配列があるとしましょう。(5, 3, 4, 2, 1, 6).

• ケース 1: X = 5 を探したい。

最初の要素自体は一致しているので、インデックス 0 を返します。(ベストケース)

• ケース 2: X = 1 を探したい。

配列を走査してインデックス 4 に到達し、一致するものを見つけてそのインデックスを返します。(平均的なケース)

• ケース 3: X = 9 を探したい

配列を探索しますが、配列の最後の要素に到達しても一致するものは見つかりません。戻り値は -1 です。(最悪の場合)

線形探索アルゴリズムの実装

シングルマッチのための線形探索アルゴリズム

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) return i;
  }
  return -1;
}

int main() {
  int n = 5;
  int arr[] = {2, 4, 0, 1, 9};
  int x = 1;
  int result = search(arr, n, x);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index: " << result;
}

複数のマッチのための線形探索アルゴリズム

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
  vector<int> ans;
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      ans.push_back(i);
    }
  }
  return ans;
}

int main() {
  int n = 9;
  int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
  int x = 1;
  vector<int> res = search(arr, n, x);
  if (res.empty()) {
    cout << "Element not found!!";
  } else {
    cout << "Element found at ";
    for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
    }
  }
}

線形探索アルゴリズムの複雑さ

時間計算量

• 平均ケース

線形探索アルゴリズムの時間的複雑さは O(n) です。

• 最良の場合

最良の時間的複雑さは O(1) です。これは探索対象の要素が配列内に最初に存在する場合に発生します。

• 最悪の場合

最悪の場合は、探している要素が配列内に存在しないか、配列の最後のインデックスにある場合です。最悪の場合の時間的複雑さは O(n) です。

空間計算量

このアルゴリズムの空間複雑度は、マッチ数と使用される実装に依存する。一般的に、空間の複雑さは O(1) とされているが、複数のマッチインデックスが配列内に格納されている場合には、より複雑になる可能性がある。