Binary Search, Paramametric Search

이분 탐색 (Binary Search)

이분 탐색은 이름 그대로 탐색 알고리즘의 종류이다.
포인트는, “필요 없는 부분은 쳐다보지 않아” 시간을 줄인다.

주요 조건으로는, 정렬이 되어있어야 한다.

보통 정보들은 정렬이 되어 있지 않기 때문에, 입력을 받고 정렬을 해주어야 하는데, 이 경우 정렬 알고리즘으로 O(logN)이 소요된다.

(필자는 주로 <algorithm>의 sort 를 사용함)

따라서, 하나씩 다 확인해 보는 기존의 탐색 알고리즘 O(N)을 O(logN)으로 줄이면,
전체 O(logN)으로 탐색을 할 수 있다.

알고리즘의 핵심은, “정렬 기준과 중앙 기준값”을 잘 설정해 주는 것이다.

보통의 이분 탐색 문제에서는 정말 중앙(middle = left + right / 2)을 고르면 된다.

1 2 3 4 5 6 에서 5를 탐색하는 알고리즘을 짜자. (정렬되어있음)
기존 1 ~ 6 중 중앙인 3을 선택한다.
찾고자 하는 5 는 3 보다 크기 때문에, 탐색 범위를 4 ~ 6 으로 좁힌다.
우리는 범위 1 ~ 3 을 생각할 필요가 없다! (시간복잡도 감소)

단계가 총 $log_2(N)$ 개 이므로, O(logN)의 시간복잡도로 탐색이 가능하다.

파라매트릭 서치 (Parametric Search)

이분 탐색과 매우 유사한 파라매트릭 서치 (Parametric Search) 도 함께 알아보자.
이는 이분 탐색을 응용하여 최솟값이나 최댓값을 구하는 알고리즘이다.

이분 탐색의 알고리즘과 같이 범위를 기준 중앙값에 따라 logN으로 좁혀 간다.
단, 이분탐색은 주로 작다/크다 를 확인하는 반면, 파라매트릭 서치에서는 주로 가능하다/불가능하다 를 확인한다. ( <- 파라매트릭 서치의 핵심 )
가능한 것들만을 모은다면, 그 중 최소/최대 값이 가능한 최소/최대 값이 되는 것이다.

이분탐색과 파라매트릭 서치 문제에서는
어떠한 방식으로 정렬을 하고,
어떠한 방식으로 기준 중앙값을 놓고,
그 기준 중앙값과 찾고자 하는 경우를 어떻게 비교해 가며 범위를 좁혀나갈 것인지가
핵심 포인트라고 생각한다.