#자료구조와 함께 배우는 알고리즘 입문 C언어편 - 3

3장 검색

 

03-1 검색 알고리즘

배열 검색

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행

2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검새을 수행

 - 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

 - 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

03-2 선형 검색

선형 검색/순차 검색

// 선형 검색
int search(const int a[], int n, int key)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		if (a[i] == key)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
}

int main(void)
{
	int i, nx, ky, idx;
	int* x;
	puts("선형 검색");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));
	for (i = 0; i < nx; i++)
	{
		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;
}

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색

 

배열 검색의 종료 조건

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

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

 

 

03-3 이진 검색

이진 검색

// 이진 검색
int bin_search(const int a[], int n, int key)
{
	int pl = 0;
	int pr = n - 1;
	int pc;
	do {
		pc = (pl + pr) / 2;
		if(a[pc] == key)
		{
			return pc;
		}
		else if (a[pc] < key)
		{
			pl = pc + 1;
		}
		else
		{
			pr = pc - 1;
		} 

	} while (pl <= pr);
	return -1;
}

int main(void)
{
	int i, nx, ky, idx;
	int* x;
	puts("이진 검색");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));
	printf("오름차순으로 입력하세요.\n");
	printf("x[0] : ");
	scanf_s("%d", &x[0]);
	for (i = 1; i < nx; i++)
	{
		do {
			printf("x[%d] : ", i);
			scanf_s("%d", &x[i]);
		} while (x[i] < x[i - 1]);
	}
	printf("검색 값 : ");
	scanf_s("%d", &ky);
	idx = bin_search(x, nx, ky);
	if (idx == -1)
	{
		puts("검색에 실패했습니다.\n");
	}
	else
	{
		printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);

	}
	free(x);

	return 0;
}

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색 (전제 조건 : 데이터가 키 값으로 이미 정렬상태)

 

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준

1. 시간 복잡도 : 실행에 필요한 시간을 평가

2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가

 

bsearch 함수(정렬된 배열에서 검색하는 함수)

특징 1. 검색 대상의 배열은 항상 정렬되어 있어야 함

특징 2. 검색하는 값과 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는 것은 아님

 

함수 포인터

// int를 받아들여 double로 반환하는 함수
double func(int);

// int를 받아들여 double을 반환하는 함수에 대한 포인터 fp의 선언
double(*fp)(int);

// int를 받아들여 double에 대한 포인터를 반환하는 함수 선언
double *fn(int);