50. Pow(x, n)

Implement pow(x, n).

S1: 逆向binary search O(logn)

注意n的奇偶，和corner case的处理

    double myPow(double x, int n) {
        if (x == 1) {
            return 1;
        }
        if (x == -1) {
            return n & 1? -1 : 1;
        }
        if (x == 0 || n == INT_MIN) { //防止 n=-n overflow
            return 0;
        }
        if (n < 0) {
            return myPow(1/x, -n);
        }
        double result = 1;
        while (n > 0) {
            if (n & 1) result *= x;
            x *= x;
            n /= 2;
        }
        return result;
    }

S2： recursion O(logn)

double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {  //没有处理INT_MIN overflow
            n = -n;
            x = 1/x;
        }
        return n % 2 == 0? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
    }

S3 避开n = -n潜在的overflow O(logN)

    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (x == 0 || x == 1) return x;
        double half = myPow(x, n / 2);
        double result = half * half;
        if (n & 1) {
            return n < 0? result / x : result * x;
        } 
        return result;
    }