[leetcode]Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

【注意】：

1. 本题int类型可能会溢出，因此不能用乘法运算，应尽量用除法。

2. 绝大多数数字都不是可开方的，该如何得到比较近的结果呢？

算法思路：

思路1：顺序遍历肯定不需要试了，二分查找比较靠谱。二分法在数值计算中非常常见，需要熟练掌握。

代码如下：

public class Solution {
    public int sqrt(int x) {
        if(x <= 1) return x == 0 ? 0 : x;
        int l = 1, r = x /2 + 1 ;
        while(l <= r){
            int mid = (l + r) / 2;
            if(mid <= x / mid && (mid + 1) > x / (mid + 1)){
                return mid;//这里用的很巧妙
            }else if(mid > x / mid){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return 0;
    }
}

思路2：牛顿迭代法；比较高大上，详细分析过程请戳这里。

代码如下：　　

 1 public int sqrt(int x) {
 2     if (x == 0) return 0;
 3     double lastY = 0;
 4     double y = 1;
 5     while (y != lastY)
 6     {
 7         lastY = y;
 8         y = (y + x / y) / 2;
 9     }
10     return (int)(y);
11 }

这道题出的很好