이진 검색

이진 검색

이진 검색(Binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

 

오름차순으로 정렬된 데이터에서 66을 검색하는 과정이다. 66은 중앙 요소 40보다 큰 값이다. 그러므로 대상을 뒤쪽의 요소들로 좁힐 수 있다.

 

예제 코드

/* 이진 검색 */
#include <stdio.h>
#include <stdlib.h>

int bin_search(const int a[], int n, int key)
{
    int pl = 0;
    int pr = n - 1;
    int pc;

    do {
        pc = (pl + pr) / 2;
        if(a[pc] == key)    /* 검색 성공 */
            return pc;
        else if(a[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while(pl <= pr);
    return -1;  /* 검색 실패 */
}

int main(void)
{
    int i, nx, ky, idx;
    int *x;

    puts("이진 검색");
    printf("요소 개수 : ");
    scanf("%d", &nx);

    x = calloc(nx, sizeof(int));
    printf("오름차순으로 입력하세요.\n");
    printf("x[0] : ");
    scanf("%d", &x[0]);
    for(i = 1; i < nx; i++) {
        do {
            printf("x[%d] : ", i);
            scanf("%d", &x[i]);
        } while(x[i] < x[i - 1]);   /* 바로 앞의 값보다 작으면 다시 입력 */
    }

    printf("검색값 : ");
    scanf("%d", &ky);
    idx = bin_search(x, nx, ky);
    if(idx == -1)
        puts("검색에 실패했습니다.");
    else
        printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);
    free(x);

    return 0;
}

 

복잡도

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것

2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

선형 검색의 시간 복잡도

int search(const int a[], int n, int key)
{
    int i = 0;	# 1
    while(i < n) {	# 2
        if(a[i] == key)	# 3
            return i;	# 4
        i++;	# 5
    }
    return -1;	# 6
}

위 코드는 1 ~ 6의 각 단계가 몇 회 실행되는지에 대한 내용 정리이다.

 

- 1 : i에 0을 대입 후 처음 한 번 실행한 이후에는 없다. (이렇게 한 번만 실행하는 경우 복잡도는 O(1)로 표기한다)

- 2 : 배열의 끝에 도달했는지를 판단하는 2와 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지를 판단하는 3의 평균 실행 횟수는 n/2이다. 이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)이다.

- 4, 6 : 이 부분도 한번만 실행하기 때문에 O(1)로 표기한다.

 

 

이진 검색의 시간 복잡도

int bin_search(const int a[], int n, int key)
{
    int pl = 0;		# 1
    int pr = n - 1;	# 2

    do {
        int pc = (pl + pr) / 2;	# 3
        if(a[pc] == key)    /* 검색 성공 */	# 4
            return pc;	# 5
        else if(a[pc] < key)	# 6
            pl = pc + 1;	# 7
        else	# 8
            pr = pc - 1;	# 9
    } while(pl <= pr);	# 10
    return -1;  /* 검색 실패 */# 11
}

- 1 : 실행 횟수 1 복잡도 O(1)

- 2 : 실행 횟수 1 복잡도 O(1)

- 3 : 실행 횟수 log n 복잡도 O(log n)

- 4: 실행 횟수 log n 복잡도 O(log n)

- 5 : 실행 횟수 1 복잡도 O(1)

- 6 : 실행 횟수 log n 복잡도 O(log n)

- 7 : 실행 횟수 log n 복잡도 O(log n)

- 8 : 실행 횟수 1 복잡도 O(1)

- 9 : 실행 횟수 log n 복잡도 O(log n)

- 10 : 실행 횟수 log n 복잡도 O(log n)

- 11 : 실행 횟수 1 복잡도 O(1)