Binary search
Binary search (이진 탐색)
#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