Parametric Search (파라메트릭 서치)

가능한 해 구간에 대해서 이분탐색을 하는 방법을 'Parametric Search'라고 한다.
흔히 가능한 해의 최솟값이나 최댓값을 구하라는 문제에서 사용할 수 있는 기법이다.
Optimization Problem을 Binary Search + YES/NO Problem으로 바꾸어 푸는 방법이다.
Parametric Search를 사용하기 위해서는 몇 가지 조건이 있다.

1. 가능한 해의 영역이 연속적이어야 한다.
예시로 가능한 해의 최솟값을 찾는 문제에서 설명하면

가능한 해 구간 [ L , R ]에서 우리가 정한 답 X를 기준으로 2가지 경우가 있다.
1) X가 해를 만족할 때, [ X , R ]에 대해서도 모두 해를 만족해야 한다.
따라서 X의 탐색 범위를 해 구간 [ L , R ]에서 [ L , X )로 줄여볼 수 있다.
2) X가 해를 만족하지 않을 때, [ L , X ]에 대해서 모두 해를 만족하지 않는다.
따라서 X의 탐색 범위를 해 구간 [ L , R ]에서 ( X , R ]로 줄여볼 수 있다.

2. YES/NO Problem이 기존의 Optimization Problem을 풀 때에 비해 쉽게 풀린다.
기존의 문제에 비해 시간복잡도가 낮은 다항 시간 알고리즘으로, 결정한 답 X에 대해 해를 만족하는지 확인할 수 있어야 한다.