题目描述：

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

 

直觉解法：

从1到x，判断结果i 使得i*i <= x && (i+1)*(i+1) > x

并且把0 1作为特殊情况分开判断：

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

 

当x值特别大时运行时间长，正确解法：

使用二分查找，从1到x 查找left的平方小于等于x;right的平方大于x

 1 class Solution {
 2     public int mySqrt(int x) {
 3         int l = 0, r = x, ans = -1;
 4         while (l <= r) {
 5             int mid = l + (r - l) / 2;
 6             if ((long) mid * mid <= x) {
 7                 ans = mid;
 8                 l = mid + 1;
 9             } else {
10                 r = mid - 1;
11             }
12         }
13         return ans;
14     }
15 }
16 
17 作者：LeetcodeFrom20210207
18 链接：https://leetcode-cn.com/problems/sqrtx/solution/69xde-ping-fang-gen-by-leetcodefrom20210-huk8/
19 来源：力扣（LeetCode）
20 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。