[자료구조] : 선형 검색 (C)

출처 > DO IT C언어 자료구조(입문편)

이번 시간에는 선형탐색에 대해서 알아보겠다.

선형 검색이란?

• 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘이다.
• 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 요소를 출력하는데, 이것이 선형 검색 OR 순차검색 알고리즘이다.

• 배열의 요소를 맨 앞부터 순서대로 검색한다.

다음 그림을 보자.

검색은 다음과 같이 진행된다.

1. 첫 번째 요소 6에 주목한다 -> 원하는 값이 없다.
2. 두 번째 요소 4에 주목한다 -> 원하는 값이 없다.
3. 세 번째 요소 3에 주목한다. -> 원하는 값이 없다.
4. 네 번째 요소 2에 주목한다. -> 원하는 값이다 검색에 성공했다.

만약에 키 값을 가진 요소가 배열에 항상 존재하지 않는다면?

-> 배열의 끝을 지나간다.

성공과 실패의 종결조건은 2가지다.

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우-> 검색 실패
2. 검색할 값과 같은 요소를 발견한 경우 -> 검샐 성공 

다음 예시를 보자,

#include <stdio.h>
#include <stdlib.h>

// <main>
//idx = Search(x, nx, ky);
//const int  a[] = x  
//int nx = int n 
//int key = ky
int Search(const int a[], int n, int key)// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형탐색한다.
{
	int i = 0;
	while (1)
	{
		if (i == n)
			return -1;
		if (a[i] == key)
			return i;
		i++;
	}

}

int main()
{
	int i, nx, ky, idx;
	int* x; // 포인터 x를 선언한다. why? -> 배열의 첫 번째 요소를 가리키려고
	puts("선형 검색\n");
	puts("요소 개수 : ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int)); // x에 대한 주소 값 자체가 -> 메모리를 만든다. -> nx만큼 배열이 형성된다.
	for (i = 0; i < nx; i++) // 1. 전체적으로 for문을 돌면서 사용자로부터 값을 받는다.
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]); // 배열에 값을 입력한다.
	}
	printf(" 검색 값  : ");
	scanf_s("%d", &ky); // ky값을 받는다. 선형탐색을 시작한다.
	idx = Search(x, nx, ky);
	if (idx == -1)
		puts("검색에 실패했습니다.");
	else
		printf("%d는 x[%d]에 있습니다.\n",ky, idx);


	free(x);
}

<핵심코드1>

// <main>
//idx = Search(x, nx, ky);

int Search(const int a[], int n, int key)// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형탐색한다.
{
	int i = 0;
	while (1)
	{
		if (i == n)
			return -1;
		if (a[i] == key)
			return i;
		i++;
	}

}

• Search 함수는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색한다.
• 만약 값이 key인 요소가 여러개 존재한다면 반환값은 검색 과정에서 처음 발견된 요소의 인덱스가 된다.
• key값이 존재하지 않으면 -1를 반환한다.

 1. i == n이 성립하는 경우 ( 종료조건 1 : 검색 실패하므로 -1를 반환 )
 2. a[i] == key가 성립하는 경우 (종료조건 2 : 검색 성공이므로 i를 반환 )

<일반적인 결과>

<반환 값이 중복 되는 경우>

while문이 아니라 for문으로 간단명료하게 표현해보자.

int Search(const int a[], int n, int key)
{
  int i;
  for(i = 0; i < n; i++)
    if(a[i] == key)
      return i;
   return -1;
}

※ 참고 : 무한 루프의 구현

1. while문

while(1)
{



}

2. for문

for( ; ; ) {



}

3. do~while

do{


}while(1);

보초법

• 선형 검색은 반복 할 때마다 종료조건을 확인한다.

1. 검색할 값을 발견하지 못하면 배열의 끝으로 간 경우
2. 검색할 값과 같은 요소를 발견한 경우

• 보초법은 검색할 값과 같은 요소를 뒤에 넣는 것이다.(빨강)

  • 6를 검색 : a[5] = 6를 저장 (검색 실패)
  • 2를 검색한다고 가정하면, (검색 성공) a[7] = 2를 넣는다(보초)

• 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 종료조건이 성립한다. -> 반복문에서 보초는 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

• 마지막 빨간색 배열 부분은 입력한 요소 개수에 1를 더한 크기의 배열을 생성한다.

다음 예제를 보자.

#include <stdio.h>
#include <stdlib.h>

int Search(int p[], int nx, int ky)
{
	int i = 0;
	p[nx] = ky; //검색값 ky를 보초로 p[nx]에 대입한다.
	while (1)
	{

		if (p[i] == ky)
			break;
		i++;
	}
	return i == nx ? -1 : i;
	//변수 i값이 nx이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.

}

int main()
{
	int i, nx, ky, idx;
	int* p;
	puts("선형탐색으로 검색한다.(보초법)");
	printf("요소 개수를 입력하세요 : "); scanf_s("%d", &nx);
	p = calloc(nx + 1, sizeof(int));//요소의 개수가 (nx+1)인 int형 배열을 생성했다.
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i); scanf_s("%d", &p[i]); // 사용자가 입력하는 spot
	}
	printf("검색값 : "); scanf_s("%d", &ky);
	idx = Search(p, nx, ky);
	if (idx == -1)
	{
		puts("검색에 실패했습니다.");
	}
	else
	{
		printf("%d(은) x[%d]에 있습니다. \n", ky, idx);
	}
	free(p);
	return 0;

}

<결과>

<핵심코드1>

int Search(int p[], int nx, int ky)
{
	int i = 0;
	p[nx] = ky; //검색값 ky를 보초로 p[nx]에 대입한다.
	while (1)
	{

		if (p[i] == ky)
			break;
		i++;
	}
	return i == nx ? -1 : i;
	//변수 i값이 nx이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다.

}

• 검색값 key를 보초로 a[n]에 대입한다.
• 배열 요소를 순서대로 검사한다. 이전에는
  1. if(i == n)
  2.if(a[i] == ky) 로 설정했는데, 하나의 if문만 사용했다.

• 삼항연산자로 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아닌지 보초인지 판단해야된다. 변수 i값이 nx이면 찾은 값이 보초 ==> 검색 실패 -1반환