CS/자료구조, 알고리즘

Binary Search 증명

matt1235 2022. 9. 4. 14:12

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

 

이분탐색 알고리즘, 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)

저작자표시 (새창열림)