1.题目描述
描述
实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）
数据范围：
要求：空间复杂度 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.运行结果
成功通过！
