[자료구조] Binary Search 증명

 

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

 

이번 글은 다들 아는 이진탐색에 대한 증명을 배웠다. 사실 이진 탐색 알고리즘 자체는 직관적이고, 이해하기가 쉽다.

문제는 이 당연한 것을 증명하려고 따지다 보니까 머리가 터지는 기분(살아있음에 감사함을)이 들었다.

 

이런거 증명해서 어디다 쓰지? 라고 생각할수도 있지만, 이런건 학생 신분일때 한번은 해봐야 향후 나의 발전에 큰 도움이 될거라 믿어의심치 않는다.

 

Binary Search 의 증명

우선 이진탐색의 코드를 확인해 보자. 아 그리고 이진탐색은 항상 sorting되어있어야만 한다.

int BinarySearch(int a[], int n, int x){
	int left, right, middle;
	left = 0;
	right = n-1;
	
	while(left <= right){
		middle = (left+right)/2;
		if(x == a[middle])
			return middle;
		else if(x < a[middle])
			right = middle-1;
		else
			left = middle+1;
	}
	return -1;
}

 

이를 Invariant를 사용하여 증명해 보자. 아 Invariant가 무엇인지 부터 말하고 시작해야겟다.

Invariant: 단어 의미 그대로 불변하는 조건이다. 이 불변의 조건이 함수가 도는 동안 변화가 없으면 증명되는 것 이다.

 

이진탐색에서는 Invariant를 다음과 같이 정하자.

▶ Invariant: 만약 어떤 index i에 대해서 a[i] = x를 만족하는 i가 있다면, i는 left <= i <= right를 항상 성립한다.

- 알고리즘이 도는 동안 a[i] = x인 i가 없다면, 가정이 거짓으로 귀납적 논리에 의해 left <= i <= right이 성립 하든 말든 Invariant는 참이된다.

- 알고리즘이 도는 동안 a[i] = x인 i가 있다면, left <= i <= right이 항상 성립한다. 이는 Invariant이다.

 

▶ a[i] = x를 만족하는 i가 없다면 loop는 반드시 끝나고 -1을 반환한다.

▶ a[i] = x를 만족하는 i가 있다면 loop안에서 반드시 return된다.

	left = 0;
	right = n-1;

 

함수에서 위와 같은 코드가 있다. 즉 left는 배열의 시작 지점을 가리키고, right는 배열의 끝을 가리키고 있는 상황이다. 다음처럼 말이다.

1) 시작부분

x값이 어디 있든 처음 시작에서는 a[i] = x를 만족하는 i가 있으며, left <= i <= right를 만족하는 i가 존제한다. Invariant는 성립

 

2) while문 안에 들어갔을때

if(x == a[middle])
    return middle;

 

위의 식을 만족한다면, left와 right값은 변하지 않는다. left와 right가 변하지 않았다는 말은 while문에 들어오기 이전의 left와 right값이 그대로 이며, l과 r이 변하지 않은 상태에서 답이 나왔다는것은 a[i] = x를 만족하는 i가 (이전)left <= i <= (이전)right를 만족한다는 말이다. 즉, Invariant는 성립한다.

 

while문 안에는 다음과 같은 코드도 있다.

	else if(x < a[middle])
		right = middle-1;
	else
		left = middle+1;

 

X < a[middle] 를 만족 한다는 말은 => X < a[m+1], a[m+2] ... 을 만족한다는 말이다. 왜냐하면 이들은 sorting되어있기 때문이다. a[m+1], a[m+2] ... 중에는 X = a[i]를 만족하는 i값이 없다. 즉 중간부터 오른쪽 나머지를 버려도 Invariant는 성립한다.

이와 같은 논리로 else 부분의 X > a[middle] 부분도 Invariant는 성립한다.

 

3) -1을 반환하는 경우

-1을 반환하는 경우는 while문의 조건문에서 걸렸다는 말이다.

while(left <= right)

 

코드가 loop를 돌수록 right-left의 값 즉, 배열의 길이는 계속 줄어들게 된다. 결국 (left <= right)조건문이 깨지면 left <= i <= right를 만족하는 i값은 0개가 된다. 이경우도 Invariant는 성립한다.

어떤 i에 대해서 "a[i] = x를 만족하는 i가 있으며, left <= i <= right를 만족하는 i가 존제"가 성립해야 하는데, 이걸 만족하는 i가 없으니 -1을 반환하게 된다.

위에서 말하지 않았는가? 귀납적으로 a[i] = x를 만족하는 i가 없어도 Invariant는 성립한다고 말이다.

 

여기서 없을때 -1을 반환하니, 있을때는 값을 반환한다는 것 을 알 수 있다.

 

4) 증명 완료

함수가 작동하는 동안 Invariant는 계속 성립한다. 따라서 Binary Search는 타당하다.

 

 

 

Recursive Binary Search 의 증명

이번에는 재귀함수 버전의 이진탐색을 증명해보자. 이는 이전보다 훨 간단하다. 우선 코드를 확인해 보자.

int BinarySearch(int a[], int n, int x){
	int left, right, middle;
	left = 0;
	right = n-1;
	middle = (left+right)/2;
	
	if(n == 0) return -1;
        if(x == a[middle])
		return middle;
	else if(x < a[middle])
		return BinarySearch(a, middle, x);
	else{
		int rval;
		rval = BinarySearch(a+middle+1, n-(middle+1), x);
		if(rval == -1) return -1;
		else return rval + m + 1;
	}
}

 

내가 생각한 코드랑 조금 다른데 우선 ppt코드를 사용하겠다.

 

이를 수학적 귀납법으로 증명해 보자.

 

주장: 만약 어떤 i에 대해서 a[i] = x를 만족하는 i가 있다면 i를 return 한다.

 

(1) Base: P(1)이 참인지 확인해야 한다.

n=1인 경우 left는 0, right도 0이다. 1칸짜리 배열이다.

a[i] = x 라면 주장을 만족하는 i가 있으니(여기서는 배열이 한칸이니 index i는 0) 0을 반환할 것 이고, 만족하는 i가 없다면 가정이 틀리게 되니 의논할 여지 없이 그냥 참이다. 귀납적 논리에 의해 말이다.

 

(수업에서는 n=0인 경우를 보여주셧지만, n=1을 보이는 것이 원래 귀납적 증명이라 생각하여 나는 이를 보였다.)

 

(2) Step:

- case 1: a[m] = x를 만족하는 m가 있는경우 m을 반환하니 주장이 성립

- case 2: a[m] > x인 경우 a[m], a[m+1], ... a[n] 중에는 x와 같은 값이 없다. 따라서 a[i] = x를 만족하는 i는 0, 1, ... m-1중 하나이다. 귀납적으로 P(n-1)인 BinarySearch(a, m, x)가 정확하게 index를 return 한다고 가정하면, P(n)도 그 index를 return 하니까 성립

위의 그림을 보면 P(n-1)에서 index를 return 하고있다. 이는 P(n-1)을 포함하는 P(n)에서도 index i를 return함을 나타낸다.

- case 3: a[m] < x인 경우 case2와 유사

 

(3) Result: P(n)은 모든 자연수 n에 대해서 참이다.

 

Complexity

$T\left(n\right)\ =\ 1\ +\ T\left(\frac{n}{2}\right)$​

$\ \ \ \ \ \ \ \ \ \ =\ 1\ +\ 1\ +\ T\left(\frac{n}{4}\right)\ =\ \log n$​

$\ \ \ \ \ \ \ \ \ \ =\ O\left(\log n\right)$​

logN 시간안에 가능해 진다.