[알고리즘] 이분 탐색이 너무 헷갈릴 때

이분 탐색에 대해서는 다음의 글을 참고: 이분 탐색과 최적화 문제

우선 이분 탐색의 큰 틀은 대충 알 것이다.

while(l < r) {
    int m = (l + r) / 2;

    if( check(m) ) // m이 조건을 만족
    	l = m;
    else // m이 조건을 불만족
    	r = m;
}

return l;

(check(m) 만족에 따라 l, r 어느 쪽의 범위를 좁히느냐는 문제마다 다르니 넘어가고)

나만 그런지 모르겠는데 l, r 경계값과 리턴값이 항상 헷갈린다. 뭐 언제는 while(l+1 < r)을 썼던 거 같고 언제는 if문 안에 check(l)==check(m)를 썼던 거 같고... 제대로 정리가 안된 탓이겠지ㅜㅜ

 

여튼 내가 헷갈렸던 바리에이션(?)은 사실 모두 맞다. 다만 탐색 범위에 따라 다른 것이다. 정확히는 탐색 범위를 반열림 구간 [L, R)으로 설정하느냐, 닫힘 구간 [L, R]으로 설정하느냐에 따라 다르다.

차례로 보자.

 

 

[ L, R ) (반열림 구간)

int l = 0, r = max + 1;
while (l < r) {
    mid = (l + r) / 2;
    if (check(mid)) 
        l = mid + 1;   // mid는 이미 확인된 값 → 다음 후보는 mid+1
    else
        r = mid;
}

• 초깃값: l = 최소값, r = 최대값 + 1
• 종료 조건: while(l < r)
• 범위 이동: l = mid + 1 +1 안해주면 while문에서 무한 루프 돌 가능성이 있다. (l == mid인 경우)
• 불변 조건: r은 항상 조건을 만족하지 않는 첫 지점
• 따라서 종료 후:
  • l == r == 경계의 첫 지점
  • 조건 만족 최댓값 = l - 1
  • 조건 만족 최솟값 = l
  • 즉 MIN ~ l-1 의 값이 같고 l ~ MAX의 값이 같다.
• 이 경우는 R은 전혀 return의 고려 대상이 아님. 그냥 l 또는 l-1 바로 쓰면 됨.
• 많이 쓰이는 lower_bound 패턴.

 

+) 여기서 나는 진짜 이분 탐색 뇌 빼고 적고 싶다, 하면

int l = 0, r = max + 1;
while (l < r) {
    mid = (l + r) / 2;
    if (check(l) == check(mid)) // mid의 체크 값이 l, r 중 어느 것과 같은지? 다른 쪽에 초점을 둬야 한다
        l = mid + 1;
    else
        r = mid;
}

if 부분을 저렇게 쓰고 넘어가면 된다. 왜냐면 어차피 우리가 찾는건 check의 결과값이 달라지는 경계이기에 mid와 값이 다른 쪽으로 범위를 좁혀야 한다. 2차 함수 미분했을 때 f'(x) == 0인 부분을 찾는 것과 같다. 물론 check가 복잡하다면 시간 복잡도에서 불리하긴 하겠지만.. 앵간하면 괜찮지 않을까(무책임)

 

---

 

[ L, R ] (닫힌 구간)

int l = 0, r = max;
while (l + 1 < r) {
    mid = (l + r) / 2;
    if (func(mid) >= M)
        l = mid;    // mid는 가능 → 더 오른쪽으로
    else
        r = mid;    // mid는 불가능 → 왼쪽으로
}

• 초깃값: l = 최소값, r = 최대값
• 종료 조건: while(l + 1 < r)
• 종료 후: l과 r이 붙어있음
• 이때는 둘 중 하나가 답일 수 있으므로 마지막에 check(l) / check(r)을 확인해야 함.
• 주로 최솟값/최댓값 후보가 정확히 경계에 있을 때 쓰는 방식.

 

---

 

정리

👉 경계 하나만 찾으면 되는 문제는 [l, r) + while(l < r) + return l
👉 정확한 최소/최대값 찾는 문제는 [l, r] + while(l+1 < r) + l/r 중 선택

 

코테/실무에서는 보통 [ l, r ) 반열림 버전을 쓰는 게 압도적으로 많다고 지피띠니가 그랬다.
왜냐하면

1. while 종료 후 return L (혹은 return L-1)로 깔끔히 끝낼 수 있음
2. 마지막 L, R 확인 불필요 → 실수 줄어듦

그래서 결론! 아래의 구조를 잘 외워서 헷갈리지 않도록 하자...

int l = 0, r = max + 1;
while (l < r) {
    mid = (l + r) / 2;
    if (check(l) == check(mid)) // mid의 체크 값이 l, r 중 어느 것과 같은지? 다른 쪽에 초점을 둬야 한다
        l = mid + 1;
    else
        r = mid;
}