이분 탐색은 사람마다 구현 방식이 다르긴 한데 크게 나누면 닫힌구간 [l, r]을 쓰는 사람과 반닫힌구간 [l, r)을 쓰는 사람으로 나뉜다.

나는 옛날에 삽질 해본 이후부터는 항상 반닫힌구간만을 써왔고 그 삽질을 해본지도 꽤 오래되서 왜 반닫힌구간을 썼는지도 기억이 잘 안 났었는데, 이번에 오랜만에 생각해본 기회에 왜 이분 탐색을 할 때는 반닫힌구간을 써야하는지 이유를 정리한다.

반닫힌 구간?

일단 반닫힌 구간을 이용한 이분 탐색 과정을 서술한다. 어떤 조건, $f(m)=1$을 만족하는 가장 큰 정수를 찾으려고 할 때, 먼저 $[l, r)$ 구간을 적당히 잡는다. 이 $[l, r)$ 구간은 항상 두 가지 조건을 만족하는데, $f(l)=1, f(r)=0$이다. 처음에도 그렇고 루프를 반복하는 중간에도 이 조건을 유지시킬 것이다.

1. $m:=\frac{l+r}{2}$가 $f(m)=1$을 만족한다면 $l:=m$, 그렇지 않다면 $r:=m$을 대입한다. 대입 이후에도 $f(l)=1, f(r)=0$가 성립함을 주목하라.
2. $r-l$은 구간의 길이이며 또한 이 구간에 포함된 정수의 개수와 같다. 이 구간에 포함된 정수가 단 하나만 있을 때는 "$f(m)=1$을 만족하는 가장 큰 정수"를 찾은 경우이며, 루프를 종료하며 $l$을 답으로서 반환하면 된다.
3. 당연히 $r-l>1$이면 구간에 포함된 정수가 1개 초과이므로 루프를 반복한다. (다시 말해, 1. 으로 돌아간다.)

그래서 왜 닫힌구간 말고 반닫힌 구간을 써야 하는가?

1. 무한루프를 고려할 필요가 없다.

이분탐색에 있어 무한루프가 나는 경우는 간단하다. $l=m$인데 $l:=m$을 실행한다든지 하는 경우다.
반닫힌구간을 쓰면 루프를 돌 동안에는 반드시 $r-l>1$이므로 $l, r$ 사이에 $l, r$이 아닌 정수가 존재한다. 따라서 $l:=m, r:=m$을 실행해도 구간이 줄어들지 않을 일이 없다.

2. m+1? m-1?

반닫힌구간을 쓰면 $l, r$에 m을 대입할지 m+1을 대입할지 m-1을 대입할지 고려할 필요가 없다.
또한 $m=l+r>>1$을 쓸 지 $m=l+r+1>>1$을 쓸 지 고려할 필요도 없다.^[1]

예시

예시를 보여줘 이해를 돕겠다.

어떤 조건을 만족하는 가장 큰 수를 찾으려면 구간 $[l, r)$을 다뤄가며, $m:=\frac{l+r}{2}$로 $l, r$에 $m$을 반복적으로 대입하여, 구간을 줄여가 루프가 끝날 때 $l$이 답이 된다.
어떤 조건을 만족하는 가장 작은 수를 찾으려면 구간 $(l, r]$을 다뤄가며, $m:=\frac{l+r}{2}$로 $l, r$에 $m$을 반복적으로 대입하여, 구간을 줄여가 루프가 끝날 때 $l$이 답이 된다.^[2]

근데 반닫힌구간 대신 닫힌 구간을 쓴다면,
어떤 조건을 만족하는 가장 큰 수를 찾으려면 구간 $[l, r]$을 다뤄가며, $l:=m, r:=m-1$을 대입한다. 또 무한루프를 방지하기 위해 $m:=\frac{l+r}{2}$ 대신 $m:=\frac{l+r+1}{2}$을 써야 한다. $l=m$인데 $l:=m$을 수행하면 구간 길이가 안 줄어들어 무한루프를 돌기 때문이다.
어떤 조건을 만족하는 가장 작은 수를 찾으려면 구간 $[l, r]$을 다뤄가며, $l:=m+1, r=m$을 대입한다.

-1, +1이 붙은 이유는 열린구간이 아니라 닫힌 구간을 다루기에 구간을 줄여나갈 때 한칸을 더 줄여야 하기 때문이다. 또 닫힌구간을 쓸 때는 종료 조건도, $r-l=1$이 아니라 $r-l=0$으로 다르다.

$m:=\frac{l+r}{2}$과 $m:=\frac{l+r+1}{2}$ 중 뭘 쓸지도, 반닫힌구간을 쓸 때는 둘 중 아무거나 써도 된다. 구간 길이 $r-l$이 항상 2 이상이기에 둘 중 뭘 써도 $l$보다 크고 $r$보다 작기 때문이다. 근데 닫힌구간을 쓸 때는 무한루프가 안 나도록 생각을 한 후에 써야 된다.

사실 뭐 대충 구현해서 결과만 맞으면 아무래도 좋은 기초 중의 기초 알고리즘이긴 하지만 처음 배웠을 때 혼란스러운 것도 사실이라 간단히 글로 정리해봤다. 아무튼 이분탐색은 꼭 반닫힌구간으로 하자. 어떤 조건을 만족하는 가장 큰 수를 찾을 때와 대비해 가장 작은 수를 찾을 때는 $[l, r)$ 대신 $(l, r]$을 쓰는 게 불만이라면 각주^[2:1]에서 언급했듯 그냥 $f(m)=0$을 만족하는 가장 큰 수를 찾고 여기다 1을 더하면 그만이다. 결국 가장 큰 수를 찾든 가장 작은 수를 찾든 그게 그거라는 말이다.

while, m 계산, l이나 r에 m 대입하는 방식 외에 binary jumping 방식으로 구현하는 예시도 있다. 보편적이지는 않으나 간지 있어 보인다는(?) 큰 장점이 있다. 정수 오버플로우는 조심하자. 출처는 이 글에서 dohoon님의 커멘트.

int x = lo-1;
for (int b = hi; b >= 1; b >>= 1)
    while (x+b <= hi and f(x+b)) x += b;

---

1. . >>는 rshift 연산자로 a>>1은 a를 2로 나눈 것을 뜻한다. 또한 덧셈보다 우선순위가 밀려 $m=(l+r)>>1$과 같이 괄호를 쳐줄 필요가 없다. ↩︎

2. 사실 $f(m)=0$을 만족하는 가장 큰 수를 찾고 여기다 +1을 해도 된다. ↩︎ ↩︎