50. Pow(x, n)

We can use binary search using recursion to do it, seperate the case where the expression could be expressed as half*half or half*half*itself. But in real life we don't advise recursion..Also pay attention to over flow.

Run Time: log(N)

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
            return 1/helper(x,-n);
        }
        else{
            return helper(x,n);
        }
    }
    public double helper(double x,int n){
        if(n == 0){
            return 1;
        } 
        double v = helper(x, n/2);
        if(n%2 == 0){
            return v*v;
        }
        else{
            return v*v*x;
        }
    }
}

Other Solutions(General Way) http://blog.csdn.net/linhuanmars/article/details/20092829

Iterative Solution 比如9次方 1001 = 8次方 和 1次方 结合 keep a sequence of x, x^2,x^4,x^8 从后面一直扫到前面 如果bit的位是1 乘以相应的x的值 (下面的代码可能没有overflow)

public class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        //to change the type of the n
        long num = Math.abs((long)n);
        while(num > 0){
            if((num & 1) == 1)res = res * x;
            num = num >> 1;
            x = x * x;
        }
        return (n > 0)? res : 1/res;
    }
}

29. Divide Two Integers

比较直接的方法是用被除数一直减去除数，直到为0。这种方法的迭代次数是结果的大小，即比如结果为n，算法复杂度是O(n)。

那么有没有办法优化呢？ 这个我们就得使用位运算。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度为O(logn)注意几个边界 最大最小 除数是0

public class Solution {
    public int divide(int dividend, int divisor) {
        int res = 0;
        if(divisor == 0 ) return dividend > 0? Integer.MAX_VALUE: Integer.MIN_VALUE;
        //if it is the min value then dealing with it directly is not possible(use abs)
        if(dividend == Integer.MIN_VALUE)  
        {  
            dividend += Math.abs(divisor);  
            if(divisor == -1)  return Integer.MAX_VALUE;
            res++;  
        }
        if(divisor == Integer.MIN_VALUE)return res;

        //The unsigned right shift operator ">>>" shifts a zero into the leftmost position
        //if the signed bit are different then it is negative 
        boolean isNeg = (dividend ^ divisor) >>> 31 == 1;  

        dividend = Math.abs(dividend);  
        divisor = Math.abs(divisor);  

        int digit = 0;  
        //first move to the largest possible
        while(divisor <= (dividend >> 1))  
        {  
            divisor <<= 1;  
            digit++;  
        }  
        //each time subtract and compute the result
        while(digit >= 0)  
        {  
           if(dividend >= divisor)  
          {  
            res += 1 << digit;  
            dividend -= divisor;  
          }  
          divisor >>= 1;  
          digit--;  
        }  
        return isNeg?-res:res;  
    }
}

69. Sqrt(x)

public class Solution {
    public int mySqrt(int x) {
        if(x == 0)return 0;
        int start = 1;
        int end = x - 1;
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            if(x/mid < mid){
                end = mid;
            }
            else if(x/mid > mid){
                start = mid;
            }
            else return mid;
        }
        return start;
    }
}

367. Valid Perfect Square

二分边界跳跃条件和while里面的判断有关

public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num == 0 ||num == 1)return true;
        //use long here to avoid overflow
        long start = 1;
        long end = num;
        while(start + 1 < end){
            long mid = start + (end - start)/2;
            long val = mid * mid;
            if(val > num){
                end = mid;
            }
            else if(val < num){
                start = mid;
            }
            else{
                return true;
            }
        }
        return false;
    }
}