[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search)

[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search)

이진 탐색 알고리즘

이진 탐색 알고리즘을 위해서는 데이터가 정렬되어 있어야 한다. 

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

배열 { 1, 2, 3, 7, 9, 12, 21, 23, 27 }에서 3을 찾는 경우 알고리즘 진행 방식은 아래와 같다.

첫번째 시도

배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 그 인덱스에 해당하는 값이 3인지 확인한다.

두번째 시도

arr[4]의 값 9와 찾는 값 3의 대소를 비교한다.

3이 9보다 작으므로 인덱스 4~8은 탐색의 범위에서 제외한다.(정렬된 데이터여서 가능)

0과 3을 더하고 2로 나눈다.(나머지는 버린다.)

결과가 1이므로 arr[1]의 값 2와 찾는 값 3이 일치하는지 비교한다.

세번째 시도

arr[1]의 값 2와 찾는 값 3의 대소를 비교한다.

3이 2보다 크므로 인덱스 0~1은 탐색의 범위에서 제외한다.

2와 3을 더해서 2로 나눈다.

결과가 2이므로 arr[2]의 값 3과 찾는 값 3이 일치하는지 비교한다.

일치하므로 알고리즘을 종료한다.

탐색 대상이 절반씩 줄어드므로 시간 복잡도는 $O(logn)$을 가진다.

종료 조건

탐색 실패시 시작 인덱스가 마지막 인덱스보다 큰 경우 탐색이 종료된다.

이해가 가지 않는다면 아래 코드를 보고 탐색에 실패하는 경우를 생각해 보면 이해가 갈 것이다.

Code

#include <stdio.h>
 
// 이진 탐색 알고리즘 반복문 구현
// 찾는 숫자가 있으면 찾는 숫자의 인덱스 리턴 없으면 -1 리턴
int BSearch(int ar[], int len, int target){
    int first = 0;
    int last = len - 1;
    int mid = 0;
 
    // first와 last가 같은 경우까지 반복하는 이유
    // while(first < last)이면 마지막 하나가 남았을때
    // 검사하지 않고 종료되기 때문이다.
    while (first <= last){
        mid = (first + last) / 2;
        if (ar[mid] == target){
            return mid;
        }
        else{
            if (ar[mid] > target)
                last = mid - 1;
            else
                first = mid + 1;
        }
    }
    return -1;
}
 
// 이진 탐색 알고리즘 재귀 구현
int BSearchRecur(int ar[], int first, int last, int target){
    int mid = (first + last) / 2;
    if (first > last)
        return -1;
    else{
        if (ar[mid] == target)
            return mid;
        else{
            if (ar[mid] > target){
                last = mid - 1;
                BSearchRecur(ar, first, last, target);
            }
            else{
                first = mid + 1;
                BSearchRecur(ar, first, last, target);
            }
        }
    }
}
 
int main(int arc, char** argv){
    int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27 };
    int idx = 0, inputNum = 0;
 
    scanf_s("%d", &inputNum);
 
    idx = BSearch(arr, sizeof(arr) / sizeof(int), inputNum);
    if (idx == -1){
        printf("Fail\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
 
    idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, inputNum);
    if (idx == -1){
        printf("Fail\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
}

Output

10
Fail
Fail
 
2
1
1