선형 검색

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)로 표시되지만 여러 일치하는 인덱스가 배열 내에 저장되면 더 많을 수 있습니다.