使用二分搜索法查找数字平方根的 Java 程序

javaobject oriented programmingprogramming更新于 2024/3/17 11:24:17

数字的平方根是一个整数值,当将其乘以自身时,会得出原始数字。在本文中,我们将编写一个 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"函数中实现了二分搜索代码,用于查找数字的平方根代码。"s​​qrt"函数使用内置函数"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 中的二分搜索算法来查找数字的平方根。


相关文章


有用资源