[C언어 자료구조] 검색 알고리즘/선형 검색/이진 검색

검색 알고리즘이란?

: 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘

 

검색 알고리즘의 종류

1) 배열 검색

- 선형 검색

- 이진 검색

2) 선형 리스트 검색

3) 이진검색트리 검색

 

 

---

 

선형 검색? 

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

int search(const int a[], int n, int key) {
	int i = 0;
	while (1) {
		if (i == n) {
			return -1;
		}
		if (n == key)
		{
			return i;
		}
		i++;
	}
}

int main()
{
	int nx, ky, idx; // 배열의 요소 개수, 선형검색할 수, 검색한 요소의 위치
	int* x; // 배열
	printf("배열 요소의 개수 : ");
	scanf("%d", &nx); 
	x = calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}
	printf("검색값 : ");
	scanf("%d", &ky);
	idx = search(x, nx, ky);

}

검색 시간을 절감하기 위해서 '보초'라는 개념을 도입, 

배열의 마지막 요소에 key값을 넣어 while문에서 두번 종료조건(if문)을 탐색할 필요 없이 한번에 검색한다.

 

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()
{
	int i, nx, ky, idx; // 배열의 요소 개수, 선형검색할 수, 검색한 요소의 위치
	int* x; // 배열
	printf("배열 요소의 개수 : ");
	scanf("%d", &nx); 
	x = calloc(nx + 1, sizeof(int));

	for (i = 0; i < nx; i++)
	{
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}
	printf("검색값 : ");
	scanf("%d", &ky);
	idx = search(x, nx, ky);

}

보초를 이용한 선형 검색 알고리즘

 

 

---

이진 검색

: 요소가 오름차순 혹은 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 

  이미 정렬된 데이터에서 선형 검색 알고리즘보다 빠르게 검색할 수 있다. 

 

알고리즘이 탐색하는 바운더리의 시작을 pl, 끝을 pr, 그 가운데를 pc로 둔다. 

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

 

복잡도 

1) 선형 검색의 시간 복잡도

int search(int a[], int n, int key) {
	int i = 0;
	a[n] = key;
	while (1) {// n/2번 실행 O(n)
		if (a[i] == key) { // n/2번 실행 O(n)
			break;
		}
		i++;
	}
    return i == n ? -1 : i;
}

 전체 복잡도는 코드 내의 모든 시간 복잡도 중에서 가장 차원이 높은 쪽을 우선으로 두어 계산한다. 

 즉, 선형 검색의 시간 복잡도는 O(n)이다. 

 

2) 이진 검색의 시간 복잡도 

int bin_search(const int a[], int n, int key) {
	int pl = 0;
	int pr = n - 1;
	int pc;

	do {
		pc = (pl + pr) / 2; // O(logn)
		if (a[pc] == key) { // O(logn)
			return pc;
		}
		else if (a[pc] < key) {
			pl = pc + 1;
		}
		else {
			pr = pc - 1;
		}
	} while (pl <= pr);
	return -1;
}

이진 검색의 전체 복잡도는 O(log n)이 된다.