[ 자료구조 ] 배열 ( Binary Search, Recursive Binary Search)

Array ( 배열 )

• 정의 : 연속된 주소, 동일한 Type
• 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름
• 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다.
• 사용 : 변화가 없거나 드문 자료

배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 

이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다.

 

또 다른 방법은 Binary Search 이다.

이 방법은 sorting 되어있는 상태에서만 사용가능하다.

기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다.

코드로 나타내면

 

int search(int a[], int n, int x)
{
    int l, r, m;  // 처음부터, 끝에서부터, 탐색기
    l=0; r = n-1;
    while (l <=r) {  //r과l이 만나면 종료
        m =(l+r)/2;  // 중간값
        if (a[m] ==x) return m;  // 찾았다
        else if (a[m] > x) r =m-1;  // 끝에 있던거 끌고오기
        else l = m+1;  // 처음에 있던거 끌고오기
    }
    return -1;    
}

 

이 알고리즘 Invariant를 통해서 증명해 보겠다.

 

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

Invariant 은 최초에 성립하고 Invariant 가 깨질수 있는 코드는 전혀 없다.

 

따라서 a[i]=x가  i 가 없다면 루프는 반그시 끝나고 -1이 리턴되고  a[i]=x 인 i 가 있다면 루프 안에서 리턴된다.

 

이는 재귀적으로도 코드를 짤 수 있다.

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-1, x);
    else 
   		r = search (a+m+1, n-m-1, x); // 확인한거 다음 것부터 
    
}

위 코드를 수학적 귀납법으로 증명해보겠다.

 

 

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

 

Base: n=0인 경우 "어떤 i에 대해서 a[i] = x" 가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.

 

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) 에서 성립한다고 가정하면 제일 위 주장이 성립함. 
• case3:  a[m] < x 인 경우 a[0], a[1], a[2], ... ,a[m] 중에서는 x와 같은 값이 없다. 따라서 a[i] = x 인 경우가 있다면 i는 m+1, m+2, ... , n 중 하나이다. 귀납적으로 search(a, m-1, x) 가 정확하다고 가정하면, search(a+m+1, n-m-1, x)도 성립하고, 제일 위의 주장이 성립함.

 

 

시간복잡도를 알아보자

 

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에 수렵하게 된다.