1.题目描述
描述
实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）
数据范围： 0 < = x < 2 31 − 1 0<=x<2^{31}-1 0<=x<231−1
要求：空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( l o g x ) O(logx) O(logx)
2.算法设计思路
1）初稿
关键信息：所求x的平方根是一个向下取整的整数。
总体思路：二分搜索
1.二分搜索，首先要有一个初始区间，例如 [ 1 , x ] [1,x] [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.运行结果
成功通过！
结束语：
今天的分享就到这里啦，快来加入刷题大军叭！
👉点击开始刷题学习👈
感谢阅读
CSDN话题挑战赛第2期
参赛话题：学习笔记