이분 탐색

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

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

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

 

1. 정수 이분 탐색

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

 

범위 설정

현재 탐색 범위가 \(\left [l, r\right]\)이고, \(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) 헷갈리지 않게 구현하기

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