50. Pow(x, n). O(logN)​ Sol

Move the dichotomy of the official solution , The time complexity is O(log)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

​​​​class Solution {
public:
    double fastPow(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
};

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

Approach 2: Fast Power Algorithm Recursive

Intuition

Assuming we have got the result of , how can we get  ? Obviously we do not need to multiply  for another  times. Using the formula , we can get  at the cost of only one computation. Using this optimization, we can reduce the time complexity of our algorithm.

Algorithm

Assume we have got the result of , and now we want to get the result of . Let A be result of , we can talk about  based on the parity of n respectively. If n is even, we can use the formula  to get . If n is odd, then . Intuitively, We need to multiply another xx to the result, so . This approach can be easily implemented using recursion. We call this method "Fast Power", because we only need at most O(log⁡n) computations to get .