선형 검색 & 순차 검색

선형 검색(linear search) ,순차 검색(sequential search)

선형검색 & 순차 검색 이란?

 

요소가 직선 모양으로 늘어선 배열에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하여 값을 찾아내는 알고리즘

선형검색 (linear search) , 순차 검색(sequential search) 이라고도 부른다.

 

선형 검색의 종료 조건

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

2. 검색할 값과 같은 요소를 발견한 경우

 

1번의 조건이 성립하면 검색 실패,

2번의 조건이 성립하면 검색 성공이다.

 

사실 선형 검색은 선형 검색이라는 알고리즘을 배우지 않아도 프로그래밍을 해 본 사람이라면 이름만 모를 뿐이지 많이들 쓰고 계시는 방식일 것이다.

 

코드 구현

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

//int형 배열 a, 배열 요소 개수 n , 찾을 키값
int Search(const int a[], int n, int key)
{
	int i = 0;

	while (1)
	{
    	//i가 배열의 마지막 인덱스와 같다면 검색 실패, -1 리턴
		if (i == n)
			return -1;
        //배열의 i인덱스의 값이 키값과 같다면 성공, i리턴(인덱스) 
		if (a[i] == key)
			return i;
		i++;
	}
}


int main(void)
{
	int nx, ky, idx;
	int* x; //배열의 첫 번째 요소에 대한 포인터

	puts("선형 검색\n");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);

	x = calloc(nx, sizeof(int));  //위에서 받은nx만큼 int형 배열 생성(메모리 할당)

	for (int i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}
	
	printf("검색값 : ");
	scanf_s("%d", &ky);
	idx = Search(x, nx, ky); //배열 x의 요소nx중에 값이 ky인 요소를 선형검색

	if (idx == -1)
	{
		puts("검색에 실패 하였습니다.");
	}
	else
	{
		printf("%d는 x[%d]에 있습니다.\n" ,ky, idx);
	}

	free(x); //메모리 할당 해제

	return 0;

}

 

이런식으로 배열의 첫번째 인덱스부터 끝까지 돌며 키값을 검색한다.

위에 코드에서 함수는 와일문으로 작성을 하였는데, for문으로 사용하는것이 더 깔끔한 것 같다.

 

int Search(const int a[], int n, int key)
{
	for (int i = 0; i < n; i++)
		if (a[i] == key)
			return i; // a[i]가 key값과 같으면 i리턴 , 성공
		return -1; // for문이 다 돌때까지 위의 조건이 true가 아니라면 -1 리턴
}

 

보초법

일단 설명하기전에 찾아보니 보초라는 뜻이 우리가 생각하는 보초,감시 이런 단어가 맞다.(Sentinel)

 

앞에 써놨듯이 선형검색 알고리즘이 끝나는 조건은 두가지였다.

 

첫번째는 검색한 값을 발견하지 못하고 배열의 끝을 지나간 경우 (실패 ㅠ)

두번째는 값과 같은 요소를 발견한 경우 (성공)

 

만약 이 알고리즘이 끝나는 조건을 2개가 아닌 1개로 줄인다면 비용이 반이 줄지않을까?

 

보초법를 사용하면 첫번째 조건은 필요가 없어진다.

우리가 찾을 키값을 배열의 마지막 인덱스로 추가해준다.

 

만약 A배열에서 2 라는 키를 선형 검색으로 보초법을 이용해 찾는다면

현재 A의 마지막인덱스 다음 인덱스에 2를 추가해주는 것이다.

 

그러면 배열의 끝까지 검색했을때 무조건 우리가 찾는 키값이 있는거기 때문에 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

즉 우리가 보초법을 써서 검색을 하여 리턴된 값이 보초라면 실패, 보초가 아니라면 성공이 되는것이다.

 

바로 코드로 보자.

 

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

//int형 배열 a, 배열 요소 개수 n , 찾을 키값
int Search(int a[], int n, int key)
{
	int i = 0;
	a[n] = key; //a배열의 마지막 인덱스에 키값을 넣어준다.

	while (1)
	{
		if (a[i] == key)
		{
			//a[i]의 값이 키와 같다면 반복문을 탈출한다.
			break;
		}
		i++;
	}
	//i가 마지막 인덱스라면 -1 리턴(실패), 아니라면 i 리턴(성공)
	return i == n ? -1 : i;
}


int main(void)
{
	int nx, ky, idx;
	int* x;

	puts("선형 검색\n");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);

	x = calloc(nx+1, sizeof(int)); //요소 개수로 입력받은 nx에 +1을 하여 배열 생성

	for (int i = 0; i < nx; i++) //값을 입력받는것은 nx까지만
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}
	
	printf("검색값 : ");
	scanf_s("%d", &ky);
	idx = Search(x, nx, ky);

	if (idx == -1)
	{
		puts("검색에 실패 하였습니다.");
	}
	else
	{
		printf("%d는 x[%d]에 있습니다.\n" ,ky, idx);
	}

	free(x);

	return 0;

}

앞의 while문 에서는 반복문을 탈출하기 위한 반복조건이 2개 였다.

하지만 보초법을 사용하면 이처럼 반복 종료에 대한 판단 횟수가 절반으로 줄어든다.