이진 탐색(Binary Search) 알고리즘과 시간 복잡도 분석

#include <stdio.h>

int BSearch(int ar[], int len, int target) {
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;
		if (target == ar[mid]) {
			return mid;
		}
		else // 타겟이 아니라면 반으로 줄입시다.
		{
			if (target < ar[mid])
				last = mid - 1; // 1을 이동 안시켜주면 찾고자 하는 값이 없을 때 무한 루프에 빠집니다.
			else
				first = mid + 1; // 역시나 1을 이동 안하면 찾고자 하는 값이 없을 때 무한 루프에 빠집니다.
		}
	}
	return -1; // 찾지 못했을 땐 -1
}

int main(void) {
	int idx;
	int arr[] = { 1, 3, 5, 7, 9 };

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);

	return 0;
}

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘입니다. 그렇기에 first < last인 상황에서는 물론이거니와 first == last인 상황에서도 계속되어야 합니다. 즉, first가 last보다 큰 경우 탐색이 종료되어야 합니다. (탐색 실패)

 

그렇다면 왜 mid에서 -1 / +1을 했을 까요?? 이렇게 하지 않으면 mid에 저장된 인덱스 값의 배열요소도 새로운 탐색의 범위에 포함됩니다. 근데 이미 탐색의 대상이 된 부분을 또 할 필요가 없습니다.

 

또한, 제일 중요한 부분은 탐색의 대상이 배열에 존재하지 않는 경우에 존재합니다.

 

first에 저장된 값이 last보다 커져서 반복문을 탈출 할 수 있어야 하는데, 이렇게 해버리면 결코 first에 저장된 값은 last보다 커질 수 없습니다.

 

왜냐면 first <= mid <= last의 식을 만족하는 알고리즘인데 mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부인데, first에 저장된 값이 last보다 커질 방법이 없기 때문입니다.

---

시간 복잡도 계산하기

이진 탐색 알고리즘 역시 순차 탐색 알고리즘과 마찬가지로 == 연산을 연산횟수를 대표하는 연산으로 볼 수 있습니다.

그렇다면 "데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 될까요?"

 

이진 탐색 트리는 아래와 같은 연산을 거칩니다.

• n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행
• 데이터가 1개 남았을 때, 이 때 마지막으로 비교연산 1회 진행

그래서 최악의 경우에 대한 시간 복잡도는 T(n) = k + 1과 같습니다. 그럼 k는 무엇일까요?

 

k는 아래 식으로 표현할 수 있습니다.

n * (1/2)^k = 1 => logn = k => T(n) = logn

 

근데 최악의 경우의 비교연산 횟수는 k + 1입니다. 그럼 왜 여기서 +1을 계산 안 할까요? n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않습니다.

 

그래서 무시가 가능합니다.

---

재귀 함수로 구현하는 이진 탐색

#include <stdio.h>

int BSearchRec(int first, int last, int ar[], int target) {
	if (first > last) {
		return -1;
	}
	
	int mid;
	mid = (first + last) / 2;
	
	if (ar[mid] == target) {
		return mid;
	}
	else if (target < ar[mid])
		return BSearchRec(first, mid - 1, ar, target);
	else
		return BSearchRec(mid + 1, last, ar, target);
}

int main(void) {
	int index;
	int arr[] = { 1, 3, 5, 7, 9 };

	index = BSearchRec(0, sizeof(arr) / sizeof(int), arr, 5);
	printf("%d \n", index);

	index = BSearchRec(0, sizeof(arr) / sizeof(int), arr, 8);
	printf("%d \n", index);
}

---

이상 이진 탐색(Binary Search) 알고리즘과 시간 복잡도 분석였습니다. ^_^