Binary Search(이진탐색)와 증명

Binary Search

Binary Search는 가장 기본적인 탐색 알고리즘 중 하나다.

Sorting되어있는 배열의 중간값을 기준으로 크기를 비교하는 과정을 반복하여 search를 진행한다.

출처: 나무위키

만약 77을 찾는다고 하면 가장 먼저 1부터 100 사이의 중간인 middle인 50을 찍는다. 50 < 77 이므로 50이하는 볼 필요가 없기 때문에 버릴 수 있다.

따라서 다음 search에서는 51부터 100 사이의 반을 찍으면 된다.

위의 그림 3번째 search처럼 87 > 77이 되면 87 이후로는 볼 필요가 없기 때문에 버릴 수 있다.

따라서 다음 search에서는 75부터 86 사이의 반을 찍으면 된다.

반복적으로 반을 나눠 (n/2) 들어가기 때문에 $ O(logn) $ 시간에 search가 진행된다. n은 배열의 크기를 말한다.

 

Why $ O(logn) $ ?

내가 가장 처음 Big-O notation을 접했을 때 나는 왜 반복적으로 2로 나눠지면 $ O(logn) $이 되는지 직관적으로 이해가 되지 않았다. 그래서 간단하게 설명해보려고 한다.

n에서 반복적으로 2로 나눠지다보면 결국 1이 될 때 까지 나눠진다.

$$ N\div2\div2\div2 ... \div2 = 1 \to N*(\frac{1}{2})^{k} = 1$$

이를 반대로 생각해서 1에서 2를 몇번 곱해야 N이 되는지에 대해 나타낼 수 있다.

$$ 1*2*2*2 ... *2 = N \to 1*(2)^{k} = N$$

이 식에서 k는 결국 "몇번"에 해당하는 수식이 되고 k에 대해서 정리하면

$$ k = log_2N $$

즉, 1에 2를 logN번 곱하면 N이되고 반대로 N에서 2를 logN번 나누면 1이되는 것이다.

 

구현 - while을 이용한 구현

구현 - 재귀를 이용한 구현

증명(Proof)

대부분 알고리즘을 공부하는 사람이라면 알고리즘을 당연히 다 돌릴 수 있다. 하지만 왜 정확한가?에 대한 답을 낼 수 있는 사람은 많이 없다. 우리 학교 교수님이 강조하시는 점도 바로 이런점이다. 코드를 갖다 쓸 수는 있지만 왜 정확한지를 알아야 어떤게 되고 어떤게 되지 않는지, 더 나아가 많은 응용을 할 수 있게된다.

 

1. Proof by Invariant

알고리즘을 돌면서 변하지 않는 특성에 관한 것이다.

 

• Invariant: 만약 어떤 i에 대해서 a[i] = x라면 l<=i<=r이 항상 성립한다.

Invariant는 처음부터 성립하고 이 Invariant를 깰 코드는 없다.

• a[i] = x인 i가 없다면 loop은 반드시 끝나고 -1이 return된다.
• a[i] = x인 i가 있다면 loop안에서 index가 반드시 return된다.

2. Proof by Induction (수학적 귀납법)

알고리즘의 많은 부분을 수학적 귀납법을 통해서 증명할 수 있다. Binary Search또한 귀납법을 통해 증명할 수 있다.

 

• 증명하고 싶은 것: search라는 이진탐색 함수가 만약 어떤 i에 대해서 a[i]면 위 함수는 반드시 i를 return한다.
• Base: n = 0인 경우 즉, 배열의 크기가 0인 경우에는 위의 주장이 성립할 방법이 없으므로 -1을 return한다.
• Step - Case 1: a[m] = x인 경우 당연히 m을 return할 것이므로 위의 주장이 성립된다.
• Step - Case 2: a[m] > x인 경우 a[m],a[m+1],...a[n-1] 중에서는 x와 같은 값이 없고, a[i] == x인 i가 있다면 i는 0,1...m-1 중 하나일 것이다. 귀납적으로 search가 정확하다고 가정하면 search함수는 즉, 0부터 m-1 사이에서 위의 주장 'search라는 이진탐색 함수가 만약 어떤 i에 대해서 a[i]면 위 함수는 반드시 i를 return한다.'가 성립한다.
• Step - Case 3: a[m] < x인 경우 a[0],a[1],...a[m] 중에서는 x와 같은 값이 없고, a[i] == x인 i가 있다면 i는 m+1,1...n-1 중 하나일 것이다. 귀납적으로 search가 정확하다고 가정하면 search함수는 즉, m+1부터 n-1 사이에서 위의 주장 'search라는 이진탐색 함수가 만약 어떤 i에 대해서 a[i]면 위 함수는 반드시 i를 return한다.'가 성립한다.