[자료구조] 자료구조와 알고리즘의 이해 (2) - 이진 탐색 알고리즘

 

 이진 탐색(Binary Search) 알고리즘
 - 정렬된 데이터가 아니면 적용이 불가능하다.

 예를 들어 아래과 같은 배열이 있을 때,

 

int arr[9] = { 1,2,3,7,9,12,21,23,27 };

 

 이 배열을 대상으로 숫자 3이 저장되어 있는지 확인하기 위해 이진 탐색 알고리즘을 적용해보면

 

이진 탐색 알고리즘의 첫 번째 시도 

 1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

 2. 0과 8을 합하고 그 결과를 2로 나눈다.

 3. 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

 

이진 탐색 알고리즘의 두 번째 시도

 1. arr[4]에 저장된 값과 탐색 대상인 숫자 3의 대소를 비교한다.

 2. 대소 결과는 arr[4] > 3 이므로 탐색의 범위 인덱스를 0~3으로 제한한다.

 3. 0과 3을 더하여 그 결과를 2로 나눈다. 이 때 나머지는 버린다.

 4. 결과 1을 인덱스 값으로 하여 arr[1]에 저장된 값이 3인지 확인한다.

 

 위와 같은 작업을 반복한다.

 

 이렇듯 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다.

 

 

 

 

 BinarySearch.c

#include <stdio.h>
 
int BSearch(int arr[], int len, int target) {
    int first = 0;
    int last = len - 1;
    int mid;
 
    while (first <= last) {
        mid = (first + last) / 2;
        if (target == arr[mid]) {
            return mid;
        }
        else {
            if (target < arr[mid]) {
                last = mid - 1;
            }
            else {
                first = mid + 1;
            }
        }    
    }
    return -1;
}
int main(void) {
    int array[] = {1,3,5,7,9};
    int idx;
    
    idx = BSearch(array, sizeof(array)/sizeof(int), 7);
 
    if (idx == -1) {
        printf("탐색 실패 \n");
    }
    else {
        printf("타겟 저장 인덱스 : %d \n", idx);
    }
}

 

 

 

 이진 탐색 알고리즘의 시간 복잡도
 - 8을 예로 들어 계산해보면 8이 1이 되기까지 2로 나눈횟수 3회 + 데이터가 1개 남았을 때 마지막 비교 연산 1회로 총 4회이다.
 - 즉, n이 1이 되기까지 2로 나눈 횟수 k + 마지막 비교 연산 1회. 시간 복잡도 T(n) = k + 1 이다.
 - 수식으로 나타내면 n * 2^(-k) = 1 ->  k = log_2n 따라서 시간 복잡도 T(n) = log_2n 이다.
 - 여기서 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적으로 증가한다는 사실이기에 +1은 중요하지 않다.

 

 

---

 출처 : 윤성우, 「윤성우의 열혈 자료구조」, 오렌지미디어(2019), p24-p34