使用二分搜索法查找数字平方根的 Java 程序
数字的平方根是一个整数值,当将其乘以自身时,会得出原始数字。在本文中,我们将编写一个 Java 程序,使用二分搜索法查找数字的平方根。查找数字的平方根是二分搜索算法的应用之一。在本文中,我们将详细讨论如何使用二分查找计算平方根。
示例
输入:64 输出:8
因为 64 的平方根是 8,所以输出为 8。
输入:16 输出:4
因为 16 的平方根是 4,所以输出为 4。
二分查找
二分查找是一种用于在排序数组中查找元素(即键)的算法。二分算法的工作原理如下 -
假设数组为"arr"。按升序或降序对数组进行排序。
初始化 low = 0 和 high = n-1(n = 元素数量),并计算 middle = low + (high-low)/2。如果 arr[middle] == key,则返回 middle,即数组的中间索引。
否则,如果键值小于 arr[middle] 元素,则将高索引设置为中间索引-1,或者如果键值大于中间元素,则将低索引设置为中间索引+1
继续二分搜索,直到找到需要查找的元素。
如果低大于高,则直接返回 false,因为键不存在于数组"arr"中。
使用二分搜索查找键的示例
问题 - 给定一个有序的整数数组 arr = [1, 3, 5, 7, 9, 11],使用二分查找元素的索引,即 key = 7搜索。
解决方案
初始化低 = 0 和高 = 5(数组的最后一个索引)。
while 循环的第一次迭代为我们提供了中间索引 mid = low+ (high-low)/2
mid = 0+(5-0)/2 = 2
arr[mid] 的值为 5,小于键值 7。因此,我们更新低 = mid+1 = 3。
while 循环的第二次迭代通过使用 low+ (high-low)/2 为我们提供了中间索引 mid = 4。
arr[mid] 的值为 9,大于键值 7。因此,我们更新高 = 3 (mid - 1)。
while 循环的第三次迭代给了我们中间索引 mid = 3。
arr[mid] 为 7,等于键值。因此,我们返回中间索引,即 3。
因此,给定数组中键 = 7 的索引为 3,我们使用二分搜索算法找到了它。
使用二分搜索查找平方根的算法
考虑一个数字"n",初始化 low=0 和 right= n(给定数字)。
使用 mid = low + (high-low)/2 找到 low 和 high 的中间值。
找到 mid * mid 的值,如果 mid * mid == n,则返回中间值。
如果 mid 值小于 n,则 low=mid+1,否则 high =mid-1
重复步骤 2 到 4,直到找到值。
示例 1:使用二分搜索
在此示例中,我们创建自定义类"BinarySearchSqrt",并在"sqrt"函数中实现二分搜索代码,以查找数字的平方根代码。现在,创建自定义 Class 对象并用整数初始化一个名为"number"的变量,然后使用类对象类调用"sqrt"函数,从而显示所需的输出。
//Java 程序使用二分搜索查找数字的平方根
import java.util.*;
class BinarySearchSqrt {
public int sqrt(int number) {
int low = 0;
int high = number;
while (low <= high) {
int mid = (low + high) / 2;
int square = mid * mid;
if (square == number) {
return mid;
} else if (square < number) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return 0;
}
}
public class Main {
public static void main(String[] args) {
int n = 64;
BinarySearchSqrt Obj = new BinarySearchSqrt();
int result= Obj.sqrt(n);
System.out.println("Square root of " + n + " = " + result);
}
}
输出
Square root of 64 = 8
时间复杂度:O(NlogN) 辅助空间:O(1)
示例 2:使用二分搜索和 Math.pow()
在下面的示例中,我们创建了一个自定义类"BinarySearchSqrt",并在"sqrt"函数中实现了二分搜索代码,用于查找数字的平方根代码。"sqrt"函数使用内置函数"Math.pow()"来计算数字的平方。现在,创建自定义 Class 对象并用整数初始化一个名为"number"的变量,并使用类对象类调用"sqrt"函数,从而显示所需的输出。
//Java 程序使用二分搜索和 Math.pow() 查找数字的平方根
import java.util.*;
class BinarySearchSqrt {
public int sqrt(int number) {
int low = 0;
int high = number;
while (low <= high) {
int mid = (low + high) / 2;
if (Math.pow(mid,2) == number) {
return mid;
} else if (Math.pow(mid,2) < number) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return 0;
}
}
public class Main {
public static void main(String[] args) {
int n = 64;
BinarySearchSqrt Obj = new BinarySearchSqrt();
int result= Obj.sqrt(n);
System.out.println("Square root of " + n + " = " + result);
}
}
输出
Square root of 64 = 8
时间复杂度:O(NlogN) 辅助空间:O(1)
因此,在本文中,我们讨论了如何使用 Java 中的二分搜索算法来查找数字的平方根。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

