• 정의 : 연속된 주소에 동일한 타입의 데이터가 저장되는 자료구조이다.
• 장점
• n개 중 k번째 원소에 대한 access(읽기나 쓰기)가 상수 시간에 가능하다.
• “(배열 시작 주소) + k * (자료형 크기)” 번 주소에 접근하면 된다.
• search가 빠르다.
• 단점
• 크기 변화 비용이 크다.
• 근처 공간이 부족하면 원소 전체를 이동시켜야 하기 때문이다.
• Insert, Delete가 느릴 수 있다.

int search(int a[], int n, int x)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i] == x) return i;
    return -1;
}

Binary Search

int search(int a[], int n, int x)
{
    int l, r, m;
    l = 0; r = n-1;
    while(l<=r) {
        m = (l+r)/2;
        if(a[m] < x)
            l = m+1;
        else if(a[m] > x)
            r = m-1;
        else
            return m;
    }
    return -1;
}

1.  초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.
2.  유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다고 가정하면, 다음 반복이 시작되기 전까지도 계속 참이여야 한다.
3.  종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 유용한 특성을 가져야 한다.

1.  초기조건 : l은 인덱스의 시작, r은 인덱스의 끝이므로 l<=i<=r가 성립.
2.  유지조건

  

• x<a[m]이라면 i<m, i<=m-1, r=(m-1)>=i, r >= i.

  

• a[m]<x라면 m+1<=i, l=(m+1)<=i, l<=i.
• invariant가 깨질 수 있는 코드가 없다.

3. 종료조건 : l과 r의 차이가 계속 줄어들기 때문에, 적어도 l=i=r이 될 때 i를 리턴하게 된다.

• a[i] = x인 i가 없다면, l과 r의 차이가 계속 줄어들기 때문에, 루프는 반드시 끝나고 -1이 리턴 됨

int search(int a[], int n, int x)
{
    if(n==0) return -1;

    int m = n/2;
    if(a[m] == x) return m;
    else if(a[m] > x) return search(a, m, x);
    else {
        int r = search(a+m+1, n-m-1, x);
        if(r = -1) return -1;
        else return r+m+1;
    }
}

• 주장 : 만약 어떤 i에 대해서 a[i] = x라면, 위 함수는 i를 리턴한다.
• Base : n = 0인 경우 “어떤 i에 대해서 a[i] = x”가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.
• Step : n=0, n=1, n=2, …, n = k-1인 경우 주장이 참이라 가정하면, n = k인 경우 주장이 참이 됨을 보이면 된다.

• 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중 하나이다. 위에서, n=0, n=1, …, n=k-1인 경우 주장이 참이 된다고 가정하였다. 따라서 n=m일 경우, 주장이 참이 된다. 즉, search(a, m, x)는 정확하게 작동하여 i를 리턴한다. search(a, k, x)는 i를 그대로 리턴하게 되므로, n=k일 때 주장은 참이 된다.
• Case 3 : a[m] < x인 경우, a[i] = x인 경우가 있다면 i는 m+1, m+2, …, k 중 하나이다. search(a+m+1, k-m-1, x)는 n=0, …, n=k-1인 경우 중 하나이므로, 위 가정에 따르면 정확하게 작동하여 i를 리턴한다. 그러나 a에 a+m+1을 입력했기 때문에, 재귀 호출된 함수에서의 i는 호출한 함수 기준으로는 i-m-1가 된다. 이를 고려하여 m+1을 더해 리턴하므로, n=k일 때 주장은 참이 된다.
• Case1, 2, 3에서 a[i] = x를 만족하는 i가 있다고 가정하였다. a[i] = x를 만족하는 i가 없는 경우, 주장은 무조건 성립하므로, 그러한 가정을 해도 문제가 없다. (만족하는 i가 없는 경우는 고려하지 않아도 된다.)