이분 탐색(Binary Search) 헷갈리지 않게 구현하기
Excerpt
개요
이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다.
이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다.
이번 글에서는 이분 탐색을 헷갈리지 않게 구현하는 방법과 이분 탐색의 대표적 응용인 lower_bound, upper_bound에 대해 알아보겠습니다.
(1에서 경계는 항상 [lo, hi] 내에 존재하고, 2에서 Check(lo), Check(hi)는 변하지 않으며, 3에서 lo + 1 >= hi이고, lo < mid < hi에서 lo < hi이므로 lo + 1 == hi를 만족합니다)
이분 탐색(Binary Search)은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법입니다. 이때 결정 문제란 답이 Yes or No인 문제를 의미하며 (이분 탐색 문제에서는) 보통 1개의 parameter를 가집니다.
1 ~ 50까지 오름차순 정렬된 카드 더미에서 28번 카드를 찾는 문제를 예시로 이분 탐색을 알아보겠습니다. 편의상 첫 번째 카드부터 i번째 카드는 v[i], 28은 val로 표기하겠습니다.
이 경우 결정 문제를 “v[i] >= val인가?”로 잡으면 결정 문제의 답은 i가 증가함에 따라 F, F, …, F, T, T, …, T와 같이 분포함을 알 수 있습니다. 이때 우리가 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정 문제가 True가 되는 i값입니다.
이렇게 결정 문제의 parameter(이 경우 i)에 대해 결정 문제의 답이 두 구간으로 나뉘는 것을 “이분적이다”라고 하며 이런 경우 이분 탐색을 사용해 결정 문제의 답이 달라지는 경계를 찾을 수 있습니다.
이분 탐색의 아이디어는 경계를 포함하는 구간 [lo, hi]을 잡은 뒤 구간의 길이를 절반씩 줄여나가며 lo, hi이 경계 지점에 위치하도록 하는 것입니다. 이분 탐색이 끝난 뒤엔 lo의 다음 칸은 hi(즉, lo + 1 == hi)이며 Check(lo) != Check(hi)입니다. 이때 Check(x)는 결정 문제의 parameter가 x일 때 결정 문제의 답을 의미합니다.
위의 예시에선 [1, 50] -> [25, 50] -> … -> [27, 28]로 lo, hi를 줄여나간 뒤 hi = 28을 찾아주면 됩니다. 이분 탐색은 구간의 범위가 클 때 특히 효과적입니다. 만약 카드가 100만장 있었다고 하면 특정 카드를 하나하나 앞에서부터 찾으면 최대 100만번의 연산이 필요하지만, 이분 탐색을 이용하면 2^20 >= 1,000,000이기 때문에 최대 20번의 연산으로 원하는 카드를 찾을 수 있습니다.