이진탐색 알고리즘

본 포스트는 윤성우님의 열혈 자료구조를 출처로 작성된 글입니다.
필자의 복습을 위한 요약 주 목적이며 따라서 생략된 부분이 많을 수 있습니다. 오타나 잘못된 내용이 발견될 시 답글로 남겨주시면 감사하겠습니다.
본 포스팅은 함수의 재귀적 호출에 대한 이해가 필요합니다.

이진탐색(Binary Search) 알고리즘 구현과 분석

이하의 이진탐색은 배열을 기반으로 하고 있습니다.

이진탐색 알고리즘은 주어진 배열내에서 탐색 대상을 찾을때, 탐색 영역을 반절씩 줄여가며 탐색하는 알고리즘이다.

다음과 같은 과정으로 이뤄진다.

1. 주어진 배열내의 가운데 인덱스를 결정한 후, 탐색 대상과 가운데 인덱스의 값과의 비교한다.
2. 비교의 결과를 통해 주어진 탐색 대상을 반절로 줄인다.
3. 1과 2를 반복하며 탐색 대상을 찾는다.

이진탐색은 주어진 데이터가 배열 내에서 어떤 식으로든 정렬되어 있음을 제약조건으로 갖고 있다.

다음의 코드가 C로 구현한 이진탐색 알고리즘이다.

int Bsearch(int* arr, int min, int max, int target)
{
	int mid = (min + max) / 2;
	if (min > max) //재귀 탈출 조건
	{
		return printf("Bserach failed!");
	}
	else
	{
		if (arr[mid] == target)
		{
			return printf("the target index is %d\n", mid);
		}
		else
			if (arr[mid] < target)
			{
				Bsearch(arr, mid + 1, max, target); //재귀호출
			}
			else
				Bsearch(arr, min, mid -1, target); //재귀호출
	}	
}

코드 분석은 다음과 같다.

1. arr[(min + max) %2 가 mid를 결정한다.

2. 이후 arr[mid]의 결과와 target의 대소비교를 통해 다음 루틴의 탐색 영역을 결정한다.(어느쪽을 선택하든 절반씩 줄어든다.)

   이때 다음 루틴은 재귀적으로 이루어진다.
   각 재귀호출에서 인자에 +1, -1등의 연산이 있는 건, 각 재귀호출에서 우리의 의도(배열내에 탐색대상이 없을때를 판단)에 맞게 탈출조건을 만족하도록 변화를 주기 위함이다.

전체 과정에서 탐색 키와 탐색 데이터는 구별되지 않았다는 점을 유의하자..

이진탐색 알고리즘의 탈출조건

위의 주석에서 //재귀 탈출 조건이란 무엇인가?
이는 지금 수준에선, 타겟이 배열내에 없는 경우 어떻게 이를 판단할지에 대한 조건이다.

재귀호출 과정에서 min은 1씩 더해지고, max는 1씩 줄어든다. 그럼 타겟이 배열내에 없는 경우를 판단하는 조건으로
min == max을 작성하면 어떨까?

안된다. arr[min] == arr[max] == target인 경우도 있을 수 있다. 기껏 끝까지 찾아낸 탐색 대상을 포기하는 꼴이다.

따라서 우리는 탈출조건을 min과 max가 역전되는 조건으로 결정해야 한다.

위의 내용은 재귀적 호출에 대한 이해가 부족하면 이해되지 않을 수 있다. 재귀호출에 익숙해지고나서 하나씩 코드를 디버깅해보며 메모리를 살펴보거나, 호출스택을 그려보면 이해에 도움이 된다.

이때 궁금해서 이진탐색의 각 인덱스별 연산횟수를 계산해봤다.

idx
0 1 2 3 4 5 6 7 8 9
count
3 2 3 4 1 3 4 2 3 4

의 결과가 나왔다. 생각보다 대칭성도 없고.. 규칙도 잘 모르겠다. 혹시 이 점에 관해 아시는 분이 있다면 댓글로 남겨주시면 정말정말정말 감사드리겠읍니다. 아님 인덱스를 더 많이 세보겠읍니다.. 궁금합니다..

이진탐색의 시간복잡도

이진탐색의 핵심 연산자는 == 비교연산자이다.
다른 연산들은 모두 비교연산에 의존적이다.

이진탐색의 최악의 경우, 즉 타겟이 배열내에 없을때는

개의 원소가 남을때까지 총 $k$번 탐색을 진행하고, 마지막으로 남은 $1$개의 원소를 탐색하므로 총 $k+1$번 탐색을 진행한다.

$n$에 $1 \over 2$을 $k$번 곱하면 $1$이 되므로,

의 식이 성립하고 이를 다시 $k$에 대한 $n$의 식으로 바꾸면

이다.

$T(n) = k+1$이었으므로(마지막 멤버에 대한 탐색 1회), 엄밀히 $T(n) = log_2n+1$이지만, $n$이 매우 커지면 $+1$정도는 큰 의미가 없다. 따라서 $+1$은 고려하지 않는다.

이진탐색 알고리즘의 빅오는 다음과 같다.