이진탐색과 파라메트릭서치 차이점

파라메트릭서치(Parametric Search)는 파라미터(매개변수)에서 파상된 단어입니다.

그리고 이진탐색(바이너리서치)와 파라메트릭 서치는 어떻게 다른지 한번 살펴봅시다.

이진탐색(Binary Search)

이진탐색의 경우 정렬된 시퀸스에서 중간인 지점을 서치하면서 답을 찾아나가는 것으로 O(logN)의 복잡도를 보이는 것으로 알려져 있습니다.

파라메트릭서치(Parametric Search)

파라메트릭 서치는 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것이라 합니다. 그리고 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있습니다.

그러니까 단순히 어떤 값을 찾는 것과 특정한 조건을 만족하는 것을 찾아내는 차이라고 보시면 됩니다. 여기까지 보면 유사한점이 많네요 좀더 깊게 설명을 해보겠습니다.

이진탐색과는 다르게 파라메트릭 서치는 주어진 것이 값이 아니라 범위이기 때문에 특정한 상활을 최적화시키는 문제를 풀 때 용이하다는 장점을 가집니다. 문제를 풀때 파라메트릭 서치를 사용하면 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 되어 문제 접근이 상당히 용이해집니다.

최적화 문제를 결정 문제로 바꾸어 푼다는 말은 주어진 상황에서 최솟값, 최댓값 등의 특정 값을 구하는 문제를 특정 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바뀐다는 의미입니다.

이를 다시 정리하면 어떤 값을 찾는 것과 어떤 조건을 만족하는 값을 찾아가는 과정의 차이라고 보시면 됩니다. 즉 이진탐색과 파라메트릭서치는 대척되거나 반대되는 개념이 아닙니다.