8.9 分治 pow, sqrt

to do

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)

1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5.    do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)

• 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
• ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。
• 算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

11.1] Pow(x, n)

careful with what the smallest subproblems have to be in order to work. Used myPowR to calculate the power to the 2 but will stuck in loop if didn't add base case if n==1 return x.
Also note to take care of negative n cases.

    double myPowR(double x, int n) {
        if (!n) return 1;
        // if (n==1) return x;
        int n_sub = n/2;
        double inner = myPowR(x, n_sub);
        return n%2 ? x*inner*inner : inner*inner;
    }
    
    double myPow(double x, int n) {
        bool neg = n<0;
        return neg? 1/myPowR(x, abs(n)) : myPowR(x, abs(n));
    }

11.2] Sqrt(x)

take care of special cases. Careful not to overflow: use divide instead of multiple in order to compare.

    int mySqrt(int x) {
        if (x<2) return x;
        int mid;
        // took care of 0 case because can't divide by 0
        for (int l=1, r=x; l<=r; ) {
            mid=(l+r)/2;
            if (mid==x/mid || (mid<x/mid && (mid+1)>x/(mid+1))) break;
            if (mid>x/mid) {
                r=mid-1;
            } else {
                l = mid+1;
                
            }
        }
        
        return mid;
    }