이분/삼분 탐색과 구현

1. 이분 탐색

이분 탐색이란 탐색의 범위를 절반으로 줄여나가는 방법을 말한다.

결정 문제

답이 yes 혹은 no로 나오는 문제.

일반적으로 이분탐색으로 풀 수 있는 문제들은

• 우리가 정할 수 있는 어떤 값 x가 있다.
• 이 x에 따라, 어떤 결정 문제의 yes/no가 정해진다.
• 문제에서는 그 값이 yes가 나오는 최소/최대의 x를 요구한다.
• x에 의한 결과는 연속적으로 변한다. 즉, x의 값이 증가/감소하다보면, 어느 순간 yes가 no로 바뀐다.
• 즉, x일때 yes이면 x+1(혹은 x-1)일때 no이다.

이러한 성질들을 만족한다.
즉 O와 X의 경계를 찾는 것이 목적인 문제이다.

l-4	l-3	l-2	l-1	l	r	r+1	r+2	r+3
O	O	O	O	O	X	X	X	X

KOI 2012 중,고등부 1번 : 예산 (acmicpc.net 링크, dovelet 옥상에서 koi_money와 koi_budget 둘다)

이 문제와 비교해보자.

1. 우리는 정수 상한액을 정할 수 있다.
2. “해당 상한액을 설정했을 때 필요한 예산이 M을 넘지 않는다”
3. 최대를 요구한다
4. 특정 상한액을 배정할 수 있었다면, 그보다 더 작은 상한액을 배정했을 때 필요한 예산은 더 적으므로 당연히 가능하다.

이들은 ‘이 문제를 이분 탐색으로 풀 수 있다!’라는 추측을 하는데에 아주 큰 도움이 된다.

이제 이분 탐색의 원리를 알아보자.
이분 탐색은 앞에서 말한듯이 탐색의 범위를 절반으로 줄인다.
탐색의 범위라는 것은 ‘이 안에 경계가 있다!’라는 뜻이다.
탐색의 범위가 [l,r] 이라고 하자. 또한 l의 값은 yes, r의 값은 no라고 하자.

그러면 l과 r 사이에는 경계가 반드시 있다. ( (4)에서 연속적이므로 )
l과 r 사이의 어떤 m을 잡고, m에 의한 결과가 yes인지 no인지 살펴본다.

1. m이 yes이면…
   l ~ m까지는 모두 yes이므로 경계는 이 안에 없다.
   따라서 경계는 [m,r]에 대해 탐색하면 구할 수 있을 것이다.
   즉 r=m;으로 만들어도 된다.
2. m이 no이면…
   m ~ r까지는 모두 no이므로 경계가 아니다.
   따라서 경계는 [l,m]에 대해 탐색하면 구할 수 있을 것이다.
   즉 l=m;으로 만들어도 된다.

이 과정을 한 번 거치면, 여전히 l은 yes, r은 no를 유지하면서, 탐색 범위가 조금 더 줄어든다.
또한 l+1 == r이 되는 순간 우리는 우리가 원했던 ‘경계’를 찾게 될 것이다.
m을 항상 $\left \lfloor \large{\frac{l+r}{2}} \right \rfloor$로 만들면 탐색 범위가 항상 절반에 가깝게 줄어들기 때문에, 처음의 탐색 범위가 $X$라고 하면 약 $\log _{2} X$ 번의 탐색만 거치면 ‘경계’를 찾을 수 있다.
구현은 간단하다.

while(l+1 != r){
    m=(l+r)/2;
    (f(m)?l:r)=m;
}

참고로 예산 문제는 이분 탐색 이외의 풀이가 존재한다.

2. 삼분 탐색

(작성중)

---

참고로, parametric search라고 부르는 것은 이/삼분탐색을 지칭하기보다는 (2)의 성질을 말한다.
x라는 parameter(인수)에 의해 나오는 어떤 값을 이용하여 원하는 것을 찾는(search) 알고리즘인 것이다.
즉 [l,r] 사이의 모든 x에 대해서 다 테스트해보고 경계를 찾아도 parametric search라고 말할 수 있을 것이다.
다만 많은 경우 모두 테스트하기에는 오래 걸리고, 그러한 문제를 이/삼분탐색으로 해결하는 경우가 많기 때문에, ‘파라메트릭’을 이/삼분 탐색의 대명사로 쓰는 경우가 잦다.