이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로
예시를 통해서 어떻게 동작하는지 살펴보자.
아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자.
방법1
[1단계] left = 0, right = 11 처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다.
mid = (left + right) / 2 로 계산하므로 mid는 5이 된다. 인덱스가 mid(5)인 원소 7이 우리가 찾고자 하는 원소 10보다 작으므로 left = mid+1 을 수행한다.
[2단계] left = 6, right = 11
mid = (left + right) / 2 로 계산하므로 mid는 8이 된다. 인덱스가 mid(8)인 원소 11이 우리가 찾고자 하는 원소 10보다 크므로 right = mid-1 을 수행한다.
[3단계] left = 6, right = 7
mid = (left + right) / 2 로 계산하므로 mid는 6이 된다. 인덱스가 mid(6)인 원소 9가 찾고자 하는 원소 10보다 작으므로 left = mid+1 을 수행한다.
[4단계] left = 7, right = 7
mid = (left + right) / 2 로 계산하므로 mid는 7이 된다. 인덱스가 mid(7)인 원소 10이 찾고자 하는 원소 10과 일치하므로 인덱스 7을 반환하고 알고리즘을 종료한다.
즉, 이분 탐색 알고리즘을 통해 정렬된 배열에서 인덱스가 7인 원소가 10임을 알아낸 것이다.
위 예시(방법1)에서 시행한 방법이 가장 보편적으로 알려진 이분탐색이며 코드로 구현하면 아래와 같다.
방법2
[1단계] cur = -1, step=12 처음에는 현재 위치 cur을 -1, 보폭 step을 배열의 크기(12)로 지정하고 시작한다.
현재 위치 cur(-1)에서 step(12)만큼 이동했을 때 원소는 16이며 10보다 크므로 이동하지 않는다. 10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.
[2단계] cur = -1, step = 6
현재 위치 cur(-1)에서 step(6)만큼 이동했을 때 원소는 7이며 10이하이므로 이동한다. (cur = 5) 현재 위치 cur(5)에서 step(6)만큼 이동했을 때 원소는 16이며 10보다 크므로 이동하지 않는다. 10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.
[3단계] cur = 5, step = 3
현재 위치 cur(5)에서 step(3)만큼 이동했을 때 원소는 11이며 10보다 크므로 이동하지 않는다. 10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.
[4단계] cur = 5, step = 1
현재 위치 cur(5)에서 step(1)만큼 이동했을 때 원소는 9이며 10이하이므로 이동한다. (cur = 6) 현재 위치 cur(6)에서 step(1)만큼 이동했을 때 원소는 10이며 10이하이므로 이동한다. (cur = 7) 현재 위치 cur(7)에서 step(1)만큼 이동했을 때 원소는 11이며 10보다 크므로 이동하지 않는다. 10보다 큰 원소가 나왔으므로 step을 절반으로 줄인다.
step = 0이 됐으므로 현재 인덱스 cur을 반환하고 알고리즘을 종료한다.
참고로, 이 방법은 10이하인 원소라면 계속 이동하므로 10이하인 수 중에서 맨 오른쪽 인덱스를 구하게 된다.
위 예시(방법2)에서 시행한 방법은 파라매트릭 서치에서 사용하기 좋으며 코드로 구현하면 아래와 같다.
위에서 살펴본 두 알고리즘(방법1, 방법2) 모두 단계마다 절반씩 크기가 줄어들기 때문에 시간 복잡도는 $O(log \ n)$을 만족한다.
여기서 n은 살펴보는 전체 범위의 크기(보통은 배열의 크기와 동일)를 의미한다.
2. 파라매트릭 서치 알고리즘
위에서 살펴본 이분 탐색 방법2에 대해서 다시 생각해보자.
결과가 조건(10이하인 수)을 만족하는 원소 중에서 맨 오른쪽 인덱스를 반환하는 알고리즘이었다.
참고로 반환된 인덱스에 +1을 하게 되면 조건을 만족하지 않는 맨 왼쪽 인덱스가 된다.
좀 더 자세히 말하자면 위에서 살펴본 배열에 대해서
원소가 조건(10이하인가?)을 만족하면 α, 그렇지 않으면 β로 바꿔 보자.
이렇게 하면 10이하인 가장 오른쪽 인덱스를 찾는 과정은 가장 오른쪽 α를 찾는 문제와 동일해진다.
만약, 어떤 문제에서 '어떤 숫자 $x$가 답이 될 수 있나?'에 대한 상황이 위와 같이 나타난다면
우리는 이를 이분탐색을 통해서 답의 최댓값 또는 최솟값을 구할 수 있게 되는 것이다.
그리고 이러한 방식의 이분 탐색을 우리는 파라매트릭 서치(parametric search)라고 부른다.
파라매트릭 서치가 적용되는 과정을 아래의 문제를 통해서 살펴보자.
[문제] (백준 2805번) 나무의 개수 N과 가져가야하는 나무의 길이 M이 주어지며, 이어서 나무들의 높이가 주어진다. 절단기의 높이를 설정하면 절단기 높이 이상의 나무들이 잘리며, 이때 절단기의 최대 높이를 구하는 것이다. (N ≤ 1,000,000) (M ≤ 2,000,000,000) (각 나무의 높이 ≤ 1,000,000,000)
[먼저, 이 문제를 푸는 가장 기본적인 방법을 살펴보자. (브루트 포스 알고리즘)] N이 최대 100만이고 각 나무의 높이는 최대 10억이다. 따라서, 10억 이하의 높이가 답의 후보가 될 수 있으며 이를 하나씩 살펴보며 답을 구할 수 있다. 이렇게 했을 때 후보 1개당 N개의 나무들을 살펴봐야 하므로 시간 복잡도는 $O(10^9 \cdot N)$이 나오게 된다. 하지만, 이는 문제에서 요구한 시간 복잡도를 만족하지 못하므로 다른 풀이를 떠올려야 한다.
[더 효율적으로 살펴보는 방법을 찾아보자. (파라매트릭 서치)] 위의 브루트 포스 알고리즘에서 살펴 봤듯이 답은 0이상 10억 이하의 수라는 것이다. 그리고 우리가 구해야 하는 것은 답의 최대 값(높이) $k$을 구하는 것이다. 10억 이하의 자연수에 대해서 답이 될 수 있으면 α, 그렇지 않으면 β로 나타내면 다음과 같은 형태이다. 이와 같은 형태가 나오는 이유는 절단기의 높이를 낮추면 가져갈 수 있는 양은 더 많아지기 때문이다. 이제 우리는 가장 오른쪽 α의 인덱스를 구하면 되는 것이다. 이는 위에서 살펴봤듯이 이분 탐색(파라매트릭 서치)을 통해서 수행할 수 있다. 살펴 볼 범위의 크기는 최대 10억이고 한 번 살펴볼 때 N개의 나무를 살펴봐야 하므로 시간 복잡도는 $O(N \cdot log_2 10^9)$이다. 참고로, $log_2 10^9$은 약 30이므로 문제에서 요구하는 시간 복잡도를 만족한다.
위 문제에 대한 파라매트릭 서치 코드를 구현하면 아래와 같다.
이 문제는 배열을 탐색하는 것이 아닌 수의 범위를 배열처럼 취급하여 탐색한다는 점을 주의하자!
정리하면, 파라매트릭 서치는 답의 후보에 대해서 탐색하여 답의 최댓값 또는 최솟값을 구하는 알고리즘이다.
단, '답이 가능한가'에 대한 형태가 위에서 살펴봤듯이 어떤 수를 기준으로 명확히 나누어져야 사용할 수 있다.
최솟값(맨 왼쪽 β)을 구하는 것은 맨 오른쪽 α의 인덱스를 구한 후에 +1을 해주면 된다.
![[11강] 이분 탐색 알고리즘](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJfaba%2FbtrUuYtKwps%2FByLCSAEfCVxW1F8kqCXInk%2Fimg.png)
