Pow(x, n)

Implement pow(x, n).
Solution: 
二分法， 用递归来解比较容易理解，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，算法复杂度是O(logn)。

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