50. Pow(x, n)

Implement pow(x, n).

一刷
题解：
使用二分法求实数幂。注意，需要考虑n为负数的情况
Time Complexity - O(logn)， Space Complexity - O(1)。

public class Solution {
    public double myPow(double x, int n) {
        if(x==0) return x;
        if(n==0) return 1;
        double half = myPow(x, n/2);
        if(n%2 == 0){
            return half*half;
        }
        else if(n>0) return half*half*x;
        else return half*half/x;
    }
}

二刷
注意，不能直接return myPow(x, n/2)*myPow(x, n/2), 这样会超时，因为函数调用了两遍