"이분 탐색(Binary Search) 헷갈리지 않게 구현하기"를 공부하며 스스로 이해한 내용을 정리한 글입니다.
이분 탐색이란?
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘입니다. 이 알고리즘은 배열을 절반씩 나누어 탐색 범위를 줄여나가는 방식으로 동작하며, 시간 복잡도는 O(logN)입니다. 이분 탐색은 반드시 오름차순 또는 내림차순으로 정렬된 배열에서만 사용할 수 있습니다.
이분 탐색의 동작 원리
- 중앙값 선택: 배열의 가운데에 위치한 값을 선택합니다.
- 값 비교: 중앙값과 찾고자 하는 값을 비교합니다.
- 찾고자 하는 값이 중앙값과 같다면 탐색을 종료하고 해당 인덱스를 반환합니다.
- 찾고자 하는 값이 중앙값보다 작다면 배열의 왼쪽 절반에서 탐색을 계속합니다.
- 찾고자 하는 값이 중앙값보다 크다면 배열의 오른쪽 절반에서 탐색을 계속합니다.
- 반복: 위 과정을 반복하면서 탐색 범위를 계속해서 절반씩 줄여나갑니다.
- 종료 조건: 찾는 값을 발견하거나, 탐색 범위가 더 이상 없을 때(즉, 시작점이 끝점보다 커질 때) 탐색을 종료합니다.
해당 글에서는 이분 탐색을 이용해 주어진 배열에서 유일하게 존재하는 특정 값을 찾는 것이 아니라, 어떠한 조건(check())을 만족하는 최소나 최대의 경계를 찾는 upper_bound, lower_bound에 집중하여 이야기하고 있습니다.
따라서 이후 내용도 이에 대한 내용을 주로 다룰 것입니다.
세 줄 요약 분석
글을 보면 다음과 같은 세 줄 요약이 제시되어 있습니다.
- [lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
- while (lo + 1 < hi)동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
- 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력
각 번호의 내용에 대해서 살펴보려고 합니다.
1. [lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
해당 내용은 이분 탐색에서 사용되는 lo와 hi의 초기값 설정을 어떻게 해야 하는지를 의미합니다.
이는 해당 글 뒷부분에 있는 자주하는 실수 모음의 1번과도 연계되는 내용입니다.
lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야합니다. 예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때 hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안됩니다. (hi = n + 1, lo = -1로 선언해야 합니다)
뒤에서 이야기하겠지만, 해당 글의 내용대로 코드를 작성하면 조건이 변화하는 경계에 정확히 lo와 hi가 존재하게 됩니다.
그런데 만약, 주어진 구간에서 모두 True이거나 모두 False일 수 있는 상황에서 구간 내에서 lo와 hi를 설정하면 check(lo)와 check(hi)가 같은 값을 가질 수 있습니다.
예를 들어 1 이상 10 이하의 구간에서 1 이상의 수 중 최솟값을 찾는 문제라고 한다면 lo를 1, hi를 10으로 설정하였을 때는 문제를 해결할 수 없고, lo를 0으로 설정해서 경계를 나타낼 수 있도록 해야합니다.
이러면 구간 조건을 만족하지 않는다고 생각할 수도 있는데, 어차피 lo와 hi는 구간을 나타내는 인덱스일 뿐, 실제 계산에 전혀 사용되지 않기 때문에 문제가 발생하지 않습니다.
2. while (lo + 1 < hi)동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
해당 내용은 이분 탐색을 수행하는 방법을 그대로 나타낸 것입니다.
이를 자바 코드로 구현하면 다음과 같습니다.
while (lo + 1 < hi) {
mid = (lo + hi) / 2;
if (check(mid) == check(lo)) lo = mid;
else hi = mid;
}여기서 check(mid) == check(lo)는 이분 탐색에서 lo 방향으로 가는 경우와 hi 방향으로 가는 경우를 판별하는 조건입니다. 이렇게 적으면 다소 어려워보일 수 있는데, 쉬운 예시로 다시 적으면 다음과 같습니다.
1이상 10 이하의 구간에서 4 이상의 수 중 최솟값을 찾는 문제는 다음 코드로 해결할 수 있습니다.
while (lo + 1 < hi) {
mid = (lo + hi) / 2;
if (mid < 4) lo = mid;
else hi = mid;
}이렇게 조건이 설정되는 이유는, 앞서 이야기했듯 조건이 변화하는 경계에 정확히 lo와 hi가 존재하기 때문입니다.
4 미만의 구간에서는 4 이상의 여부가 모두 False이기 때문에 lo는 항상 False에 위치합니다. 반면, 4 이상의 구간에서는 4 이상의 여부가 모두 True이기 때문에 hi는 항상 True에 위치합니다.
따라서 mid가 4 미만이라면 False이기 때문에 lo = mid를 수행하는 것이고, mid가 4 이상이라면 True이기 때문에 hi = mid를 수행하는 것입니다.
단순히 왼쪽으로 갈 지 오른쪽으로 갈 지를 판단하는 조건만 잘 설정하면, 이후 행동은 무조건 lo = mid 또는 hi = mid로 설정하면 됩니다!
3. 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력
이는 이분 탐색의 while 문이 모두 수행되어 종료된 후, 어떤 값이 정답을 나타낸다고 판단해야 하는 지를 의미합니다.
위의 내용대로 코드를 작성하면 조건이 변화하는 경계에 정확히 lo와 hi가 존재하게 됩니다.
이때 우리가 원하는 정답은 크게 4가지 경우가 있을 수 있습니다.
- True에서 False로 변하는 경계에서 True의 최댓값 찾기(upper_bound)
- True에서 False로 변하는 경계에서 False의 최솟값 찾기(lower_bound)
- False에서 True로 변하는 경계에서 False의 최댓값 찾기(upper_bound)
- False에서 True로 변하는 경계에서 True의 최솟값 찾기(lower_bound)
하지만 False에서 True로 변하든, True에서 False로 변하든, 조건만 제대로 설정하면 lo는 반드시 upper bound에 위치하며, hi는 반드시 lower bound에 위치하기 때문에 upper bound를 찾는지, lower bound를 찾는지 판별하는 것이 가장 중요합니다.
예를 들어 1이상 10 이하의 구간에서 4 이상의 수 중 최솟값을 찾는 문제는 False에서 True로 변하는 경계에서 True의 최솟값을 찾는 문제입니다.
즉, lower bound를 얻는 문제이므로 결과는 hi로 얻을 수 있습니다.
앞서 이야기한 내용을 종합적으로 사용하여 다음 코드로 나타낼 수 있습니다.
int lo = 0;
int hi = 10;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (mid < 4) lo = mid;
else hi = mid;
}
int answer = hi;이러한 내용을 이해하고 해당 글을 다시 읽으면 더 수월하게 이해가 될 것이라고 생각합니다.
