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

javaobject oriented programmingprogramming更新于 2024/3/17 7:40:17

数字立方根是一个整数值,将其乘以自身三次,可得出原始数字。在本文中,我们将编写一个 Java 程序,使用二分搜索法查找数字立方根。查找数字立方根是二分搜索算法的应用之一。在本文中,我们将详细讨论如何使用二分查找计算立方根。

输入输出示例

示例 1:
输入:64
输出:4

由于 64 的立方根为 4,因此输出为 4。

示例 2:
输入:216
输出:6

由于 216 的立方根为 6,因此输出为 6。

二分查找

二分查找是一种用于在排序数组中查找元素(即键)的算法。二分算法的工作原理如下

  • 假设数组为"arr"。按升序或降序对数组进行排序。

  • 初始化 low = 0 和 high = n-1(n = 元素数量),并计算 middle = low + (high-low)/2。如果 arr[middle] == key,则返回 middle,即数组的中间索引。

  • 否则,如果 key 值小于 arr[middle] 元素,则将高索引设置为中间索引-1,或者如果 key 值大于中间元素,则将低索引设置为中间索引+1

  • 继续二分查找,直到找到需要查找的元素。

  • 如果 low 大于 high,则直接返回 false,因为 key 不存在于数组"arr"中。

使用二分查找查找 key 的示例

问题

给定一个已排序的整数数组 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,这是我们使用二分搜索算法找到的。

使用二分搜索查找立方根的算法

步骤 1 - 考虑数字"n",初始化 low=0 和 right= n(给定数字)。

步骤 2 - 使用 mid = low + (high-low)/2 找到 low 和 high 的中间值。

步骤 3 - 找到 mid * mid*mid 的值,如果 mid * mid*mid == n,则返回中间值。

步骤 4 - 如果中间值小于 n,则 low=mid+1,否则 high =mid-1

步骤 5 - 重复步骤 2 至 4,直到找到值。

示例

在此示例中,我们使用二分搜索算法查找值的立方根。我们创建了一个自定义类"BinarySearchCbrt",并在"cuberoot"函数中实现了二分搜索代码,用于查找数字代码的立方根。现在,创建自定义类对象并用整数初始化一个名为"number"的变量,并使用类对象类调用"cuberoot"函数,从而显示所需的输出。

//Java 程序使用二分搜索查找数字的立方根
import java.util.*;
class BinarySearchCbrt {
   public  int cuberoot(int number) {
      int low = 0;
      int high = number;
      while (low <= high) {
         int mid = (low + high) / 2;
         int cube = mid * mid*mid;
         if (cube == number) {
            return mid;
         } else if (cube < number) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return 0;
   }
}
public class Main {
   public static void main(String[] args) {
      int n = 64;
      BinarySearchCbrt Obj  = new  BinarySearchCbrt();
      int result= Obj.cuberoot(n);
      System.out.println("Cube root of " + n + " = " + result);
   }
}

输出

Cube root of 64 = 4 

时间复杂度:O(NlogN) 辅助空间:O(1)

因此,在本文中,我们讨论了如何使用 Java 中的二分搜索算法来查找数字的立方根。


相关文章


有用资源