선형 검색(Linear Search)은 가장 기본적이고 단순한 탐색 기법입니다. 데이터 집합의 첫 번째 요소부터 마지막 요소까지 하나씩 순서대로 확인하면서 원하는 값을 찾아냅니다. 이 방식은 정렬되지 않은 데이터에도 그대로 적용할 수 있다는 큰 장점이 있으며, '순차 검색(Sequential Search)'이라고도 불립니다. 이름이 '선형(linear)'인 이유는 시간 복잡도가 데이터의 크기 n에 비례하여 O(n)으로 증가하기 때문입니다.
선형 검색의 복잡도
- 시간 복잡도: O(n)
- 공간 복잡도: O(1)
입력과 출력
입력:
데이터 목록:
20 4 89 75 10 23 45 69
검색 키: 10
출력:
항목을 찾은 위치: 4
알고리즘
linearSearch(array, size, key)
입력 − 배열, 배열의 크기(size), 검색할 키(key)
출력 − 키가 존재하면 해당 위치(index)를 반환하고, 존재하지 않으면 유효하지 않은 위치(-1 등)를 반환합니다.
Begin
for i := 0 to size - 1 do
if array[i] = key then
return i
done
return invalid location
End
C++ 구현 예제
#include<iostream>
using namespace std;
int linSearch(int array[], int size, int key) {
for(int i = 0; i < size; i++) {
if(array[i] == key) // 배열의 각 위치에서 검색 키와 일치하는지 확인
return i; // 키가 처음 발견된 위치를 반환
}
return -1; // 키가 목록에 존재하지 않는 경우
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n]; // 크기 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
선형 검색의 특징과 활용
선형 검색은 구현이 매우 간단하고 추가적인 메모리가 거의 필요 없어 소규모 데이터나 정렬되지 않은 데이터를 다룰 때 유용합니다. 다만 데이터가 클 경우 모든 요소를 하나씩 확인해야 하므로 비효율적일 수 있습니다. 이런 경우 이진 검색(Binary Search)처럼 O(log n)의 시간 복잡도를 가진 알고리즘이 더 적합하지만, 이진 검색은 사전에 데이터가 정렬되어 있어야 한다는 전제 조건이 필요합니다.