이분 탐색
이분 탐색은 탐색 범위가 매우 넓은 값에서 특정 값을 결정할 때 유용하게 사용된다. 탐색 범위가 크지 않다면 이분 탐색의 사용으로 얻는 효용 역시 크지 않지만, 최적화가 필요한 코드에서는 상당히 자주 유용하다.
백준 온라인 저지에서는 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에 위치할 것이다.
마무리
백준 온라인 저지 1072 게임
백준 온라인 저지 2343 기타 레슨
백준 온라인 저지 2805 나무 자르기