69.Sqrt(x)

题目链接：https://leetcode.com/problems/sqrtx/description/

题目大意：实现求平方根。

法一：直接库函数。代码如下（耗时39ms）：

1 public int mySqrt(int x) {
2         double res = Math.sqrt(x);
3         return (int)Math.floor(res);
4     }

View Code

法二：逐一判断，用i*i<x来判断。代码如下（耗时72ms）：

 1     public int mySqrt(int x) {
 2         if(x == 0 || x == 1) {
 3             return x;
 4         }
 5         int i = 0;
 6         for( ; i <= x / 2; i++) {
 7             long tmp = (long)i * (long)i;
 8             if(tmp > x) {
 9                 return i - 1;
10             }
11             else if(tmp == x) {
12                 return i;
13             }
14         }
15         return x / 2;
16     }

View Code

法三（借鉴）：用二分，并没有快很多啊。代码如下（耗时44ms）：

 1     public int mySqrt(int x) {
 2         int left = 1, right = x;
 3         if(x == 0 || x == 1) {
 4             return x;
 5         }
 6         while(true) {
 7             int mid = left + (right - left) / 2;
 8             //如果mid * mid > x，则令right = mid - 1，因为值大了，而这里使用mid > x / mid的方式，是为了防止mid * mid过大，越了int的界限
 9             if(mid > x / mid) {
10                 right = mid - 1;
11             }
12             //如果mid * mid < x
13             else {
14                 //如果(mid + 1) * (mid + 1) > x，则说明x的平方根是mid和mid+1中间的值，则取小者mid 
15                 if(mid + 1 > x / (mid + 1)) {
16                     return mid;
17                 }
18                 left = mid + 1;
19             }
20         }
21     }

View Code

法四（借鉴）：牛顿迭代法，http://blog.csdn.net/wumuzi520/article/details/7026808，据说是专门解sqrt的。代码如下（耗时46ms）：

1     public int mySqrt(int x) {
2         long tmp = x;
3         while(tmp * tmp > x) {
4             tmp = (tmp + x / tmp) / 2;
5         }
6         return (int)tmp;
7     }

View Code