알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search)

[탐색 알고리즘 강좌]

데이터를 찾아보자!

이진 탐색(Binary Search)

---

이번에는 순차 탐색에 이어 이진 탐색(Binary Search)에 대해 알아보도록 할텐데, 이 '이진 탐색(Binary Search)'이 왜 이진인지 짐작이 가시나요? 이진 탐색이란 이름이 붙여진 이유는 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 줄어들기 때문에 그렇습니다. 이 탐색 알고리즘은 순차 탐색과는 달리 정렬된 배열을 전제로 합니다. 이진 탐색이 얼마나 빠른 알고리즘이냐면, 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있습니다. 놀랍죠?

  이진 탐색(Binary Search)의 탐색 과정

이제 한번, 위같은 정렬된 배열에서 이진 탐색(Binary Search) 알고리즘을 적용했을때 어떠한 과정을 거치는지 함께 살펴보도록 합시다. 위의 데이터 집합에서 8이란 데이터를 탐색하도록 하겠습니다. 자, 우선 첫번째 과정으로는 데이터 집합의 중앙 요소를 선택합니다.

두번째 과정으로는 중앙 요소의 값과 찾으려는 값을 서로 비교하게 되는데, 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 그리고 다시 이진 탐색(Binary Search)를 거치는 것입니다. 위의 경우에는 찾으려는 값인 8이 중앙값 7보다 크므로 중앙값 왼편에 있는 데이터와 비교할 필요가 없는거겠죠? 중앙 요소 오른편에서 중앙값을 다시 택합니다.

이제는 중앙값이 9이고, 다시 중앙값과 찾으려는 값을 다시 비교하게 됩니다. 찾으려는 값 8은 중앙값 9보다 작으므로 중앙값 왼편에서 데이터를 찾아야 하겠네요?

그럼 다시 왼편에서 중앙값을 선택합니다. 그렇게 되면, 남은 데이터 8이 중앙값으로 택해지게 되는데 찾으려는 데이터와 일치하므로 탐색을 끝마칩니다.

  이진 탐색(Binary Search)의 성능

이진 탐색의 과정을 봐보니 상당히 빨라보이죠? 이러한 이진 탐색 알고리즘의 성능은 어떨까요? 한번 비교가 이루어질때마다, 범위는 1/2로 줄어든다고 했었습니다. 위의 데이터 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어집니다.

위는 데이터 집합의 크기인 n을 2로 몇번을 나누어야 1이 되는지 말해주는 식으로, 위 수식을 정리하면 k=log2(n)이 되는 것입니다. 예를 들어 데이터 집합의 크기가 500만개라면 최대 23회, 1000만개라면 최대 24회의 탐색으로데이터를 찾아낼 수 있다는 것입니다.

  이진 탐색(Binary Search)의 구현

이렇게 빠른 이진 탐색 알고리즘을 한번 구현해보도록 할까요? 의외로 상당히 간단합니다.

int BinarySearch(int dataArr[], int size, int findData)
{
	int low = 0, high = size - 1, mid;

	// high가 low보다 작아진다면 찾으려는 데이터가 데이터 집합에 없다.
	while (low <= high)
	{
		// 중앙값은 low와 high를 더한 값을 2로 나누면 된다.
		mid = (low + high) / 2;
		// 만약 찾으려는 값이 중앙값보다 작다면 high를 mid - 1로 둔다.
		if (dataArr[mid] > findData) high = mid - 1;
		// 만약 찾으려는 값이 중앙값보다 크다면 low를 mid + 1로 둔다.
		else if (dataArr[mid] < findData) low = mid + 1;
		// 중앙값과 찾으려는 값이 일치하면 mid를 반환한다.
		else return mid;
	}
	// 데이터를 찾지 못하면 -1를 반환한다.
	return -1;
}

위 함수에서의 low는 탐색 범위에서 가장 왼쪽의 요소의 위치고, high는 탐색 범위에서 가장 오른쪽 요소의 위치를 나타냅니다. 그리고 mid는 그 탐색 범위의 중앙값을 나타냅니다. 각 줄에 대한 설명은 주석으로 달아놨으니 참고하시고, 위의 함수를 사용하여 어떠한 데이터 집합에서 특정 값을 찾는 예제를 보여드리도록 하겠습니다.

#include <stdio.h>

int BinarySearch(int dataArr[], int size, int findData)
{
	int low = 0, high = size - 1, mid;

	// high가 low보다 작아진다면 찾으려는 데이터가 데이터 집합에 없다.
	while (low <= high)
	{
		// 중앙값은 low와 high를 더한 값을 2로 나누면 된다.
		mid = (low + high) / 2;
		// 만약 찾으려는 값이 중앙값보다 작다면 high를 mid - 1로 둔다.
		if (dataArr[mid] > findData) high = mid - 1;
		// 만약 찾으려는 값이 중앙값보다 크다면 low를 mid + 1로 둔다.
		else if (dataArr[mid] < findData) low = mid + 1;
		// 중앙값과 찾으려는 값이 일치하면 mid를 반환한다.
		else return mid;
	}
	// 데이터를 찾지 못하면 -1를 반환한다.
	return -1;
}

int main()
{
	int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
	int length = sizeof dataArr / sizeof dataArr[0];
	int input, ret;

	while (true) {
		scanf("%d", &input);
		ret = BinarySearch(dataArr, length, input);
		if (ret != -1) printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1);
		else printf("데이터를 찾을 수 없습니다.\n");
	}
	return 0;
}

결과:

28
찾으려는 데이터는 21번째에 있습니다.
4
찾으려는 데이터는 4번째에 있습니다.
7
찾으려는 데이터는 7번째에 있습니다.
17
찾으려는 데이터는 16번째에 있습니다.

위의 예제를 살펴보시면, 무한 루프를 돌면서 사용자에게 입력을 요구합니다. 입력된 input 값에 따라, 이진 탐색 알고리즘을 통하여 찾으려는 데이터가 몇번째 요소인지 알려주는 예제라고 할 수 있습니다. (dataArr는 정렬할 필요 없이 이미 정렬된 데이터) 이 강좌를 읽고계시는 분들 중에서, 시간이 나시면 순차 탐색과 이진 탐색을 통하여 크기가 큰 데이터 집합을 다루어보시는 것도 좋을 듯 합니다. 이번 강좌에서는 이진 탐색을 간단하게 알아보았는데, 다음 강좌에서는 이진 탐색 트리(Binary Search Tree)를 다루어 보도록 하겠습니다.