Binary Search 정리, 이해 및 예제

개념 [Concept]

수학에서 정확한 해를 구할 수 없는 문제의 근사해를 구하기 위해 사용되는 이분법(Bisection Method)이 Computer Science의 Bineary Search 와 매우 유사하다.

---

Case 1 - Linear 한(즉, O(N)이 걸리는) 알고리즘으로는 해결이 불가능한 경우.

• Binary Search 기법을 이용하여, $ O(log_{2}N) $ 의 시간 복잡도를 얻을 수 있다.

---

Case 2 - 자명한 해를 구할 수 없고, 주어진 허용 오차 안에서 근사해를 구해야 하는 경우.

• 구간 $ [low, high] $ 안에서 어떠한 조건을 만족하는 해를 구한다고 하자.
• 해가 범위 안에 무조건 존재한다고 가정하면, 첫 수행에 발생 가능한 최대 오차는 $ |high-low| $ 이다.
• Binary Search 알고리즘은 반복문이 진행됨에 따라 최대 오차가 절반씩 줄어들게 한다.
• 반복문을 100번만 수행해도 절대 오차는 최대 $ \frac{|high-low|}{2^{30}} $ 이 되므로 $ |high-low| $ 가 $10^{x}$ 미만의 수라면, 오차는 항상 $10^{x-30}$ 보다 작을 것이다.

※ 때로는 수식을 풀어 접근하는 것이 더 빠르고 효율적일 수 있음을 잊으면 안 된다. ※

---

주의점

• 이분법 풀이와 접합한 반복문 불변식
• 반복문 불변식을 만족하며 모든 해를 고려할 수 있는 초기 범위 설정

---

Ex : 단변수 다항 방정식의 수치적 해

// 단일 변수 다항식의 계수가 주어질 때 미분식의 계수를 반환한다.
    vector<double> differentiate(const vector<double>& poly);
    // 1차 혹은 2차 방정식을 푼다.
    vector<double> solveNaive(const vector<double>& poly);
    // 인자 x와 단일변수 다항식 f()의 계수가 주어질 때, f(x)를 반환한다.
    double evaluate(const vector<double>&poly, double x);
    // 해의 범위 [-L, L]
    const double L = 25;
    // 방정식의 근을 반환
    vector<double> solve(const vector<double>& poly)
    {
        // n차 방정식
        int n = poly.size() - 1;

        // 탈출 조건 (1, 2차 방정식은 solveNaive로 풀 수 있음)
        if(n <= 2)
            return solveNaive(poly);

        // 미분한 n-1차 방정식
        vector<double> derivative = differentiate(poly);   
       
        // Recursively Get n-1차 Solutions
        // sols는 poly의 근사해를 구하기 위한 극점의 x축 좌표
        vector<double> sols = solve(derivative);           

        // 양 끝단 좌표 추가 해줌. insert는 argument iterator의 앞단에 추가.
        sols.insert(sols.begin(), -L-1);
        sols.insert(sols.end(), L+1);
        vector<double> ret;

        // 각 구간의 부호가 다르면 반드시 1개 이상의 해를 가지고 있을 것이므로 이분법으로 풀이
        // y2는 항상 양수라는 반복문 불변 조건을 세우고, 100번의 반복문을 통해 충분한 허용오차를 보장한다.
        for(int i=0; i+1<sols.size(); i++)
        {
            double x1 = sols[i], x2 = sols[i+1];
            double y1 = evaluate(poly, x1), y2 = evaluate(poly, x2);

            if(y1*y2>0) continue;
            if(y1 > y2) { swap(y1, y2); swap(x1, x2); }

            for(int iter=0; iter<100; iter++)
            {
                double mx = (x1+x2)/2;
                double my = evaluate(poly, mx);
                if(y1*my > 0) {
                    y1 = my;
                    x1 = mx;
                }
                else {
                    y2 = my;
                    x2 = mx;
                }
            }
            ret.push_back((x1+x2)/2);
        }
        sort(ret.begin(), ret.end());
        return ret;
       
    }