Java实现求非负整数的算术平方根 - 使用二分查找算法

Java实现求非负整数的算术平方根 - 使用二分查找算法

这篇文章介绍如何使用Java编写代码，计算一个非负整数的算术平方根，并返回其整数部分。我们不允许使用任何内置的指数函数和运算符，例如 pow(x, 0.5) 或 x ** 0.5 。

问题描述:

给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

解题思路:

我们可以使用二分查找算法来解决这个问题。二分查找是一种高效的搜索算法，适用于在一个有序数组中查找特定元素。

代码实现:

以下是使用二分查找方法计算算术平方根的Java代码：javapublic class Solution { public int mySqrt(int x) { if (x == 0) return 0; int left = 1; // 设置左边界为1 int right = x; // 设置右边界为x while (left <= right) { int mid = left + (right - left) / 2; // 取中间值 if (mid == x / mid) { return mid; // 找到平方根，返回中间值 } else if (mid < x / mid) { left = mid + 1; // 平方根在右半部分，调整左边界 } else { right = mid - 1; // 平方根在左半部分，调整右边界 } } return right; // 返回右边界，即整数部分的平方根 }}

代码解释:

上述代码使用二分查找方法在区间 [left, right] 中查找平方根。每次取中间值 mid 进行判断:

• 如果 mid 的平方等于 x，则直接返回 mid 作为平方根。* 如果 mid 的平方小于 x，则将左边界 left 调整为 mid + 1，因为平方根一定在右半部分。* 如果 mid 的平方大于 x，则将右边界 right 调整为 mid - 1，因为平方根一定在左半部分。

最终，循环结束时，right 的值将是小于等于 x 平方根的最大整数，因此我们返回 right 作为结果。

总结:

使用二分查找算法可以高效地计算非负整数的算术平方根。该算法的时间复杂度为 O(log n)，其中 n 是输入整数的大小。