数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用二分查找法查找数字平方根的 Java 程序
数字的平方根是一个整数，当它自身相乘时，会得到原始数字。在本文中，我们将编写一个 Java 程序，使用二分查找法来查找数字的平方根。查找数字的平方根是二分查找算法的应用之一。我们将在本文中详细讨论如何使用二分查找法计算平方根。
示例
Input: 64 Output: 8
例如，64 的平方根是 8，输出为 8。
Input: 16 Output: 4
例如，16 的平方根是 4，输出为 4。
二分查找
二分查找是一种用于在已排序数组中查找元素（即键）的算法。二分查找算法的工作原理如下：
假设数组为“arr”。将数组按升序或降序排序。
初始化 low = 0 和 high = n-1（n = 元素数量），并计算中间值 middle = low + (high-low)/2。如果 arr[middle] == key，则返回 middle，即数组的中间索引。
否则，如果键值小于 arr[middle] 元素，则将 high 索引设置为 middle 索引-1；或者如果键值大于 middle 元素，则将 low 索引设置为 middle 索引+1。
继续进行二分查找，直到找到需要查找的元素。
如果 low 大于 high，则直接返回 false，因为键不在数组“arr”中。
使用二分查找查找键的示例
问题 - 给定一个已排序的整数数组 arr = [1, 3, 5, 7, 9, 11]，使用二分查找法查找元素（即键）key = 7 的索引。
解决方案
初始化 low = 0 和 high= 5（数组的最后一个索引）。
while 循环的第一次迭代为我们提供了中间索引 mid = low+ (high-low)/2
mid = 0+(5-0)/2 = 2
arr[mid] 的值为 5，小于键值 7。因此，我们将 low 更新为 mid+1 = 3。
while 循环的第二次迭代为我们提供了中间索引 mid = 4，使用 low+ (high-low)/2。
arr[mid] 的值为 9，大于键值 7。因此，我们将 high 更新为 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 值。
如果 mid 值小于 n，则 low=mid+1，否则 high =mid-1
重复步骤 2 到 4，直到我们找到该值。
示例 1：使用二分查找法
在这个例子中，我们创建了一个自定义类“BinarySearchSqrt”并在“sqrt”函数中实现了用于查找数字平方根的二分查找代码。现在，创建自定义类对象并用一个整数初始化名为“number”的变量，然后使用类对象调用“sqrt”函数，从而显示所需的输出。
//Java Program to find Square root of a number using Binary Search
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()”来计算数字的平方。现在，创建自定义类对象并用一个整数初始化名为“number”的变量，然后使用类对象调用“sqrt”函数，从而显示所需的输出。
//Java Program to find Square root of a number using Binary Search and 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 中使用二分查找算法查找数字的平方根。
2K+ 浏览量
