描述

实现 int sqrt(int x) 函数，计算并返回 x 的平方根。

样例

sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3

挑战

O(log(x))

代码

class Solution {
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    public int sqrt(int x) {
        long start = 1;
        long end = x;
        while (start + 1 < end) {
            long mid = (end - start) / 2 + start;
            // 如果不取 long 则此处会超出 int 范围
            if (mid * mid == x) {
                return (int)mid;
            }
            if (mid * mid < x) {
                start = mid;
            }
            if (mid * mid > x) {
                end = mid;
            }
        }
        
        if (end * end <= x) {
            return (int)end;
        } else {
            return (int)start;
        }
    }
}