Leetcode - Divide Two Integers || pow(x, v) || Sqrt(x)

这三个题都是实现一种操作，且思想都是二分法，具体实现有些许不同，可对照着看
Divide two integers without using multiplication, division and mod operator.[Thoughts]: 通过减去divisor计算count

public class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        sign = dividend < 0 ? 0-sign : sign;
        sign = divisor < 0 ? 0-sign : sign;
        
        long a = dividend;//必须要把dividend cast成long，因为int类型最小值是-214748364(-2^31),若把这个数用abs方法转化成正数的话会溢出 
        long b = divisor;
        a = Math.abs(a);
        b = Math.abs(b);
        
        int count = 0;
        while(a>=b){
            long temp = b;
            int c = 1;
            while(a>=temp){
                a = a - temp;
                count = count + c;
                temp = temp*2;
                c = c*2;
            }
        }
        return sign<0 ? 0-count : count;
    }
}

Implement pow(x, n).
[Thoughts]: 递归，记得处理n<0的情况

public class Solution {
    public double pow(double x, int n) {
        if(n==0) return 1;
        double d = pow(x, Math.abs(n/2));
        double res = n%2==0 ? d*d : d*d*x;
        return n>0 ? res: 1/res;
    }

}

Implement int sqrt(int x).
Compute and return the square root of x.
[Thoughts]:通过找mid，赤裸裸的二分

public class Solution {
    public int sqrt(int x) {
        long high = (long) x, low =0, mid;
        
        while(low<=high){
                mid = (low+high)/2;
                long sqr = mid*mid;
                if(sqr == x) return (int) mid;
                else if(sqr > x) high = mid-1;
                else if(sqr < x) low  = mid+1;
        }
        
        return (int) high;
    }
}

这个题若是指定double了，那就是在问牛顿迭代了：

double square_root(double a, double epsilon){
    if(a+0.0==0) return 0;
    double x = 1;
    while(Math.abs(x*x-a)>epsilon){
        x = (x+a/x)/2;
    }
    return x;
}