[알고리즘] 순차 검색 (Sequential Search)

순차 검색(Sequential Search)은

가장 기본적인 검색 방법으로 주어진 데이터에서 순차적으로 찾고자 하는 값이 나올때까지 루프를 반복하는 방식입니다.

이 알고리즘으로 키(특정값)를 찾기 위한 검색 횟수는 항목의 위치에 따라 다르지만 최악의 경우에는 data 의 크기(n) 만큼 검색해야 합니다.

• 장점 : 구현이 단순하다.
• 단점 : 찾아야 할 Data 범위가 크고, 키에 대한 위치정보가 없다면 모두 확인해야 한다.(비효율적)

 

Algorithm

1. 입력 인수

• n : 입력 Data Array 의 Size
• Data[ ] : Key 값을 검색할 Data
• x : 검색해야 하는 Key 값

 

2. 출력

• Key 값이 존재하는 위치 index

 

3. 수행 절차

• 반복 loop (for문 또는 while) 를 사용하여 Data[index] 에 일치하는 Key 값이 있는지 확인
• 존재하지 않는 경우, index 를 n 보다 큰 값으로 입력하여 구분할 수 있도록 처리
• 검색 완료 후 위치 index return 한다. ※ 찾으면 바로 함수를 중단하고 return 하는 방식도 가능하다.

4. 코드 구현

int Seq_Search(int n, const int Data[], int x) {
	int index = 1;
    
	//! for-loop 또는 while-loop 사용
	while (index <= n && Data[index] != x)
		index++;

	//! 존재하지 않는 경우, index 를 N보다 큰 값으로 처리
	if (index > n)
		index = 99999;
        
	//! 검색 완료 후 위치 return
	return index;
}

 

 

Test Function

int main(void)
{
	printf("------------------ Test Data ------------------\n");
	for (int i = 0; i < N; i++) {
		printf("[%d] %d\n", i, testarr[i]);
	}
	
	printf("-------------------- Test --------------------\n");

	int value, result;

	value = 36;
	result = seqsearch(N, testarr, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);


	value = 12;
	result = seqsearch(N, testarr, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);

	value = 100;
	result = seqsearch(N, testarr, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);

	return 0;
}

 

Test Result

 

Test Data 는 전역으로 10개의 int 형 array 로 정의

const int N = 10;
int testarr[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 };

 

Test Result 는 36, 12, 100 을 찾는 Test Code 를 실행한 결과이다.

• 36 의 경우, testarr[ ] 의 index 9 (0부터 시작하여 10번째) 로 return 된다.
• 12 의 경우, testarr[ ] 의 index 5 (0부터 시작하여 6번째) 로 return 된다.
• 100 은 testarr[ ] 에 존재하지 않는 것으로 return 된다.

------------------ Test Data ------------------
[0] 9
[1] 11
[2] 8
[3] 3
[4] 22
[5] 12
[6] 23
[7] 45
[8] 31
[9] 36
-------------------- Test --------------------
36 is 9 in array
12 is 5 in array
100 is not in array

 

다음 포스팅에는 좀 더 발전된 검색 방법인 이진 검색 (Binary Search) 에 대해서 공유하겠습니다.

 

이상입니다.