Binary Search 증명

(본문은 학교 강의내용을 바탕으로 이해한 것을 정리한 글입니다. 틀린 부분이 있다면 지적 감사하겠습니다.)

 

이분탐색 알고리즘, Binary Search는 기초적인 탐색 알고리즘이다. 알고리즘을 공부하다 보면 다들 한번쯤은 들어봤을 만한 녀석이다.

나 또한 처음 알고리즘을 접하고 binary search를 접했을 때에는 직관적으로는 이해하기 어렵지는 않았다.

하지만 이녀석을 정확하게 증명한 적은 없었고, 깊이 생각해본 적도 없었던 것 같다.

 

굳이 왜..? 라는 생각이 들지도 모르지만 학부생일때 이런 경험을 많이 하는게 나중에 도움이 될 거라 믿어 포스팅을 작성하게 되었다.

Binary Search

// Binary Search
// a is sorted array, n: size, x: value to find
int search(int a[], int n, int x){
    int l, r, m;
    l=0; r=n-1;
    while(l<=r){
        m = (l+r)/2;
        if(a[m] == x) return m;
        else if (a[m] > x) r = m-1;
        else l=m+1;
    }

    return -1; // 비정상적인 종료 : 값을 못 찾은 경우
}

search 함수는 인자로 배열 a, 배열의 크기 n, 찾으려는 값 x를 받는다.

l,r 은 각각 탐색의 범위를 나타내는 값. 제일 왼쪽, 제일 오른쪽을 의미한다.

 

증명

▶ Invariant 를 통한 증명

Invariant 는 불변 조건 이라는 뜻이다. 이 불변 조건이 함수가 도는 동안 깨지지 않으면, 증명이 되는 것이다.

 

이진탐색 알고리즘에서 Invariant 를 다음과 같이 정의하자.

 

▶ Invariant : 만약 어떤 인덱스 i 에 대해 a[i]=x 를 만족하는 i 가 있다면, l<= i <= r 이 항상 성립한다.

 

우리가 흔히 명제를 논할 때 가정이 거짓인 경우 결과가 참이든 거짓이든 전체 명제는 참이라고 정의한다.

 

명제 P -> Q   (P 이면 Q 이다.)

P	Q	전체
T	T	T
T	F	F
F	T	T
F	F	T

위 경우 잘봐야 할 것은 가정인 P 가 거짓(F) 인 경우에는 Q 가 어떻든 전체 명제가 참(T)이라는 것이다.

 

수학에서는 이를 vacuous(의미없음) 라는 말로 정의하며 전체 명제는 vacuously true 이다.

즉 위 명제가 거짓인 경우에는 P가 참이고,Q가 거짓일 때 뿐이다.

 

이제 다시 invariant에 집중해보자.

 

• 알고리즘이 도는 동안 a[i] = x 인 i 가 없다면, 가정이 이미 거짓이므로 귀납적 논리에 의해 Invariant 는 참이된다.
• 알고리즘이 도는 동안 a[i] = x 인 i 가 있다면, l <= i <= r 이 항상 성립한다. (우리가 이를 Invariant 라 정했다.)

 

1) 시작

처음 시작에서 a[i] = x 를 만족하는 i 값이 있다면, l <= i <=r 을 만족하는 i 가 존재한다. => Invariant 성립.

 

2) while 문에 들어갔을 때

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

위 식을 만족하면, m 값을 리턴한다. 이 때 l 과 r 값은 처음과 그대로이고 그 상태에서 답이 나왔다는 얘기는

a[i] = x 를 만족하는 i 가 l<= i <= r을 만족한다는 의미이다. 따라서 Invariant 는 성립한다.

 

else if (a[m] > x) r = m-1;
else l=m+1;

x < a[m] 를 만족한다는 것은

x < a[m+1] < a[m+2] <..... 또한 만족한다는 말이다. a는 정렬된 배열이므로.

따라서 i 는 인덱스이므로 i < m 이다. m 부터 오른쪽 끝까지 나머지들을 버려도 Invariant 는 성립한다.

 

같은 논리로, x > a[m] 일 때도 m 부터 왼쪽을 전부 버려도 Invariant 는 성립한다.

 

 

3) -1 을 리턴

-1을 반환하는 경우 while 문의 조건인 l <= r 에 걸려 빠져나왔다는 얘기다.

while(l <= r)

배열의 길이는 계속 줄어들게 되면서 결국 길이가 0 이 되어버린다. Invariant 의 가정 l<= i <= r 이 거짓이 되므로 vacuously true, 

Invariant 는 깨지지 않는다.

 

 

1, 2, 3 의 상황에서 Invariant 는 깨지지 않는다.

즉 함수가 작동하는 동안 Invariant 는 항상 성립하므로 search 함수는 참이다.

 

 

 

이번에는 재귀로 짜여진 이분탐색 코드를 보자.

Recursive Binary Search

int search(int a[], int n, int x){
    int m;
    if(n<=0) return -1;
    m = n/2;
    if(a[m] == x) return m;
    else if (a[m]>x) return search(a, m, x);
    else{
        return search(a+m+1, n-m-1, x);
    }
}

 

증명

귀납법으로 증명을 해보자.

 

▶ 주장

만약 어떤 i 에 대해 a[i]=x 라면 위 함수는 i 를 리턴한다.

 

▶ Base

n=1 인 경우 P(1) 은 길이가 1인 배열로, 원소도 하나뿐이다.

a[i]=x 인 i 가 있다면 i 를 리턴할 것이고, 만족하는 i 가 없다면 가정이 틀리게 된다. 따라서 참이다.

 

▶ Step

Case 1:  a[m] = x 인 경우 m 을 리턴. 주장이 성립한다.

 

Case 2: a[m] > x 인 경우 a[m], a[m+1], ..... , a[n] 중에는 x가 없다.

따라서 a[i] = x 인 경우가 있다면, i 는 0, 1, ... m-1 중 하나이다. 귀납적으로 search(a, m-1, x) 가 정확하다고 가정하면  

즉 search(a, m-1, x)가 어떤 i 에 대하여 a[i]=x 일때 i 를 리턴한다면 search(a, n, x)도 그 값을 똑같이 리턴함.

귀납적으로 P(n-1) 인 search(a, m, x) 가 i를 리턴한다고 하면 P(n) 도 그 i 를 리턴하니까 성립.

 

Case 3: a[m] < x 인 경우

case 2 와 유사. 귀납적으로 성립

 

▶ Conclusion

따라서 P(n)은 모든 자연수 n 에 대해서 참이다.

 

 

시간복잡도 (Complexity)

T(n) = 1 + T(n/2)

        = 1 + 1 + T(n/4)

        = O(logN)