이분 탐색

  일단 이 글에서 이분 탐색이 무엇인지에 관한 설명은 하지 않겠습니다.

이미 잘 정리된 글이 많으며, 잠깐만 구글링을 해 보아도 쉽게 찾을 수 있습니다. (물론 CLRS를 봐도 좋고)

이 포스팅에서는 실수와 정수 범위에서 이분 탐색을 할 때의 탐색 범위에 관해 다룹니다.

 

1. 정수 이분 탐색

  말 그대로 정수 범위에서의 이분 탐색이며, 특정한 조건을 만족하는 최초의 정수 같은 것을 찾을 때 이용합니다.

 

범위 설정

현재 탐색 범위가 $[l,r]$이고, $m=\lfloor \frac{l+r}{2}\rfloor$라고 합시다.

그리고 $g(m)$이 우리가 만족하길 바라는 조건입니다.

 

이때 범위를 나눈다면 두 가지 경우가 있습니다.

 

1. $g(m)$이 True이면, 모든 $n\in [m,r]$에 대해서 $g(n)$ 도 True 이다.

2. $g(m)$이 True이면, 모든 $n\in [l,m]$에 대해서 $g(n)$ 도 True 이다.

 

$g(m)$이 True일때 상황이 1번 이라면 탐색 범위를 $[m,r]$로 잡아 주어야 하며, 2번이라면 $[l,m]$이어야 합니다.

반대로 $g(m)$이 False일 때 1번 상황에서 탐색범위를 $[l,m-1]$, 2번 상황에서 $[m+1,r]$입니다.

 

때에 따라서 $l-r=1$인 상황이고 $l$이 짝수라고 한다면, 무한 루프가 발생할 수 있습니다. 이를 처리하기 위해서 $l-r=1$이라면 탐색을 종료하고, $g(l)$은 True일 것이기에 $g(r)$가 True or False 여부만 확인해주면 됩니다.

 

2. 실수 이분 탐색

실수 범위 내에서 특정한 조건을 만족하는 최초의 $x$ 값을 근사하는 방법입니다.

 

범위 설정

실수 범위에서 이분 탐색을 하기 위해서 $m=\frac{r+l}{2}$로 다시 정의하겠습니다.

정수 이분 탐색에서는 정수 범위만 확인하기 때문에 $g(m)$이 False였다면 탐색 범위에서 $m$을 제외시켜 주었지만, 실수 이분 탐색에서는 그런 행동을 하면 안 됩니다.

 

위에서 정리한 2가지 Case에 대해 실수 이분 탐색에서는

$g(m)$이 True일 때 1번 상황이라면 탐색 범위를 $[m,r]$로 잡아주고, 2번이라면 $[l,m]$으로 잡는다.

$g(m)$이 False일 때 1번 상황이라면 탐색 범위를 $[l,m]$로 잡아주고, 2번이라면 $[m,r]$으로 잡는다.

 

이렇게 변하는 이유는 간단하게, 구간 안의 모든 실수가 탐색 범위에 들어가기 때문입니다.

정확하게 하면 탐색 범위는 $g(m)$이 True이고 1번 상황일 경우에 $(m,r]$입니다만, 구현할 때에는 위에서 서술한 바와 차이가 없습니다.

 

 

닫는 말

이분 탐색은 개념 자체는 쉽지만 구현할 때에 헷갈릴 수 있는 기법입니다. 탐색에 포함하고 배제할 범위를 잘 생각하여 복잡한 상황에서도 실수하지 않도록 하기를 바랍니다.

나정휘 님의 https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

이런 글 도 있으니 필요하다면 참고하시길 바랍니다.