본문 바로가기

컴퓨터 공학/알고리즘

[탐색 알고리즘] 이진 탐색 알고리즘(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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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[] = { 1237912212327 };
    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, 0sizeof(arr) / sizeof(int- 1, inputNum);
    if (idx == -1){
        printf("Fail\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
}
cs


Output

1
2
3
4
5
6
7
10
Fail
Fail
 
2
1
1
cs


  • 김동규 2017.08.20 17:12

    안녕하세요. 코드 중에 궁금한 사항이 있어서 글 남깁니다.
    재귀 바이너리 서치 함수에서 BSearchRecur(ar, first, last, target);
    이 부분에 return 을 사용하지 않은 이유와, 사용하지 않아도 결과값이 나오는 이유가 궁금합니다.