[자료구조/C] 순차 탐색(sequential search)

순차 탐색?

정렬되지 않은 배열의 항목들을 처음부터 마지막까지 차례대로 하나씩 검사하여 원하는 항목을 찾아가는 방법

 

출처 : C언어로 쉽게 풀어쓴 자료구조

#include <stdio.h>

int seq_search(int key, int low, int high){
	int i;
    for (i=low; i<=high; i++)
    	if (list[i]==ley)
        	return i; //탐색에 성공하면 인덱스를 반환하고 종료
    return -1; //탐색에 실패하면 -1 반환
}

순차 탐색의 시간복잡도

탐색이 성공할 경우, 찾으려는 항목(key)의 위치에 따라 비교 횟수가 다르다. 첫 번째에 있으면 1회, 두 번째에 있으면 2회, ... n번째에 있으면 n회 비교한다. 즉, 모든 키가 탐색될 확률이 동일하다고 가정하면,

평균 비교 횟수는 (1+2+3+....n)/n = (n+1)/2이며

실패했을 경우의 비교횟수는 n번이다.

 

따라서 순차 탐색의 시간 복잡도는 O(n)이다.