2.1 선형 검색 (Linear Search)

배열에서 검색하는 방법중에 가장 기본이 되는 알고리즘으로써,

직선 모양의 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 앞부터 순서대로 요소를 검색하는 것이다.

 

값 2를 선형 검색을 해보자

6

4

3

2

1

3

8

6

4

3

2

1

3

8

6

4

3

2

1

3

8

6

4

3

2

1

3

8

 

위와 같은 배열이 있을 때, 6->4->3->2 순으로 검색을 하게 된다.

원하는 값을 찾을 때까지 모든 원소를 탐색하는 것이다.

그러나 원하는 요소가 없는 경우에는 끝까지 검색을 수행해도 값이 나오지 않게 될 것이다.

 

이로써, 선형 검색의 종료 조건은 아래와 같다.

1. 검색할 값을 발견한 경우

2. 배열 끝까지 검색해도 검색할 값을 찾지 못 한 경우

 

선형 검색을 구현해보자.

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

using namespace std;

// N개의 배열 a에서 key와 일치하는 요소를 검색하기
int search(const int a[], int n, int key)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i] == key)
			return i;//검색 성공
		return -1;//검색 실패
	}

}

int main(void)
{
	int i, nx, ky, idx; //배열 개수, 키 값, 인덱스

	int* x;//배열 첫 요소 포인터
	puts("선형 검색");
	printf("요소 개수 : ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int)); // 요소의 개수가 nx인 int형 배열 생성
	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ",i);
		scanf("%d", &x[i]);
	}
	printf("검색 값 : ");
	scanf("%d", &ky);
	idx = search(x, nx, ky);
	if (idx == -1)
		puts("검색 실패");
	else
		printf("%d는 x[%d]에 있습니다.\n", ky, idx);
	free(x);//배열 해제

	return 0;


}