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

반응형

 

우선 탐색은 여러 정보들 중에서 특정한 값을 찾는 것이다.

 

사전을 예로 들어, 사전에서 특정한 단어를 찾는 방법은 대표적으로 2가지가 있다.

Orange라는 단어를 찾는다고 해보자. 첫 번째 방법은 처음부터 Orange가 나올 때까지 찾아보는 것이다.

 

 

이 방법도 생각할 수 있다. 사전의 중간(Kiwi)을 펼쳐놓고 Orange의 위치는 이보다 뒤이므로 나머지 뒷부분에서 중간을 펼치고... 를 반복해 Orange를 찾는 방법이다.

 

 

첫번째 방법이 선형 탐색(순차 검색), 두번째 방법이 이진 탐색(이분 탐색)이라고 볼 수 있다.

 

선형 탐색(Linear Search)

처음부터 찾고자 하는 값이 나올 때까지 탐색하는 기법이다.

 

배열 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이 있고 8을 찾는다고 하면, 선형 탐색은 다음 과정으로 진행된다.

1은 찾는 값이 아니다.
2는 찾는 값이 아니다.
3은 찾는 값이 아니다.
...
7은 찾는 값이 아니다.
8은 찾는 값이 맞다. 찾는 값은 8번째에 있다.

 

처음부터 찾아나가기 때문에, 시간 복잡도는 \(O(n)\)이 된다.

 

다음은 백준 온라인 저지의 1920번 문제를 선형 탐색으로 풀이한 것이다. 아래 풀이는 제출시 시간 초과가 발생한다.

[BOJ 1920번] 수 찾기

1920번: 수 찾기

 

#include <cstdio>

int A[100000];
int N, M;

int linear_search(int find) {
    for (int i = 0; i < N; i++) {
        if (A[i] == find) {
            return 1;
        }
    }
    
    return 0;
}

int main() {
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    scanf("%d", &M);

    int find;
    for (int i = 0; i < M; i++) {
        scanf("%d", &find);
        printf("%d\n", linear_search(find));
    }

    return 0;
}

 

배열의 크기가 작으면 큰 상관이 없겠지만, 배열의 크기가 커지기 시작한다면 문제가 발생한다.

 

이 단점을 보완하는, 더 빠른 탐색 시간을 보장하는 알고리즘이 바로 이진 탐색이다.

 

이진 탐색(Binary Search)

정렬된 리스트에서 중간 값을 선택해 찾고자 하는 값보다 큰지 작은지를 비교하면서 찾고자 하는 값을 찾는 방법이다.

정렬된 리스트임에 유의한다. 탐색 방법의 특성상 정렬된 리스트에서만 사용 가능한 방법이다.

\(O(n)\)인 선형 탐색과는 달리 \(O(log n)\)의 복잡도를 가진다.

 

정렬된 배열 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 이 있고 8을 찾는다고 하면, 이진 탐색은 다음 과정으로 진행된다.

배열에서 중간값 5는 찾고자 하는 값보다 작다.
그러니 5부터 왼쪽의 값들은 무시한다.

나머지 오른쪽 배열에서 중간값은 7이다.
7은 찾고자 하는 값보다 작다.
그러니 7부터 왼쪽의 값들은 무시한다.

또 그 나머지 오른쪽 배열에서 중간값은 8이다.
8은 찾는 값이 맞다. 찾는 값은 8번째에 있다.

 

위의 선형 탐색과 값이 맞는지 체크하는 횟수를 비교해보자.

선형 탐색은 8을 찾기 위해 8번 비교해야했지만, 이진 탐색은 단 3번만에 탐색이 종료되었다.

이진 탐색이 선형 탐색보다 속도가 더 빠르다는 점을 확인할 수 있다.

 

아래는 위 1920번 문제를 이진 탐색으로 다시 풀이한 것이다. (이제 제출시 통과된다.)

 

#include <cstdio>
#include <algorithm>

int A[100000];
int N, M;

int bin_search(int find) {
    int left = 0;
    int right = N - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;

        if (A[mid] == find) {
            return 1;
        }
        else if (A[mid] < find) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return 0;
}

int main() {
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    // 이진 탐색을 위해 반드시 정렬을 해준다.
    std::sort(A, A + N);

    scanf("%d", &M);

    int find;
    for (int i = 0; i < M; i++) {
        scanf("%d", &find);
        printf("%d\n", bin_search(find));
    }

    return 0;
}

 

 

728x90