Sqrt LeetCode

原来没觉得这道题难，看来第一遍刷leetcode没有把testcase设计的非常精准。现在我重新写出现了两个问题。 第一个问题就是要判断数字是否大于1，因为0和1这两个case比较特殊。
第二个问题就是涉及到越界的问题。
我倾向于第二种，就是最后数据类型转换的时候要小心。

第一种写法
public int sqrt(int x) {
        double diff = 0.01;     // 误差
        int low = 0;
        int high = x;
       
        while(low <= high){
            // 注意越界！所以用double来存
            double mid = low + (high-low)/2;
            if(Math.abs(mid*mid-x) <= diff){
                return (int)mid;
            }else if(x > mid*mid+diff){
                low = (int)mid+1;
            }else if(x < mid*mid-diff){
                high = (int)mid-1;
            }
        }
       
        // 当找不到时候，这是low,high指针已经交叉，取较小的，即high
        return high;
    }

第二种写法：
 public int sqrt(int x) {
        if (x==0 || x==1) return x;
        long low = 1;
        long high = x;
        long mid = 0;
     
        while (low <= high){
            mid = (low + high)/2;
            Long upper = mid + 1;
            if (mid*mid <=x && upper*upper >x){
                break;
            }
            if (mid*mid > x){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    return new Long(mid).intValue();
    }

Newton Method.

public int sqrt(int x) {
        if (x==0) return 0;
        double lastY = 0;
        double y=1;
        while (y != lastY) {
            lastY = y;
            y = (y+x/y)/2;
        }
        return (int)(y);
    }