首页 > 代码库 > Sqrt(x)

Sqrt(x)

题目

Implement int sqrt(int x).

Compute and return the square root of x.

方法一

使用二分查找,注意int的边界问题,使用除法。
    public int sqrt(int x) {
        if (x  <= 1) {
            return x;
        }
        int start = 0;
        int end = x;
        while (start <= end) {
            int median = start + (end - start) / 2;
            int temp = x / median;
            if (temp == median) {
                return median;
            } else if(temp < median) {
                end = median - 1;
            } else {
                start = median + 1;
            }
        }
        return end;
    }


方法二

使用牛顿迭代法。
    public int sqrt(int x) {
        double pre;
        double cur = 1;
        do {
            pre = cur;
            cur = (pre + x /pre) / 2.0;
        }while(Math.abs(cur - pre) > 0.00000001);
        return (int) cur;
    }