이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다.
이분 탐색 문제를 풀다보면 탈출 조건으로 low ≤ high, low < high, low + 1 < high 중 어느 걸 선택해야 할 지, 정답이 low인지 high인지 (low + high)/2 인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다.
해당 포스팅에서는 이분 탐색을 헷갈리지 않게 구현하는 방법과 이분 탐색의 대표적 응용인 lower bound, upper bound에 대해 알아보겠습니다.
이분 탐색(Binary Search)은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법입니다. 이 때 결정 문제란 답이 Yes or No인 문제를 의미하며 (이분 탐색 문제에서는) 보통 1개의 parameter를 가집니다.
이분 탐색의 아이디어는 경계를 포함하는 구간 [low, high] 구간의 길이를 절반씩 줄여나가며 low, high의 경계 지점에 위치하도록 하는 것입니다. 이분 탐색이 끝난 뒤엔 low의 다음 칸은 high (즉, low + 1 == high) 이며 Check(low) ≠ Check(high) 입니다. 이때 Check(x)는 결정 문제의 parameter가 x일 때 결정 문제의 답을 의미합니다.
mid는 항상 low < mid < high를 만족합니다. 따라서 구간의 길이는 매번 절반씩 줄어들며 언젠간 lo + 1 == hi가 되어서 반복문을 탈출하게 됩니다.
*Q. 1 ~ 100 까지의 배열에서 85를 찾기
// 1. (1 + 100) / 2 -> 50.5 -> 50
// 2. (51 + 100) / 2 -> 75.5 -> 75
// 3. (76 + 100) / 2 -> 87.5 -> 87
// 4. (76 + 87) / 2 -> 81.5 -> 81
// 5. (82 + 87) / 2 -> 84.5 -> 84
// 84 + 1 -> 85*
많은 최적화 문제는 이분 탐색으로 풀 수 있습니다. 최적화 문제란 어떤 조건(Check(x))을 만족하는 x의 최댓값 또는 최소값을 찾는 문제를 말합니다. 이 경우 Check(x)가 x에 대해 이분적이면 이분 탐색을 사용할 수 있습니다.
// 이분 탐색
let low = 1, high = 100;
// Checklist
// Check(low) = True, Check(high) = False를 만족하는가?
while (low + 1 < high) {
const mid = (low + high) / 2; // 항상 low < mid < high를 만족
if (Check(mid)) low = mid;
else high = mid;
}