算法22 Pow(x, n)

题目：Pow(x, n)，pow(x,n) 方法就是算 x 的 n 次方。
例1：
输入： 2.00000,10
输出： 1024.00000
例2：
输入： 2.10000,3
输出： 9.26100

思路：求x的n次方，首先n可能为0则值为1。n>0是时,例如x的5次方可以将xxxxx算法变成x²x²x，x的4次方就为x²*x²。当n<0,x取倒数,n取反，即和正的一致.这即可用到迭代的方式。具体如下。

代码：

public static double myPow(double x, int n) {
    //等于0返回1
    if(n == 0)
        return 1;
    //小于0
    if(n<0){
        n = -n;
        x = 1/x;
        //解决MIN_VALUE的问题
        if (n == Integer.MIN_VALUE) {
            n = Integer.MAX_VALUE;
            x *= x;
        }
    }
    //递归,注意对偶数和奇数的处理
    return (n%2 == 0) ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}

时间复杂度O（logn）空间复杂度O（logn）