题目

Implement int sqrt(int x).

Compute and return the square root of x.

分析

主要思想很简单，就用二分法。需要注意的是，当平方根不是整数时，需要向下取整。

实现

class Solution {
public:
    int mySqrt(int x) {
        return solve(x, 0, x);
    }
    int solve(int x, int start, int end){
        if(start>=end-1) return end*end==x ? end : start;
        long long mid = (start + end) / 2;
        if(mid*mid>=x) return solve(x, start, mid);
        else return solve(x, mid, end);
    }
};

思考

一开始使用二分搜索的方法写，默认了搜索空间是整数了，导致了一些问题。
后来想想，其实搜索空间还是实数空间，只是精度为1罢了。