求平方根（又是辛苦 debug 的一天）

作者：清风莫追

2022 年 10 月 05 日
湖南
本文字数：1468 字
阅读完需：约 5 分钟

个人主页：CSDN清风莫追
系列专栏：牛客刷题——数据结构与算法🔥 该专栏作为刷题笔记，持续更新中。
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

1.题目描述

描述

实现函数 int sqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： $0 < = x < 2^{31} - 1$

要求：空间复杂度 $O (1)$ ，时间复杂度 $O (l o g x)$

2.算法设计思路

1）初稿

关键信息：所求 x 的平方根是一个向下取整的整数。

总体思路：二分搜索 1.二分搜索，首先要有一个初始区间，例如 $[1, x]$ 。2.搜索时每次取区间的中点值 mid，看是否为 x 的平方根。3.若 mid 就为 x 的平方根，则返回 mid；否则，继续对 mid 左右两个区间进行二分搜索。

细节：1.判断一个数 mid 是否为 x 的平方根：mid 的平方等于 x；mid 的平方比 x 小，且 mid+1 的平方比 x 大。（注意是向下取整）2.对一个区间停止搜索的条件：搜到区间只剩下一个元素 3.当区间恰好剩两个元素而不能分为三部分：分别判断这两个元素是否为 x 的平方根

2）bug

在按照最初的算法设计思路编写完代码后，我并没有成功通过。

第一个问题：判断平方根在判断一个数 t 是否为 x 的平方根时，我使用t * t <= x && (t+1)*(t+1) >= x的方式，这样就存在一个漏洞，例如当 t 为 2 且 x 为 9 时，该表达式将返回true。

第二个问题：数据范围 x 是 int，但是 x 的平方就不是了，会溢出。干脆就不平方了，就比较x / t 与 t的大小。

第三个问题：0 作为除数从乘法改到除法，就要小心 0 了。

第四个问题：我真的二分了吗？就在我以为自己终于要过了的时候，报了个超时的错误。本来在二分搜索中，每次搜索后剩余区间都会缩小为原来的一半，而我没有写停止另一半搜索的判断，倒在了 x=21 亿这个测试数据上。

添加二分时丢掉一半区间的判断：如果一个区间的最大（小）值都比 x 的平方根小（大），就没必要继续搜索该区间了。

if((e+1) < x / (e+1) || (f > 1 && (f-1) > x / (f-1)))            return;

复制代码

小结写 bug 改 bug，bug 套 bug，好在“神龟虽寿，犹有竟时”，修修补补终于还是过了这一关。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

成功通过的 C++代码：

class Solution {  public:    //判断xsqrt是否为x的平方根    bool is_sqrt(int x, int xsqrt) {        int t = x / xsqrt;        int t2 = x / (xsqrt + 1);        if (t >= xsqrt && t2 < (xsqrt + 1)) {            return true;        }        return false;    }    //在【1，x】的区间中采用二分搜索x的平方根    void find(int x, int f, int e, int & result) {        if((e+1) < x / (e+1) || (f > 1 && (f-1) > x / (f-1)))            return;        if (e - f ** 0) {            if (is_sqrt(x, f)) {                result = f;            }            return;        }        if (e - f ** 1) {            if (is_sqrt(x, f)) {                result = f;            }            if (is_sqrt(x, e)) {                result = e;            }            return;        } 
        int mid = (f + e) / 2;        if(is_sqrt(x, mid)){            result = mid;            return;        }        find(x, f, mid - 1, result);        find(x, mid + 1, e, result);    }    //返回x的平方根    int sqrt(int x ) {        // write code here        if(x ** 0)            return 0;        int result = 0;        find(x, 1, x, result);        return result;    }};

复制代码

4.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/78a77b4b77cef73b0631a5189】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景

求平方根 （又是辛苦 debug 的一天）