Binary search

 

 

Binary search (이진 탐색)

출처 : https://www.geeksforgeeks.org/binary-search-in-java/

#include <stdio.h>

int binary_search(int a[], int n, int x){
    int l = 0;
    int r = n-1;
    while(l <= r){
        int m = l + (r - l) / 2; 
        if(a[m] == x) return m; // 찾는 수와 같은 경우 ...(2)
        else if (a[m] > x) r = m-1; // 찾는 수가 더 작은 경우
        else l = m+1; // 찾는 수가 더 큰 경우
    }
    return -1; // ... (1)
}

int main(){
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    printf("%d\n", binary_search(a, 10, 3));
    return 0;
}

index가 있으면 index를 return 하고, 없으면 -1을 return 

l은 왼쪽 끝의 index, r은 오른쪽 끝의 인덱스로 시작하여 범위에 따라 절반씩 줄어든다. 

Proof of invariant

* invariant : 어떠한 변하지 않는 성질, 깰 수 있는 코드가 없음을 증명해야함, 이가 만족되면 코드가 지정한 역할을 수행함

invariant : 어떤 i에 대하여 a[i]  = x 라면, l ≤ i ≤ r 이다 (sorting이 되었다는 가정)

p : 어떤 i에 대하여 a[i] = x라면

q : l ≤ i ≤ r 이다

if ) 어떤 i에 대하여 a[i] = x (p)가 참이라면 q가 참이면 참이된다.

if ) 어떤 i에 대하여 a[i] = x (p)가 거짓이라면 q의 결과와 상관 없이 참이된다.

∴ p가 참이라는 가정 하에 q가 참이라는 것을 보이면 됨 > q를 깰 수 있는 코드가 없음을 보이면 됨

[코드 분석]

 - 어떤 i에 대하여 a[i] = x 존재할 때

1 ) 초기 상태 

l = 0, r = n-1이므로,  l ≤ i ≤ r 을 만족하는 i가 존재함 ∴ invariant가 성립

2 ) 반복(while) 문

l ≤ r이 while문의 조건이다. r은 줄어들고, l은 증가하지만 반복문 조건에 의해 한없이 줄어들 수 없으므로 무조건 종료되는 코드임

if(a[m] == x) return m; // 찾는 수와 같은 경우 ...(2)
else if (a[m] > x) r = m-1; // 찾는 수가 더 작은 경우
else l = m+1; // 찾는 수가 더 큰 경우

a[m] == x : l, r이 변하지 않음 → l ≤ i ≤ r 을 만족하는 i가 존재함 ∴ invariant가 성립

a[m] > x :

이 배열은 sorting 되어있으므로 x < a[m], a[m+1], a[m+2] ... a[n-1]이므로 이 중에는 a[i] = x인 i가 없다.

중간부터 오른쪽을 버려도 ( r = m-1로 설정하는 효과와 같음 ) l ≤ i ≤ r 을 만족하는 i가 존재함 ∴ invariant가 성립

a[m] < x (else) :

이 배열은 sorting 되어있으므로  a[1], a[2], ... a[m-1], a[m] < x 이므로 이 중에는 a[i] = x인 i가 없다.

중간부터 왼쪽을 버려도 ( l = m + 1로 설정하는 효과와 같음 ) l ≤ i ≤ r 을 만족하는 i가 존재함 ∴ invariant가 성립

 

- 어떤 i에 대하여 a[i] = x가 없을 때 : while문의 조건을 벗어나면서 return -1을 하게 됨

 

[결론]

함수가 작동하는 동안 invariant는 항상 성립한다.

• a[i] = x를 만족하는 i가 없다면, loop는 반드시 끝나고 -1을 return 한다 ... (1)
• a[i] = x를 만족하는 i가 있다면, loop 안에서 반드시 return 한다 ...(2)

Recursive Binary search 

#include <stdio.h>

int recursive_binary_search(int a[], int n, int x){
    int l = 0;
    int r = n-1;
    while(l <= r){
        int m = l + (r - l) / 2; 
        if(a[m] == x) return m; // 찾는 수와 같은 경우
        else if (a[m] > x) return recursive_binary_search(a, m, x);// 찾는 수가 더 작은 경우
        else { // 찾는 수가 더 큰 경우
            int val;
            val = recursive_binary_search(a+m+1, n-(m+1), x);
            if(val == -1) return -1;
            else return val + m + 1;
        } 
    }
    return -1;
}

int main(){
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    printf("%d\n", recursive_binary_search(a, 10, 9));
    return 0;
}

 

[ 재귀함수와 수학적 귀납법의 연관성 ]

재귀함수 : 결과 (정답)을 return해주는 것이라고 생각(믿음) - P

재귀함수일 때에는 return 값에 초점을 맞춰 invariant를 잡아보자

proof of induction

* 코드의 모든 줄이 증명에 등장해야함

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

그 외 전제 : 배열이 sorting되어있음, 같은 값이 없음, 값이 없을 때는 -1을 리턴한다.

 

proof ) 

(1) Base : n = 0인 경우, 배열에 값이 없기 때문에 "어떤 i에 대해서 a[i] = x"가 성립할 수 없으므로 -1을 리턴함 (while 조건식 어긋남)

→ n = 1을 보여도 무관하다

 

(2) Step :

Case 1 : a[m] = x 인 경우 m을 리턴한다 ∴invariant 성립

 

Case 2 : a[m] > x인 경우, x는 존재한다면 왼쪽에 존재해야함

a[m], a[m+1], ... a[n-1] 중에서는 x와 같은 값이 없다. (sorting 되어있기 때문)

따라서 a[i] = x인 경우 x가 있다면 0, 1, m-1 중 하나이다.

귀납적으로 recursive_binary_search(a,m,x) (→P(n-1))가 정확하다고 가정한다면 전체(→P(n))에서도 성립한다.

∴invariant 성립

 

Case 3 : a[m] < x 인 경우 - x가 존재한다면 오른쪽에 존재해야함

a[0], a[1], ... a[m] 중에서는 x와 같은 값이 없다 (sorting 되어있기 때문)

따라서 a[i] = x인 경우 x가 있다면, m + 1, m + 2, ... n-1 중 하나이다.

즉 배열의 오른쪽 값만 봐야하므로, 앞으로 검색할 배열의 첫번째 시작은 a+m+1, 크기는 n-(m+1), 찾는 값은 x가 된다

귀납적으로 recursive_binary_search(a+m+1, n-(m+1), x)(→P(n-1))가 정확하다고 가정한다면

값이 없을 때에는 -1을 리턴하고,

값이 있을 때에는 a+m+1을 기준으로 시작한 인덱스 값을 리턴하므로, 전체에서 리턴값의 m+1을 해준다면 정확한 인덱스 값을 리턴한다

∴invariant 성립

 

(3) Result : invariant는 모든 자연수 n에 대해 참이다.

 

The complexity (시간)

\( T(n) = 1 + T(n/2) = 1 + 1 + T(n/4) ... = logn\)

\(T(n) = O(log n)\)

 

log n이란?

\(k = logn  \Leftrightarrow  2^{k} = n\)

• n을 2로 log n번 나누면 1에 가까워진다
• 1이 될 때까지 2로 나눌 수 있는 횟수
• 2를 log n 번 곱하면 n이 됨
• log n <<< n