题目：

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:
Input: 2.00000, 10
Output: 1024.00000

Example 2:
Input: 2.10000, 3
Output: 9.26100

Example 3:
Input: 2.00000, -2
Output: 0.25000

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2³¹, 2³¹ − 1]

思路：

这道题可以采用二分法来做。首先观察n。

• 如果n%2为0，返回x/2 * x/2。
• 如果n%2为1，返回x/2 * x/2 * x。
• 如果n为0，则返回1。因为任何数除了0之外的0次方全为1.
  举例：
  5⁷按照以上原则分解
  5³ * 5³ * 5
  5¹ * 5¹ * 5 * 5¹ * 5¹ * 5 *5
  5⁰ * 5⁰ * 5 * 5⁰ * 5⁰ * 5 * 5 * 5⁰ * 5⁰ * 5 * 5⁰ * 5⁰ * 5 * 5 * 5 = 5⁷
  注意：
  如果n为负数，首先按照n的绝对值计算xⁿ再用1除以xⁿ，即最终结果。

代码：

/**
     * Calculating pow(x, n).
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        if(x == 0){
            return 0.0;
        }
        if(n > 0){
            return Pow(x, n);
        }else{
            return 1 / Pow(x, -n);
        }
    }
    
    private double Pow(double x, int n){
        if(n == 0)
            return 1;
        double mid = Pow(x, n/2);
        if(n%2 == 0){
            return mid * mid;
        }else{
            return mid * mid * x;
        }
    }