题目

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 2³¹ - 1

题解

public int mySqrt(int x) {
    // 二分法
    BiFunction<Integer, Integer, Integer> division = new BiFunction<Integer, Integer, Integer>() {
        @Override
        public Integer apply(Integer begin, Integer end) {
            // 出现小数的情况 向上取整
            if (begin > end) {
                return end;
            }
            // 二分法
            int mid = begin + (end - begin) / 2;
            if (mid > x / mid) {
                return this.apply(begin, mid - 1);
            } else if (mid < x / mid) {
                return this.apply(mid + 1, end);
            }

            return mid;
        }
    };

    return x <= 1 ? x : division.apply(2, x);
}

public int mySqrt1(int x) {
    return (int) Math.sqrt(x);
}