선형 검색

선형 검색 기술은 가장 간단한 기술입니다. 이 기술에서는 항목을 하나씩 검색합니다. 이 절차는 정렬되지 않은 데이터 세트에도 적용됩니다. 선형 검색은 순차 검색이라고도 합니다. 시간 복잡도가 n O(n) 정도이기 때문에 선형이라고 합니다.

선형 검색 기법의 복잡성

• 시간 복잡성: 오(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

알고리즘

linearSearch(array, size, key)

입력 - 정렬된 배열, 배열의 크기 및 검색 키

출력 - 키의 위치(발견된 경우), 그렇지 않으면 잘못된 위치입니다.

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

예시

#include<iostream>
using namespace std;

int linSearch(int array[], int size, int key) {
   for(int i = 0; i<size; i++) {
      if(array[i] == key) //search key in each places of the array
         return i; //location where key is found for the first time
   }
   return -1; //when the key is not in the list
}

int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; //create an array of size 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;
}

출력

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