38. Binary Search

이분 탐색(이진 탐색, Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 방법이다. 기본적인 원리는 정렬된 데이터를 앞쪽 절반과 뒤쪽 절반으로 나눈 다음 두 구간 중 해당 값을 포함하지 않는 구간을 배제하고 남은 한 구간에서 다시 데이터를 찾는 과정을 반복하는 것이다. 이렇게 하다가 구간에 값이 하나 남았을 경우 그 값을 찾는 값과 비교해서 같다면 원하는 값을 찾은 것이고, 다르다면 데이터에 원하는 값이 존재하지 않는 것이다. 데이터의 수가 $n$일 때 이분 탐색의 시간복잡도는 $O(\text{lg }n)$이다.

 

BOJ 1920. 수 찾기 (Silver IV)

이 문제를 통해서 이분 탐색을 더 자세히 이해할 수 있다. 일단 $n$개의 정수를 정렬하고, 찾으려는 각각의 값이 $n$개의 정수 중에 존재하는지를 이분 탐색으로 확인하면 된다.

원리는 쉽지만, 구현 시 주의해야 할 부분이 존재한다.

 

이분 탐색의 구현을 위해서는 데이터의 양 끝과 중간 위치를 저장할 세 개의 변수가 필요하다. (이 변수들이 '값' 자체가 아닌 값의 '위치'를 저장한다는 사실을 헷갈리지 않아야 한다) 일반적으로 데이터의 처음을 가리키는 변수$(l)$는 첫 번째 원소의 인덱스를 저장하기 때문에 별로 문제가 되지 않지만, 데이터의 끝을 가리키는 변수$(r)$는 마지막 원소의 인덱스를 저장할 수도 있고 마지막 원소 다음의 인덱스를 저장할 수도 있다. $r$이 저장하는 값에 따라서 찾으려는 데이터가 존재할 수 있는 인덱스 구간이 $[l, r]$이 될 수도 있고 $[l, r)$이 될 수도 있으므로 구현 시 둘 중 어떤 방법을 사용할지를 확실하게 정해야 한다.

 

다음으로 데이터의 중간 위치를 가리키는 변수$(m)$이 어떤 인덱스를 가리키게 할지를 결정해야 한다. 만약 $l$과 $r$의 홀짝이 같다면 단순히 $m=(l+r)/2$로 두면 문제가 없다. $l$과 $r$의 홀짝이 다를 경우가 문제인데, 이 경우 구간의 정중앙이 하나로 결정되지 않기 때문에 가운데에 있는 두 인덱스 중 어느 한쪽을 $m$으로 하게 된다. 왼쪽을 $m$으로 할 경우 $m=(l+r)/2$로, 오른쪽을 $m$으로 할 경우 $m=(l+r+1)/2$로 두면 된다.

 

또한 $m$을 정하는 방법에 따라 구간을 나누는 방법도 달라진다. $m=(l+r)/2$인 경우 나누어지는 두 구간은 $[l, m]$과 $[m+1, r]$(또는 $[m+1, r)$)이 되고, $m=(l+r+1)/2$인 경우 $[l, m-1]$과 $[m, r]$(또는 $[m, r)$)이 된다. 이런 차이는 두 구간의 크기 차이를 최소화해야 하기 때문에 발생한다. 더 정확한 목적은 크기가 $0$인 구간이 생기지 않게 하는 것이다. 구간을 잘못 나눠서 두 구간 중 하나의 크기가 $0$이 될 경우 탐색이 끝나지 않는 문제가 발생할 수 있다.

 

이것들을 모두 고려해서 구현한 이분 탐색 코드는 다음과 같다. $r$은 구간의 마지막 원소의 인덱스를 가리킨다. 찾는 수는 $k$이다.

------------------------------------

i) m = (l + r) / 2

for(l = 1, r = n; l < r;)
{
    m = (l + r) / 2;
    if(a[m] < k)l = m + 1;
    else r = m;
}

------------------------------------

ii) m = (l + r + 1) / 2

for(l = 1, r = n; l < r;)
{
    m = (l + r + 1) / 2;
    if(a[m] <= k)l = m;
    else r = m - 1;
}

------------------------------------

반복이 끝난 후 $a[l]$이 $k$와 같다면 $k$의 위치를 찾은 것이고, 다르다면 데이터에 $k$가 없는 것이다. 이때 마지막 비교에 $a[l]$ 대신 $a[r]$을 써도 결과는 같지만 $a[m]$을 쓰면 결과가 달라질 수 있으므로 주의해야 한다.

만약 $r$이 구간의 마지막 원소 다음의 인덱스를 가리킬 경우 나머지는 그대로 두고 반복의 조건만 $l+1<r$로 바꾸면 된다.

 

위에서 언급한 주의할 점들 때문에 이분 탐색의 구현에 익숙하지 않을 경우 실수하기 쉽다.

------------------------------------

for(l = 1, r = n; l < r;)
{
    m = (l + r) / 2;
    if(a[m] < k)l = m;
    else r = m;
}

------------------------------------

for(l = 1, r = n; l < r;)
{
    m = (l + r) / 2;
    if(a[m] <= k)l = m;
    else r = m;
}

------------------------------------

위의 두 코드는 특정한 상황에서 반복이 끝나지 않게 된다. $l+1=r$인 경우 $m=l$이 되고, 비교를 통해서 $l=m;$ 문장이 실행될 경우 반복 후 $l$과 $r$ 중 어느 값도 변하지 않는다. 따라서 무한루프가 발생한다. $m$을 $(l+r+1)/2$로 설정하더라도 $r=m;$ 문장이 실행되면 반복 후 $l$과 $r$이 모두 그대로인 것은 마찬가지이다. 이 상황을 막기 위해서 $a[m]$이 $k$와 같은 경우를 먼저 따로 처리한다고 해도 반복이 끝나지 않을 가능성이 여전히 존재한다. 실수하기 좋은 코드이므로 주의할 필요가 있다.

 

정확한 이분탐색 코드를 작성한 다음 찾으려는 각각의 수에 대해서 실행하면 위의 문제를 해결할 수 있다. 이 문제의 경우 매우 전형적이지만 실수하기 좋은 부분이 많으므로 꼼꼼한 확인이 필요하다.

 

1. $n$개의 정수를 정렬하는 과정에서 문제가 생기는 경우
A) $n$의 최대값이 $10$만이므로 시간복잡도가 $O(n^2)$인 정렬 방법을 이용할 경우 데이터가 약하지 않다면 당연히 시간 초과가 발생한다.
B) 퀵 정렬을 직접 구현할 경우 모든 입력에 대해 좋은 피벗을 정하는 것이 쉽지 않다. 다양한 저격 데이터가 존재하면 시간 초과가 발생할 가능성이 매우 높다. 피벗을 정할 때 무작위적인 요소를 넣으면 느려지는 문제를 일부 해결할 수는 있다.
C) 병합 정렬을 직접 구현할 경우 배열의 재할당이나 vector의 복사 처리를 잘못하면 시간 초과, 런타임 에러, 메모리 초과 등의 결과가 나올 수 있다.

2. 입출력이 느린 경우
D) C++의 cin, cout을 그냥 사용할 경우 시간 초과가 발생할 수 있다. cin, cout의 입출력 속도가 느리기 때문이며, 이때는 ios::sync_with_stdio(0);과 cin.tie(0);을 main 함수의 시작 부분에 추가해야 한다. 단 이것을 추가하면 cin, cout 계열의 입출력과 scanf, printf 계열의 입출력 중 하나만 일관적으로 사용해야 한다. 두 계열의 입출력을 같이 사용하면 작동 순서가 엉망이 될 수 있다.
E) 줄바꿈을 endl로 처리해서 시간 초과가 발생할 수도 있다. endl이 출력 버퍼를 매번 비우기 때문에 느려지는 것이며, 이때는 endl 대신 '\n'을 사용해야 한다.

3. 오버플로우가 발생하는 경우
F) $4$바이트 정수 자료형을 사용하고 $l+r$을 계산하거나 $l$과 $r$의 대소 비교를 $r-l$과 같은 방식으로 하는 경우 오버플로우가 발생할 수 있으며 이때는 $8$바이트 정수 자료형을 사용하면 된다. $4$바이트 정수 자료형으로도 조금 복잡한 방법으로 해결은 가능하지만 그렇게까지 해야 할 이유가 딱히 없다.

4. 이분 탐색의 구현이 잘못된 경우
G) $l==r$일 때 반복을 끝내는 방식으로 구현하면 시간 초과가 발생할 수 있다. 구현 방식에 따라 반복 중간에 $l>r$이 되는 경우도 존재할 수 있으므로 $l>=r$일 때 반복을 끝내는 방식으로 구현하는 것이 좋다.
H) 이분 탐색 과정에서 한 번의 반복 후에는 $l$과 $r$ 중 최소한 하나의 값이 변한다는 것이 보장되어야 한다.

 

이분 탐색은 단독으로 쓰이는 경우는 생각보다 많지는 않고 나중에 소개할 Parametric Search의 일부로 사용되는 경우가 많다.

 

→ solved.ac tag: binary_search