Leetcode 69: sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

M1: 最暴力的解法：
直接遍历从 i=0-> i < x， 如果i * i > x，就直接跳出，  这样做的时间复杂度是O（i），对于大的数据会超时；

M2：二分法
其实这个题目是说 在0-X之间找一个值，使得 i*i = x， 其实是一种search类型的题目， 给定一个搜索范围找到某一个值，应该想到二分法的数值计算方法，只是这里的binary search 和之前做过的binary search不同，之前的binary search 是找打一个准确的值，这里的binary search是找一个值使其满足一个数学公式： i*i = x； 其实实质是一样的。 binary search的时间复杂度： O（log ｘ), 这里有一点可以改进的是，i^2 = x的话，i 的值是不超过 x/2 ＋　１的。
这里计算mid的时候可能会溢出，所以mid要用long
class Solution {
public:
    int mySqrt(int x) {
        //sanity check
        if (x <= 1) return x;
        long  left = 0;
        long right = x/2 + 1;
        while (left <= right) {
            long mid = left + (right - left)/2;
            if (mid * mid < x) {
                left  = mid + 1;
            } else if (mid * mid > x) {
                right = mid -1;
            }else return mid;
        }
        return right;
    }
};