Binary1

发表于 更新于 分类于 ，

题目描述 [原题链接][https://leetcode-cn.com/problems/sqrtx/]

实现int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

算法

(二分) O(logx)
二分出最大的 y，满足y^2<=x,

则 y就是答案。

​ 输入x，设置左边界为0，右边界为x，计算出mid ，int mid = l + (r-l)/2，用两个变量分别存储x/mid，x/(mid+1)的值，通过与这两个值比较更新左右区间边界，当s>mid&&ss<mid+1时说明此时的mid就是我们要找的数，s>mid更新左区间，s<mid更新右区间，相等的时候该s就是要找的目标值。按照这个流程实现就可以解决问题了。

时间复杂度分析：二分的时间复杂度是 O(logx)。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public:
    int mySqrt(int x) {
        int l = 0;
        int r = x;
        if(r==1||r==0)return x;
        while(r>=l){
            int mid = l + (r-l)/2;
            int s = x/mid;
            int ss = x/(mid+1);
            if(x/s==s)return s;
            if(s>mid&&ss<mid+1)return mid;
            if(s>mid)l=mid+1;
            if(s<mid)r = mid-1;
        }
        return 0;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        if(r==1||r==0)return x;
        while(r>=l){
            int mid = l+(r-l)/2;
            int s = x/mid;
            int ss = x/(mid+1);
            if(mid==s)return s;
            if(s>mid&&ss<mid+1)return mid;
            if(s>mid)l=mid+1;
            if(s<mid)r=mid-1;
        }
        return 0;
    }
}