LeetCode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

【题目分析】

这道题目要求求一个整数的开方数，而且结果是返回一个整数。

【思路】

一个整数x的开方整数是什么呢？假设结果是y，那么y*y <= x。

因为肯定存在y<=x/2关系，我们从1开始向后遍历，找到y*y = x或者刚好y*y > x的前一个数。

　　　这样遍历的缺点是时间复杂度高，而且可能存在overflow的情况，即存在y*y > Integer.MAX_VALUE的情况

采用二分查找的方法

　　　二分查找方法在1~x/2的范围内每次取中间值进行判断，然后找到我们要的值返回。因为y*y <= x，所以当中间值mid > x/mid时mid肯定比y大，此时改变查找的右边界。否则的话，此时的mid可能是我们要的结果，我们看一下(mid+1)是否也可能满足，如果不满足的话此时的mid就是我们要找的结果，如果mid+1也满足的话，改变查找的左边界继续。

牛顿法

【java代码】

二分查找：

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         if (x <= 1) return x;
 4         
 5         int left = 1, right = x/2;
 6         while(left <= right) {
 7             int mid = left + (right - left)/2;
 8             if(mid > x/mid) {
 9                 right = mid - 1;
10             }
11             else {
12                 if((mid + 1) > x/(mid + 1))
13                     return mid;
14                 left = mid + 1;
15             }
16         }
17         return 0;
18     }
19 }

牛顿法：

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         if (x <= 1) return x;
 4         
 5         double last = 0, res = 1;
 6         while(last != res) {
 7             last = res;
 8             res = (res + x/res)/2;
 9         }
10         return (int)res;
11     }
12 }

可见牛顿法的收敛速度是相当快的！牛顿法在机器学习中也是一种找最优化值的有效的方法。

上述的步骤中我们判断两个double值是否相等，java是如何进行判断的呢？应该是两个值的差小于某个精度的时候就判为相等。