[c] 알고리즘 - 선형검색, 이진검색

mj·2022년 4월 23일
0

[C] 알고리즘

목록 보기
5/20

선형 검색(순차 검색)
: 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검섹

  • 선형 검색 종료 조건
  1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
  2. 검색할 값과 같은 요소를 발견한 경우

1-1. while문을 사용한 방법

/* 선형 검색 */
#include <stdio.h>
#include <stdlib.h>

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

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);		/* 배열 x의 값이 ky인 요소를 선형 검색 */

	if (idx == -1)
		puts("검색에 실패했습니다.");
	else
		printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
	
	free(x);						/* 배열을 해제 */
	
	return 0;
}

1-2. for문을 사용한 방법

while문보다 짧고 간결함.

/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(버전 1 : 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, 2를 모두 체크함. -> 많은 비용 발생

검색하고자 하는 키 값을 맨 끝 요소에 저장. 저장하는 값을 보초(sentinel)라고 함.
원하는 값이 데이터에 존재하지 않아도 보초까지 검색하면 종료조건 2가 성립함.
따라서 종료조건 1이 없어도 된다.
종료 판단 조건을 2회 -> 1회로 줄이는 역할을 함.

/* 선형 검색(보초법) */
#include <stdio.h>
#include <stdlib.h>

/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) ---*/
int search(int a[], int n, int key)
{
	int i = 0;
	a[n] = key;						/* 보초를 추가 */

	while (1) {
		if (a[i] == key)
			break;					/* 원하는 키 값을 찾은 경우 */
		i++;
	}

	return i == n ? -1 : i;
}

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

	puts("선형 검색(보초법)");
	printf("요소의 개수 : ");
	scanf("%d", &nx);
	x = calloc(nx + 1, sizeof(int));		/* 요소의 개수(nx + 1)인 int형 배열을 생성 */

	for (i = 0; i < nx; i++) {				/* 주의 : 값을 읽어 들인 것 nx 개 */
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}

	printf("검색 값 : ");
	scanf("%d", &ky);
	idx = search(x, nx, ky);				/* 배열 x에서 값이 ky인 요소를 선형 검색 */
	
	if (idx == -1)
		puts("검색에 실패했습니다.");
	else
		printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);

	free(x);								/* 배열을 해제 */

	return 0;
}



2. 이진 검색

  • 조건
    데이터의 키 값이 이미 오름차순 또는 내림차순으로 정렬됨

  • 이진 탐색의 시간 복잡도

    참고) https://jwoop.tistory.com/9

/* 이진 검색 */
#include <stdio.h>
#include <stdlib.h>

/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 이진 검색 ---*/
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("%d", &nx);
	x = calloc(nx, sizeof(int));		/* 요소의 개수 nx인 int형 배열을 생성 */
	
	printf("오름차순으로 입력하세요.\n");
	printf("x[0] : ");
	scanf("%d", &x[0]);
	for (i = 1; i < nx; i++) {
		do {
			printf("x[%d] : ", i);
			scanf("%d", &x[i]);
		} while (x[i] < x[i - 1]);		/* 바로 앞의 값보다 작으면 다시 입력 */
	}
	
	printf("검색 값 : ");
	scanf("%d", &ky);
	idx = bin_search(x, nx, ky); 		/* 배열 x에서 값이 ky인 요소를 이진 검색 */
	
	if (idx == -1)
		puts("검색에 실패했습니다.");
	else
		printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);

	free(x); 			/* 배열 해제 */

	return 0;
}



복잡도(Complexity)

  1. 시간 복잡도 : 실행에 필요한 시간을 평가
  2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

복잡도와 증가율



bsearch 함수

bsearch 함수

  • 헤더 : #include <stdlib.h>
  • 형식 : void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void*));
    bsearch(키 값, 배열의 포인터, 배열의 요소 개수, 배열의 요소 크기, 두 요소를 비교하기 위한 함수 포인터)
  1. const void *key : 찾으려는 자료의 포인터 주소
  2. const void *base : 찾는 대상이 되는 테이블 포인터 주소
  5. 두 요소를 비교하기 위한 함수 포인터
    (리턴값이 양수이면 오른쪽, 음수이면 왼쪽)
  • 반환 : 일치하는 요소에 대한 포인터를 반환, 일치하는 요소가 없다면 NULL 포인터를 반환
  • 조건 : 검색 대상의 배열은 항상 정렬되어 있어야 한다.
/* bsearch 함수를 사용하여 오름차순으로 정렬된 배열을 검색 */
#include <stdio.h>
#include <stdlib.h>

/*--- 정수를 비교하는 함수(오름차순) ---*/
int int_cmp(const int *a, const int *b)
{
	if (*a < *b)
		return -1;
	else if (*a > *b)
		return 1;
	else
		return 0;
}

/*--- 조건 연산자를 사용한 비교 함수 ---*/
// int int_cmp(const int *a, const int *b)
// {
// 	return *a<*b ? -1: *a>*b ? 1 : 0;
// }

/*--- 캐스팅(casting)없이 사용할 수 있는 비교함수 ---*/
// int int_cmp(const void *a, const void *b)
// {
// 	if(*(int *)a < *(int *)b)
// 		return -1;
// 	else if(*(int *)a > *(int *)b)
// 		return 1;
// 	else
// 		return 0;
// }

int main(void)
{
	int i, nx, ky;
	int *x;		 		/* 배열의 첫 번째 요소에 대한 포인터 */
	int *p; 	        /* 검색한 요소에 대한 포인터 */
	
	puts("bsearch 함수를 사용하여 검색");
	printf("요소의 개수 : ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int)); 		/* 요소의 개수 nx인 int형 배열을 생성 */

	printf("오름차순으로 입력하세요.\n");
	printf("x[0] : ");
	scanf("%d", &x[0]);
	for (i = 1; i < nx; i++) {
		do {
			printf("x[%d] : ", i);
			scanf("%d", &x[i]);
		} while (x[i] < x[i - 1]); 	/* 바로 앞의 값보다 작으면 다시 입력 */
	}

	printf("검색 값 : ");
	scanf("%d", &ky);
	p = bsearch(&ky, 					                /* 검색 값에 대한 포인터 */
		x,	 							                /* 배열 */
		nx,				 				                /* 요소의 개수 */
		sizeof(int),									/* 요소의 크기 */
		(int(*)(const void *, const void *)) int_cmp 	/* 비교 함수 */
	);

	if (p == NULL)
		puts("검색에 실패했습니다.");
	else
		printf("%d는 x[%d]에 있습니다.\n", ky, (int)(p - x));
	
	free(x); 		/* 배열을 해제 */

	return 0;
}

비교 함수

/*--- 정수를 비교하는 함수(오름차순) ---*/
int int_cmp(const int *a, const int *b)
{
	if (*a < *b)
		return -1;
	else if (*a > *b)
		return 1;
	else
		return 0;
}
/*--- 정수를 비교하는 함수(내림차순) ---*/
int int_cmpr(const int *a, const int *b)
{
	if (*a < *b)
		return 1;
	else if (*a > *b)
		return -1;
	else
		return 0;
}

구조체 배열에서 검색하기

/*--- Person형의 비교 함수(오름차순으로 이름 정렬) ---*/
int npcmp(const Person *x, const Person *y)
{
	return strcmp(x->name, y->name);
}

strcmp()
str1 < str2 : 음수반환
str1 > str2 : 양수반환
str1 == str2 : 0반환

/* bsearch 함수를 사용한 구조체 배열에서의 검색 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	char name[10]; 		/* 이름 */
	int height; 		/* 키 */
	int weight; 		/* 몸무게 */
} Person;

/*--- Person형의 비교 함수(오름차순으로 이름 정렬) ---*/
int npcmp(const Person *x, const Person *y)
{
	return strcmp(x->name, y->name);
}
int main(void)
{
	Person x[] = {					/* 배열 요소는 이름의 오름차순으로 */
		{ "김영준", 179, 79 }, 		/* 정렬되어 있지 않으면 안 됩니다. */
		{ "박현규", 172, 63 },
		{ "이수진", 176, 52 },
		{ "최윤미", 165, 51 },
		{ "함진아", 181, 73 },
		{ "홍연의", 172, 84 },
	};
	int nx = sizeof(x) / sizeof(x[0]); 		/* 배열 x의 요소의 개수 */
	int retry;

	puts("이름으로 검색합니다.");
	do {
		Person temp, *p;
		printf("이름 : ");
		scanf("%s", temp.name);
		p = bsearch(&temp, x, nx, sizeof(Person),
			(int(*)(const void *, const void *)) npcmp);

		if (p == NULL)
			puts("검색에 실패했습니다.");
		else {
			puts("검색 성공 !! 아래 요소를 찾았습니다.");
			printf("x[%d] : %s %dcm %dkg\n",
				(int)(p - x), p->name, p->height, p->weight);
		}

		printf("다시 검색할까요? (1) 예 / (0) 아니오 : ");
		scanf("%d", &retry);
	} while (retry == 1);

	return 0;
}
profile
mj
일단 할 수 있는걸 하자.
이전 포스트

[c] 알고리즘 - 배열과 구조체

다음 포스트

[c] 알고리즘 - 스택과 큐

0개의 댓글