[C언어] 탐색 알고리즘 (순차탐색, 이진탐색)

알고리즘이란? 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 한마디로 문제 해결방법을 공식화한 형태라고 할 수 있다. 

 

탐색 알고리즘에 대해 알아보자. 

 

1. 순차탐색

배열의 순서대로 확인하면서 값을 찾는 방법이다. 매우 단순한 탐색방법이며 웬만하면 이 방법을 사용한다고 한다. 그러나 찾는 값이 맨 끝에 있다면 모든 값을 다 비교해야 하기 때문에 비효율적이다. 

 

#include <stdio.h>

int main(void)
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int key = 8;
	int index;

	for (int i = 0; i < 10; i++) {
		if (key == arr[i]) index = i;
	}

	printf("%d는 arr[%d]안에 있습니다.\n", key, index);

	return 0;
}

 

참고 유튜브 링크: https://www.youtube.com/watch?v=eMzjlYIjRk4

2. 이진탐색

순차탐색의 비효율적인 점을 보완한 탐색방법이다. 이진탐색은 배열이 오름차순이나 내림차순으로 정렬되어 있다고 가정한 상태에서 실행된다. 

 

탐색과정을 설명하자면,

1. 검색 범위에서 중간에 위치한 값을 찾는다. 이를 중간값이라 한다.

2. 찾는 값과 중간값을 비교한다. 두 값이 다르면 범위를 반으로 줄인다. 

찾는 값이 중간값보다 크다면 중간값의 다음 값부터 마지막 값까지로 범위를 줄인다. (중간값+1 ~ 마지막 값)

찾는 값이 중간값보다 작다면 중간값 바로 이전 값부터 처음 값까지로 범위를 줄인다. (처음 값 ~ 중간값-1)

3. 위 과정을 반복하여 계속 범위를 줄여 나간다.

4. 값을 찾으면 탐색 끝!

 

#include <stdio.h>

int main(void)
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int key = 8; // 찾는값
	int mid_i; // 중간값 인덱스
	int start_i = 0, end_i = 9; // 시작값 인덱스, 끝값 인덱스
	while (1) {
		mid_i = (start_i + end_i) / 2;
		if (arr[mid_i] > key) {
			end_i = mid_i - 1;
		}
		else if (arr[mid_i] < key) {
			start_i = mid_i + 1;
		}
		else {
			break;
		}
	}
	printf("%d는 arr[%d]안에 있습니다.\n", key, mid_i);

	return 0;
}

 

참고 유튜브 링크: https://www.youtube.com/watch?v=IfIuG95RH0o