Leetcode/各大家 -- 50.pow(double x,int n) Binay Search

Pow(x, n) - Binary Search

• Difficulty: Medium

Implement pow(x, n).
Ex: 9^-3  = 1/27
2^-2 = 1/4 // -2%2 = 0
2^-3 = 1/8 // -3%2 = 1

company： LinkedIn, Google, Bloomberg, Facebook
https://leetcode.com/problems/powx-n/

思路：每次将指数n/2，然后 n分三种情况： 
1.等于1，则x*res*res 2.等于0 则res*res 3.负数，则res*res/x
关键词： Divide and Conquer （Recurrsion）
Time & Space complexity: O(log n) O(1)

public class Solution {
    public double myPow(double x, int n) {
        if (x == 0)return 0;
        if (n == 0)return 1;// base case: x^0 = 1
        double res = myPow(x, n/2);
        if(n%2 == 0){//-2%2=0
            return res*res;
        }else if(n%2 == 1){
            return res*res*x;
        }else {//-1 here, -3%2=-1
            return res*res/x;
        }
    }
}