03. 검색

03-1. 검색 알고리즘

검색과 키

검색

• 배열 검색
  - 선형 검색 : 무작위로 늘어 놓은 데이터 모임에서의 검색
  - 이진 검색 : 일정한 규칙으로 늘어 놓은 데이터 모임에서의 아주 빠른 검색
  - 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서의 아주 빠른 검색
• 선형 리스트 검색
• 이진검색트리 검색

03-2. 선형 검색

선형 검색

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

배열 검색의 종료 조건(판단 횟수 : 평균 n/2 회)

• 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(판단 횟수 : n+1 회)
• 검색할 값과 같은 요소를 발견한 경우(판단 횟수 : n회)

/*--- 요소의 개수 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; 			/* 검색 실패 */
}

보초법

종료 조건을 검사하는 비용을 반(50%)으로 줄이는 방법

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;
}

03-3. 이진 검색

이진 검색

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

1. a[pc] < key 일 때

a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pc+1] ~ a[pr]로 좁혀짐
pl의 값을 pc+1로 업데이트

2. a[pc] > key 일 때

a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pl] ~ a[pc-1]로 좁혀짐
pr의 값을 pc-1로 업데이트

이진 검색 알고리즘의 종료 조건

• a[pc]와 key가 일치하는 경우
• 검색 범위가 더 이상 없는 경우

/*--- 요소의 개수 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;	 		/* 검색 실패 */
}

복잡도(complexity)

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

• 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
• 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

선형 검색의 시간 복잡도

int search(const int a[], int n, int key)
{
/*l1*/	int i = 0;
/*l2*/	while (i < n) {
/*l3*/		if (a[i] == key)
/*l4*/			return i; 		/* 검색 성공 */
/*l5*/		i++;
      	}
/*l6*/	return -1;				/* 검색 실패 */
}

l1 : 변수 i에 0을 대입하는 횟수가 1회이므로 O(1)
l4, l6 : 함수에서 값을 반환하는 시행이 한 번이므로 O(1)
l2 : 배열의 맨 끝에 도달했는지 판단 - 처음부터 도달하면 1, 마지막에 도달하면 n이므로 평균 실행 횟수는 n/2
l3 : 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지 판단 - l2와 같은 이유로 평균 실행 횟수는 n/2
따라서 시간 복잡도는 O(n)

🔴 이진 검색의 시간 복잡도

int bin_search(const int a[], int n, int key)
{
/*l1*/	int pl = 0; 				/* 검색 범위 맨 앞의 인덱스 */
/*l2*/	int pr = n - 1; 			/* 검색 범위 맨 끝의 인덱스 */

	do {
/*l3*/		int pc = (pl + pr) / 2;		/* 중앙 요소의 인덱스 */
/*l4*/		if (a[pc] == key) 		
/*l5*/			return pc;		/* 검색 성공 */
/*l6*/		else if (a[pc] < key)
/*l7*/			pl = pc + 1;		/* 검색 범위를 뒤쪽 반으로 줄임 */
/*l8*/		else
/*l9*/			pr = pc - 1;		/* 검색 범위를 앞쪽 반으로 줄임 */
/*l10*/	} while (pl <= pr);

/*l11*/	return -1;	 				/* 검색 실패 */
}

단계	실행 횟수	복잡도	비고
l1	1	O(1)	대입
l2	1	O(1)	대입
l3	log n	O(log n)	급격->완만 감소
l4	log n	O(log n)
l5	1	O(1)	반환
l6	log n	O(log n)
l7	log n	O(log n)
l8	log n	O(log n)
l9	log n	O(log n)
l10	log n	O(log n)
l12	1	O(1)	반환

따라서 시간 복잡도는 O(log n)
* 참고 : [알고리즘] 3. 시간복잡도(BigO) 기초 - 센치한개발자