이분 탐색 | Parametric Search 에 대한 이론 비교

Binary Search | 이분 탐색 = 이진 탐색 = 이분 검색

• 정렬된 데이터에서 특정 값을 찾기 위해 (특정 범위)를 절반으로 줄여나가면서 중앙값과 비교해가며 빠르게 탐색하는 기법이다.

이분 탐색 설명

---

Parametric Search | 파라메트릭 서치

• 이러한 이분 탐색의 응용을 Parametric Search 라고 부르다.
• 최적화 문제를 결정 문제로 환원하면 더 쉽게 풀 수 있다면 고려해봐라

(1) 예, 아니오 판단할 함수 만들고

(2) 판단 함수를 활용하여, 이분 탐색 범위를 좁혀가면서 타겟값을 구하는 거다.

1) 최적화 문제 : 여러 해답 중 기준에 따라 최소, 최대값 등을 구하는 문제
            : f(i) = 1 이 되는 i의 최솟값을 구하라
2) 결정 문제 : 예 아니오로 답할 수 있는 문제
              : 어떤 i에서 f(i) = 1 이 되는가 ?