offer2-72

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4
输出: 2

示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

提示:

• 0 <= x <= 231 - 1

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

        if (x == 2 || x == 3) {
            return 1;
        }

        long start = 2l;
        long end = (long)x / 2;

        while (start <= end) {
            if (start == end) {
                return (int)start;
            }

            if (start + 1 == end) {
                if (end * end <= x) {
                    return (int)end;
                } else {
                    return (int)start;
                }
            }

            long mid = start + (end - start) / 2;

            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid < x) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)