1.题目描述

描述

实现函数 int sqrt(int x).

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

数据范围：

−

0<=x<2^{31}-1

$0 <= x < 2^{31} - 1$

要求：空间复杂度

(

)

O(1)

$O (1)$ ，时间复杂度

(

)

O(logx)

$O (l o gx)$

2.算法设计思路

1）初稿

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

总体思路：二分搜索
1.二分搜索，首先要有一个初始区间，例如

[

]

[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;
    }
};