【LeetCode】69.x 的平方根

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根。

x 保证是一个非负整数。

案例:1:
输入: 4
输出: 2
案例2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于我们想返回一个整数,小数部分将被舍去。

代码

一个数 x 的开方 sqrt 一定在 0 ~ x 之间,并且满足 sqrt == x / sqrt 。可以利用二分查找在 0 ~ x 之间查找 sqrt。

public int mySqrt(int x) {
    if(x <= 1) return x;
    int l = 1, h = x;
    while(l <= h){
        int mid = l + (h - l) / 2;
        int sqrt = x / mid;
        if(sqrt == mid) return mid;
        else if(sqrt < mid) h = mid - 1;
        else l = mid + 1;
    }
    return h;
}

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/problem/582.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。

最后修改:2018 年 03 月 18 日 07 : 21 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论