순차 탐색

순차 탐색은 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법이다. 이름에서도 알 수 있다시피 처음부터 끝까지 모두 확인하여 원하는 항목을 찾아가는 방법이다. 코드는 다음과 같다.

int seq_search(int key, int low, int high) {
	int i;
	
	for(i = low; i <= high; i++)
		if(list[i] == key)
			return i;
	return -1;
}

개선된 순차 탐색

순차 탐색에서 비교 횟수를 줄이는 방법을 생각해 보자. 위에서 작성된 코드는 리스트 전체를 탐색하기 위한 반복문에서 리스트의 끝을 테스트하는 비교 연산이 있고 반복문 안에 키 값의 비교 연산이 있다.

아래의 코드에서는 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해 리스트의 끝을 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하였다. 이와 같은 방법으로 탐색하면 루프 종료 조건이 단순해지고 반복 과정에서 검사할 조건이 하나로 줄어들어 성능이 개선된다. 이러한 기법을 Sentinel 기법이라고 한다.

int seq_search2(int key, int low, int high) {
	int i;
	
	list[high + 1] = key;
	// 키값을 찾으면 종료
	for(i = low; list[i] != key; i++);
	
	if(i == (high + 1))
		return -1; // 탐색 실패
	else
		return i; // 탐색 성공
}

순차 탐색의 시간 복잡도

• 최선의 경우: 탐색 대상이 배열의 첫 번째 원소에 위치하는 경우에는 $O(1)$이다.
• 최악의 경우: 탐색 대상이 배열의 마지막 원소에 위치하거나 없는 경우에는 $O(n)$이다.
• 평균적인 경우에도 $O(n)$이다.

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구