50. Pow(x,n)

Implement pow(x,n), which calculates x _raised to the power _n(x^n).

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

Explanation:
 2^-2 = 1/2
1/2^2 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0

• n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Thoughts:

1. halve the exponent, squae the input

2. flip the sign of exponent if negative, then inverse the base

   1. if the exponent == INT_MIN; change it to INT_MAX,

      1. if x is negative, change x to -x before finally inverse it

Sequential Search: T: O(n)

class Solution {
    public int findPeakElement(int[] nums) {
             for(int i = 1; i < nums.length; i ++)
                {
                    if(nums[i] < nums[i-1])
                    {// <
                        return i-1;
                    }
                }
            return nums.length-1;
    }
}

class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if (n<0){
            if(n == Integer.MIN_VALUE){
                n = Integer.MAX_VALUE;
                if(x<0) x = -x;
            } 
            else{
                n = -n;
            }

            x = 1/x;
        }

        return n%2==0?myPow(x*x,n/2):x*myPow(x*x,n/2);
    }
}