069 - Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.
Hide Tags
Math Binary Search
Hide Similar Problems
(M) Pow(x, n)

跟pow一样，也是二分法，不过简单点。
考虑到 1 的平方还是 1，起点终点就选 0 和 x，
每次折半，看平方是否等于 x，直到上下限颠倒。
因为返回值是向下取整，所以一旦上下限颠倒，返回 a-1 即可。
另外注意，如果X输入很大，计算 x 平方就可能溢出，所以变量用 long 而不是 int。

class Solution {
public:
    int mySqrt(int x) {
        long a=0, b=x;
        while(a<=b)
        {
            long mid=(a+b)/2;
            long sq = mid*mid;
            if(x==sq)
                return (int)mid;
            if(x>sq)
                a=mid+1;
            else
                b=mid-1;
        }
        return a-1;
    }
};
8 ms.