이진 탐색(Binary Search)

데이터가 정렬되어 있을 때, 선형 탐색(Linear Search)보다 더 빠른 O(logN)의 시간이 걸리는 탐색 알고리즘이다.

(알고리즘에서 log는 밑이 2인 log₂를 말하는 것이다.)

 

이진 탐색은 UP/DOWN으로 숫자를 맞추는 게임이랑 똑같다고 볼 수 있다.

만약 1~100의 숫자에서 65라는 숫자를 골랐을 경우를 가정하자

65를 빨리 맞출 수 있는 방법은 아래와 같이 5번의 질문으로 끝낼 수 있다.

(1+100)/2 = 50?

UP

(50+100)/2 = 75?

DOWN

(50+75)/2 = 62?

UP

(62+75)/2 = 68?

DOWN

(62+68)/2 = 65?

CORRECT

이 방법은 현재 남은 범위에서 최소값과 최대값의 합에 2를 나누어서 나오는 몫을 물어보며 범위를 갱신하는 방법인데, 이진 탐색도 데이터가 정렬된 상태에서 탐색하기 때문에 이런 방법을 사용하여 값을 찾는다.

 

이 과정을 코드로 만들어야하니 번호를 붙여 설명하자면

1. low와 high라는 변수로 범위를 설정

2. mid라는 변수를 통해 가운데 값을 계산한다.

3-1. mid 값과 찾는 값이 같으면 루프를 빠져나온다.

3-2. val > mid이면 low = mid + 1로 변경, val < mid이면 high = mid - 1로 변경한다.

4. low > high가 될때까지 2~4를 반복한다.

라고 말할 수 있다.

 

이것을 코드로 구현하면

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int num[101];
    int low=1, high=100, mid, val, res = 0;

    cout << "찾는 값을 입력해주세요:";
    cin >> val;

    for(int i = 1; i <= 100; i++)
        num[i] = i;

    while(low <= high)
    {
        mid = (low + high) / 2;
        res += 1;

        cout << mid << endl;

        if (num[mid] == val)
            break;
        if (num[mid] > val)
            high = mid - 1;
        if (num[mid] < val)
            low = mid + 1;
    }

    cout << res << "번만에 값을 찾았습니다." << endl;

    return 0;
}

 

Python

num = [i for i in range(101)]
low, high = 1, 100
res = 0

val = int(input("찾는 값을 입력해주세요: "))

while low <= high:
    mid = (low + high) // 2
    res += 1

    print(mid)

    if num[mid] == val : break
    elif num[mid] > val : high = mid - 1
    else : low = mid + 1

print(str(res)+"번만에 값을 찾았습니다.")

 

 

참고로 이진 탐색은 데이터가 정렬되어 있으니 이것을 그래프로 그려보면 단조증가/단조감소하는 그래프가 나온다.

그리고 삼진 탐색이라는 알고리즘도 있는데 이것은 고등학교 수학에서 배우는 극대값, 극소값 개념이 나온다.

삼진 탐색의 시간복잡도는 O(log₃N)으로 이진 탐색보다 빠른 것 같지만 실제로 사용해보면 이진 탐색보다 느리다고 한다.

이진 탐색은 나중에 자료구조 시간에서 이진 탐색 트리라는 곳에서도 사용이 된다.

 

 

 

 

문제를 통해 이진 탐색을 적용해보자

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

이 문제는 먼저 배열 A를 정렬하고, 나중에 입력 받는 배열을 B라고 할 때 for문으로 배열 B의 값을 하나하나 선택하고, 이진 탐색을 하여 배열 B에서 선택한 값이 정렬된 배열 A에 있는지 확인하면 된다.

 

여기서 시간복잡도는 stl::sort 함수를 사용하는데 이것은 Intro sort이므로 시간복잡도는 O(NlogN), 그리고 선형 탐색을 하는동안 이진 탐색을 하는 코드 역시 O(NlogN)이 걸려서 최악의 경우 O(NlogN)이다.

log₂(100,000)의 값은 약 16.6이기 때문에 1억을 넘지 않아서 1초내로 풀 수 있다.

 

이때 주의할 점은 Fast io를 사용하지 않으면 시간 초과가 나오기 때문에 C++은 cin, cout, endl 대신 scanf, printf, "\n"을 사용하고, Python은 sys.stdin.readline을 사용한다.

 

C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,A[100001],B[100001];
    int low, high, mid, val, res = 0;

    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
        scanf("%d", &B[i]);

    sort(A, A+n);

    for(int i = 0; i < m; i++)
    {
        low = 0;
        high = n-1;
        val = B[i];
        res = 0;

        while(low <= high)
        {
            mid = (low + high) / 2;

            if (A[mid] == val)
            {
                res = 1;
                break;
            }
            if (A[mid] > val)
                high = mid - 1;
            if (A[mid] < val)
                low = mid + 1;
        }

        cout << res << "\n";
    }

    return 0;
}

 

Python 코드

input = __import__('sys').stdin.readline

n = int(input())
A = sorted([*map(int,input().split())])
m = int(input())
B = [*map(int,input().split())]

for i in range(m):
    low, high = 0, n-1
    val = B[i]
    res = 0

    while low <= high:
        mid = (low + high) // 2

        if A[mid] == val:
            res = 1
            break
        if A[mid] > val: high = mid - 1
        else: low = mid + 1
    print(res)