Parametic Search

결정 문제를 최적화 알고리즘으로 변환하는 알고리즘 설계 기법 중 하나

• 이분법 : Bisection Method
• 결국은, 이진 탐색 : binary Search

 

Decision Problem -> Optimization Problem

이분법

- 수학적으로 방정식의 근(root)을 계산할 때 사용한 이진 탐색 알고리즘
    - Root-Finding Algorithm
- 근이 반드시 존재하는 폐구간에서, 폐구간의 범위를 재귀적으로 좁혀 나감

문제 LeetCode 278. First Bad Version

- n개의 제품이 있을 때,

- k번 이후에는 불량

- k번째를 찾는 문제

- 결정 문제 API : bool isBadVersion

- 불량인지 확인해 주는 api를 제공함

- api를 적게 호출할수록 유리함

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int low = 1;
        int high = n;
        while(low<high) {
            int mid = low + (high-low) / 2;
            if (isBadVersion(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}