순차 검색(Sequential Search) 개념 및 구현
순차 검색(Sequential Search)은 선형 검색(Linear Search)으로도 불리며 리스트에서 순차적으로 탐색하면서 원하는 값을 찾아내는 알고리즘입니다.
순차 검색은 구현이 쉽고 리스트의 정렬 여부와 상관없이 동작하는 장점이 있지만, 리스트의 모든 요소를 확인해야 하기 때문에 검색할 리스트의 길이가 길면 비효율적이라는 단점이 있습니다.
시간 복잡도(Time complexity)
| Operation | Best | Average | Worst |
| Search | O(1) | Θ(n) | O(n) |
*n = 데이터 수
종료 조건
순차 검색의 종료 조건은 두 가지가 있습니다. 다음 조건중 하나라도 성립하면 검색을 종료합니다.
1. 검색을 실패할 경우
- 검색할 값을 발견하지 못하고 리스트의 끝을 지나간 경우
2. 검색을 성공할 경우
- 리스트에서 검색할 값과 같은 요소를 발견한 경우
구현
위 종료 조건을 가지고 구현을 하면 다음과 같습니다.
검색을 실패하면 -1을 반환하고 성공하면 요소의 인덱스 i를 반환합니다.
int sequentialSearch(int[] arr, int n, int key) {
int i = 0;
while (ture) {
if(i==n) return -1; // 종료 조건 1. 검색 실패
if(arr[i] == key) return i; // 종료 조건 2. 검색 성공
i++;
}
}위 구현 방식은 검색을 반복할 때마다 두 가지 종료 조건을 판단하게 됩니다. 이것은 리스트의 길이가 길수록 오버헤드가 크게 됩니다.
보초 법(Sentinel method)을 사용하면 두 가지 종료조건 중 검색 실패 조건을 제거하여 판단 횟수를 2회에서 1회로 줄일 수 있습니다.
보초 법 (Sentinel method)
보초 법이란 반복의 종료를 알리는 특정한 값인 보초(Sentinel) 값을 사용하여 종료 조건중 검색 실패 조건을 제거하여 판단 횟수를 줄이는 방법입니다.
검색하고자 하는 키 값을 기존 리스트의 맨 끝 자리에 추가하고 이를 보초 값으로 사용합니다.
이렇게 하면 리스트에 찾던 값이 없어도 보초 값까지 검색하면 "종료 조건 1(검색 실패)"을 만족하게 됩니다.
이렇게 보초는 반복문에서 종료 판단 횟수를 줄이는 역할을 하게 됩니다.
Sentinel Linear Search
보초 법(Sentinel method)을 사용하는 선형 검색을 Sentinel Linear Search라고 합니다.
구현은 다음과 같습니다.
int sequentialSearch(int[] arr, int n, int key) {
int i = 0;
arr[n] = key; // 배열 마지막에 보초값 추가
while (ture) {
if(arr[i] == key) break; // 종료 조건 2. 검색 성공
i++;
}
return i == n ? -1 : i; // 보초값이면 -1 리턴, 아니면 요소의 인덱스 리턴
}이 구연은 반복문이 완료되면 찾은 값이 배열의 원래 데이터인지 보초 값인지 판단을 하고 값을 리턴합니다.
- 보초 값(i==n)이면 검색한 값이 없으므로 -1 리턴
- 그렇지 않으면 검색 성공이므로 요소의 인덱스 리턴
Sentinel Linear Search에서는 반복 문안에 "종료 조건 1" 이 제거되어 판단 횟수가 절반으로 줄어든 것을 확인할 수 있습니다.
