50

這一題需要考慮n>0, n=0, n<0的情況。

如果直接用O(n)的演算法來做，有一些Leetcode上的test case會exceed time limit。

public class Solution {
    public double myPow(double x, int n) {
        /*
        n can be positive, 0, negative
        ex: x=3, n=9
        1 -> 4, 2-> 2, 3->1 ===> 最接近的是2^3
        ans = x
        in loop: 3*3, 3^2 * 3^2, 3^4 * 3^4
        最後計算: 3^8 * 3
        */
        if(n==0)
            return 1.0;
        int powOf2 = 0;
        int nCopy = Math.abs(n);
        while(nCopy > 1){
            nCopy /= 2;
            powOf2++;
        }

        double ans = x;
        for(int i=0; i<powOf2; i++){
            ans *= ans;
        }

        for(int i=0; i<(Math.abs(n)-Math.pow(2,powOf2)); i++){
            ans*=x;
        }

        return n > 0 ? ans : 1/ans;

    }
}

所以還是要用二分法的方式來做。只是要如何優雅地結合二分過後的計算結果，還是要用遞迴的方式。

class Solution {  
public:  
    double myPow(double x, int n)   
    {  
        return Pow(n < 0 ? 1 / x : x, n);  
    }  
private:  
    double Pow(double x, int n)  
    {  
        if(n == 0)                  return 1;       // special case  
        else if(n == 1 || n == -1)  return x;       // base case  
        double half = Pow(x, n/2);  
        return half * half * (n % 2 == 0 ? 1 : x);  
    }  
};