[Data Structure] 이분 탐색(Binary Search)

● 순차 탐색 알고리즘과 시간 복잡도

탐색이란, 수많은 데이터 속에서 내가 원하는 데이터를 찾는 과정을 말합니다.

예를 들어 1부터 100까지의 숫자가 적힌 배열에서 31을 찾는 것은 탐색을 거쳐야 할 것입니다.

 

그중 순차 탐색이란, 처음부터 끝까지 찾고자 하는 데이터를 탐색하는 것을 말합니다. 

순차 탐색 알고리즘을 구현하면 다음과 같습니다.

int LSearch(int arr[], int len, int tar) {

	for (int i = 0; i < len; i++) {
		if (arr[i] == tar) {
			return i;
		}
	}
	return -1;
}

int main(void) {

	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int length = sizeof(arr);
	int target = 5;

	int index;

	index = LSearch(arr, length, target);

	printf("%d", index);
}

위 코드를 run 해본다면 index는 4가 나올 것입니다. 4가 나오는 이유라 함은 배열의 0번째 인덱스인 1부터 탐색을 수행했을 때, 5는 4번째 인덱스에 있기 때문입니다. 

그렇다면 순차 탐색 알고리즘을 사용했을 때의 최고와 최악의 경우를 살펴보면 당연히 최고는 첫 인덱스가 타깃인 경우이고, 최악은 뒤쪽에 타깃이 있는 경우일 것입니다. 혹은 아예 타깃이 배열 안에 없는 경우가 되겠네요.

그러나 보통은 처음이나 끝이 아닌 중간 어딘가에 있는 데이터를 찾기를 원하기 때문에 이를 Average case로 지정합니다. 

Average case의 경우에는 객관적인 평가가 쉽지 않다는 단점이 있습니다. 배열의 길이나 상대적 위치에 따라서도 평가의 차이가 심하기 때문입니다. 

 

가정을 하나 해보겠습니다.

1. 탐색 대상이 배열에 존재하지 않을 확률 50%

2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률 동일

 

위와 같은 가정이 있을 때, 탐색 대상이 존재하지 않는 경우의 연산 횟수를 n이라고 하면 가정 2에 의해 탐색 대상이 존재하는 경우의 연산 횟수는 n/2가 됩니다.

그렇다면 비교 연산을 식으로 표현한다면 다음과 같습니다.

 

● 이분 탐색 알고리즘

이분 탐색의 주요 원리는 전체 데이터를 절반으로 나눈 뒤 절반에 해당하는 값에 대하여 타겟의 대소를 비교해 점점 탐색 범위를 줄여나가는 것입니다. 

코드로 구현하면 다음과 같습니다.

int BSerach(int arr[], int len, int tar) {
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;

		if (tar == arr[mid]) {
			return mid;
		}
		else {
			if (tar < arr[mid]) {
				last = mid - 1;
			}
			else {
				first = mid + 1;
			}
		}
	}
	return -1;
}

first와 last는 초기의 처음과 끝 인덱스 번호를 의미합니다. 그러나 mid를 반복문 밖에서 초가화하지 않은 이유는 이후에 first와 last가 지속적으로 변함에 따라 mid도 이에 맞춰 같이 변해야 하기 때문입니다.

반복문에서의 else문만 보면 만약 타겟이 mid보다 작다면 즉, 배열을 쭉 일자로 펼쳤을 때 더 왼쪽에 있다면 last를 mid보다 1 작게 두어야 합니다. 반대일 경우에는 first를 mid보다 1 크게 합니다.

위와 같이 하는 이유는 비교 횟수를 줄이기 위해서입니다. 만약 타깃이 mid가 아니라면 경우의 수는 mid보다 작거나 크거나 둘 중 하나일 것입니다. 그렇게 되면 예를 들어 mid보다 타깃이 작다면 아예 mid보다 큰 영역은 볼 필요가 없다는 것입니다. 그래서 이분 탐색은 순차적 탐색보다 시간을 확연하게 줄일 수 있는 방법입니다. 

 

이를 직접적인 그림으로 보면 다음과 같습니다.

 

여기서 의문이 생길 수 있습니다. 배열은 숫자를 넣기 나름인데 만약 크기 순서대로 정렬되어 있지 않다면 이분 탐색은 제대로 안되지 않느냐입니다. 당연합니다. 그래서 이분 탐색은 배열이 크기 순으로 정렬되어 있는 것을 조건으로 합니다. 

 

다른 의문의 경우에는 만약 배열의 인덱스가 짝수개면 mid가 어떻게 되는지 입니다. 결론만 말하자면 정중앙에서 0.5 작은 값을 택합니다. 배열의 인수가 1부터 10까지 라면 처음에는 5에 해당하는 4번 인덱스가 mid가 되는 것입니다.

 

위의 코드를 봤을 때 시간복잡도에 영향을 주는 요인이라고 하면 ==연산자가 있습니다. 왜냐하면 ==이 부정인 횟수 +1만큼 비교를 진행하기 때문입니다. 그래서 ==연산자가 시간복잡도를 결정한다고 할 수 있습니다.

 

그림에서 볼 수 있듯 경우를 일반화해서 생각한다면 위쪽이 될 것이고 worst case 즉, 타겟이 하필 가장 마지막 탐색 때 찾아진다면 +1을 해줍니다.

 

○ 빅 오 (Big O)

빅 오는 실제로 영향을 끼치는 부분을 의미합니다. 예를 들어, n^2 + n + 1이라는 식이 있다고 할 때, 1은 n에 비해 영향력이 적기 때문에 생략해 줍니다. 대신 생략된 값은 정확한 값이 아니라 근삿값이 됩니다. 그다음으로는 n 또한 생략할 수 있습니다. 이유는 n이 커질수록 n^2가 기하급수적으로 커지기 때문에 n 또한 무의미해지기 때문입니다. 

그래서 위 식을 최종적으로 나타내면 O(n^2)이라고 적을 수 있습니다.

 

이렇게 빅 오의 경우에는 만약 T(n)이 다항식이라면 최고차항의 차수가 빅 오가 됩니다.

빅 오를 define 한다면 다음으로 정리할 수 있습니다.

앞선 순차 탐색과 이분 탐색 모두 빅 오로 나타낼 수 있기 때문에 먼저 빅 오의 그래프들을 보면 다음과 같습니다.

위 그래프의 대소 관계를 바탕으로 순차 탐색과 이분 탐색의 빅 오를 비교하여 어떤 것이 더 효율적인지를 따졌을 때 후자가 더 효율적임을 증명하고 있습니다.

---

지금까지 이분 탐색을 순차 탐색과 비교해보며 알아보았고 이들을 빅 오로 표현하여 효율성을 따지는 작업을 해봤습니다.