이분 탐색
이분 탐색은 탐색 범위가 매우 넓은 값에서 특정 값을 결정할 때 유용하게 사용되는 알고리즘입니다. 탐색 범위가 크지 않다면 이분 탐색의 사용으로 얻는 효용 역시 크지 않지만, 최적화가 필요한 코드에서는 상당히 자주 유용합니다.
백준 온라인 저지에서는 solved.ac 레이팅이 어느 정도 수준을 넘은 문제라면 이분 탐색을 사용하는건 유니온-파인드와 비슷하게 숨쉬듯 사용하게 하기도 합니다.
이분 탐색
이분 탐색은 어떤 탐색 혹은 판별 내용이 참과 거짓으로 결정될 수 있을 때 사용할 수 있는 탐색 알고리즘입니다.
34를 포함해 1부터 100 사이 임의의 30개 수를 오름차순 정렬하고, 그 중 34를 찾고자 한다고 가정해봅시다. 탐색 범위에 있는 30개 수는 모두 “34보다 작거나 같은가?”라는 특정한 기준에 대해 참, 거짓을 판별할 수 있습니다. 34를 기준으로 수는 참, 참, 거짓, 거짓, ...과 같이 평가됩니다. 그렇다면 그 경계에 있는 수가 34일 것입니다.
위 사례에서의 오름차순 정렬과 같이 값이 잘 정렬되었다면, 판별 결과가 변경되는 “경계”는 단 한 개 형성됩니다. 이분 탐색의 목표는 탐색 범위를 절반으로 잘라가며 그 경계를 찾아내는 것입니다.
탐색 과정과 구현
1
2
1 5 13 34 45 57 59 60 78 84 99
l m h
수가 위와 같이 분포되어있고, 여전히 34를 찾아내야 한다고 가정해봅시다. 다음과 같이 l(low)과 h(high)를 지정해서 탐색을 시작한다면 m(mid)는 그 절반인 5로 지정될 것입니다.
1
2
3
4
5
6
7
8
>>> arr = [...]
>>> low, high = 0, 10
>>> mid = (l + h) // 2
>>> arr[mid]
57
>>> arr[mid] > 34
True
그리고 탐색 범위의 중간에 위치한 57은 34보다 크므로 다음과 같이 탐색 범위를 조정할 수 있습니다.
1
2
3
4
5
6
>>> if arr[mid] > 34:
... high = mid
... else:
... low = mid
>>> high = 5
1
2
1 5 13 34 45 57 59 60 78 84 99
l m h
방금까지 탐색 범위의 중간 위치였던 곳을 끝 위치로 변경하면서 탐색 범위를 절반 줄였습니다. 만약 똑같은 처리를 계속해서 반복한다면 언젠가 34를 찾아낼 수 있을 것입니다.
1
2
3
4
5
6
1 5 13 34 45 57 59 60 78 84 99
l m h
l m h
l m h
l m h
l h
1
2
3
4
5
6
while condition:
mid = (low + high) // 2
if check(mid):
high = mid
else:
low = mid
이분 탐색의 탈출 조건과 “1 차이 오류”
이분 탐색의 핵심은 적절한 탈출 조건입니다. 구간을 계속해서 잘라나가는 이분 탐색은 탐색 조건이 적절하지 않으면 무한 루프에 빠지거나 목표로 하는 결과값과 근소한 차이로 잘못된 결과를 도출할 수 있습니다.
이분 탐색의 탈출 조건으로 low < high, low <= high, low + 1 < high를 주로 사용하는데, 이 조건들은 대게 1 차이로 잘못된 결과를 가져올 수 있습니다. 이것을 흔히 “Off-by-one error(1 차이 오류)”라고 합니다.
이분 탐색의 구현이 헷갈린다면 1 차이 오류를 자주 맞닥뜨릴 가능성이 높습니다. 구체적인 평가 기준에 따라서 탈출 조건을 다르게 구성할 수 있기 때문입니다. 하지만 일반적으로 low + 1 < high를 사용하는 것을 가장 권장합니다.
1
2
3
4
5
6
while low + 1 < high:
mid = (low + high) // 2
if check(mid):
high = mid
else:
low = mid
이 조건은 상당히 범용적입니다. low <= high와 큰 차이점이 없는 것 같아 보이지만, 모든 이분 탐색은 low + 1 == high일 때 탈출하므로 가장 적절히 사용할 수 있습니다.
탐색의 탈출 조건으로 low + 1 < high를 사용했다고 하더라도 1 차이 오류는 발생할 수 있습니다.
1
2
3
1 5 13 34 45 57 59 60 78 84 99
F F F F T T T T T T T
l h
위의 34를 찾는 상황에서 값의 평가 내용이 “34보다 크다”였으므로 34는 참과 거짓의 경계에서 거짓 방향에 위치하고 있습니다. 위 경우에서, 탐색 대상의 위치는 low입니다.
1
2
3
4
5
6
7
1 5 13 34 45 57 59 60 78 84 99
F F F T T T T T T T T
1 5 13 34 45 57 59 60 78 84 99
l m h
l m h
l m h
l h
만약 값의 평가 내용이 “34보다 크거나 같다”였다면 이분 탐색은 위와 같이 탐색하여 탐색 대상의 위치는 high에 위치할 것입니다.
마무리
이분 탐색은 유용하지만 익숙하지 않으면 쉽게 잘못 구현할 수 있습니다. 1 차이 오류를 항상 경계하면서 구현해야합니다. 저를 포함해 많은 사람들이 이 오류를 겪었고, 반복되는 시행 착오를 경험했습니다.
당연하지만 이분 탐색을 원할 때 유용하게 사용하고자 한다면 다소의 연습을 해두는 것이 좋습니다. 아래에 연습을 위한 추천 문제를 달아놓겠습니다.
백준 온라인 저지 1072 게임
백준 온라인 저지 2343 기타 레슨
백준 온라인 저지 2805 나무 자르기