[ 알고리즘 ] Binary Search, Recursive Binary Search

1. Binary Search

 

Binary Search

 

이진탐색트리 코드이다.

l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다.

 

기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다.

 

처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다.

탐색은 l과 r이 만나면 종료된다.

 

m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다.

1) n=2

l=0, r=1, m=0 으로 모두 탐색 가능하고

2) n-3

l=0, r=2, m=1 으로 모두 탐색 가능하다

 

a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다.

왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 탐색을 위해서는 l을 m 바로 다음 인덱스로 옮겨준다.

 

증명 (Proof by Invariant)

invariant 은 최초에 성립하고, invariant가 깨질 수 있는 코드가 없다는 것을 증명하면 된다.

 

invariant : a[i] = x 인 i가 있다면 l<=i<=r 에 있다.

-> l과 r이 변할때 이 조건은 변하지 않는다는 의미

바뀔 수 있는 포인트는 r이 변하거나 l이 변하는 부분인데, 이 둘이 변해도 x는 그 안에 있다는 것을 보장할 수 있다.

 

a[i] = x 가 없다면 루프는 반드시 끝나고 -1이 리턴된다.

a[i] = x 가 있다면 반드시 찾아서 리턴된다.

 

 

2. Recursive Binary Search

 

Recursive Binary Search

 

이는 이진탐색트리를 재귀로 표현한 것이다.

n이 0이면 탐색할 것이 없으므로 -1를 리턴하며 종료된다.

 값을 찾으면 인덱스 번호를 리턴하며 종료한다.

 

만약 a[m]이 찾으려는 값보다 작다면 search(a, m-1, x) 를 실행하여 인덱스 번호 0부터 m 전까지 탐색하게되고

a[m]이 찾으려는 값보다 크다면 search(a+m+1, n-m-1, x) 를 실행하여 m의 다음부터 끝까지 탐색하게된다.

 

증명 (Proof by Indouction)

주장 : a[i]=x 라면 i 리턴

Base : n=0 이면 a[i]=x는 없고 -1 리턴

Step

• case1 : a[m]=x면 m 리턴 -> 성립
• case2 : a[m]>x 면 a[m]부터 a[n]에는 x가 없고 i는 a[0]부터 a[m-1] 사이에 있다 -> search(a, m-1, x)
• case3 : a[m]<x 면 a[0]부터 a[m]에는 x가 없고 i는 a[m+1]부터 a[n] 사이에 있다 -> search(a+m+1, n-m-1, x) 

 

3. binary search의 시간복잡도

 

시간복잡도를 알아보자

반을 나눠 계속 계산을 반복하는데, 한번 계산을 할 때마다 탐색해야할 수열의 크기가 반으로 줄게 된다. 

 

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

      = 1+1+T(n/4) = ... =log n

따라서 T(n) = O(log n) 

 

로그에 대해 더 자세히 보자. 

귀 함수를 보면 if (a[m] == x) return m; 까지 돌아가는데 1이라고 가정하면, 1이 아니면 n/2에서 재귀호출을 하기 때문에 계속해서 돌아가면 결국 log n에 수렵하게 된다.