Example 16
x 的平方根
题目概述：给你一个非负整数 x ，计算并返回x的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题思路：由于 xx 平方根的整数部分ans 是满足k2≤x 的最大k 值，因此可以对k 进行二分查找，从而得到答案。
二分查找的下界为0，上界可以粗略地设定为x。在二分查找的每一步中，只需要比较中间元素mid 的平方与x 的大小关系，并通过比较的结果调整上下界的范围。由于所有的运算都是整数运算，不会存在误差，因此在得到最终的答案ans 后，也就不需要再去尝试ans+1 了。
解题步骤：
1. 定义变量l、r、ans，分别代表初始上界、初始下界、默认返回值，初值分别为0、x、-1。
2. 定义while循环，通过不断增大下界或减小上界来向目标值逼近，当下界不小于等于上界时，表明已经全部考察完毕，已经找到目标值，跳出循环。
3. 在while循环中，定义根据当前上、下界得出的中点。判断mid的平方是否小于等于x（mid的平方有可能出现数据溢出，因此需要转为long型），若是，则表明目标点在中点处或者在中点右侧，则将ans更新为mid（mid有可能是目标值），将下界更新为mid + 1；否则表明目标点在中点左侧，将上界更新为mid - 1。
4. 循环结束后，将得到的目标点返回。
示例代码如下：
public class SquareRootOfX { /** * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 * 示例 1： * 输入：x = 4 * 输出：2 * 示例 2： * 输入：x = 8 * 输出：2 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。 * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/sqrtx */ public static void main(String[] args) { SquareRootOfX srox = new SquareRootOfX(); System.out.println(srox.mySqrt(8)); // 2 } /** * 官方 * * @param x * @return */ public int mySqrt(int x) { int l = 0, r = x, ans = -1; while (l <= r) { int mid = (r + l) / 2; if ((long) mid * mid <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } }
