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

---

一个数字的立方根是指一个整数，当它自身乘以三次后，结果等于原始数字。在本文中，我们将编写一个 Java 程序，使用二分查找法来查找数字的立方根。查找数字的立方根是二分查找算法的应用之一。我们将在 Java 中详细讨论如何使用二分查找算法计算立方根。

问题陈述

编写一个 Java 程序，使用二分查找法查找数字的立方根 -

输入 1

64 

输出 1

4 

由于 64 的立方根是 4，所以输出为 4。

输入 2

216

输出 2

6  

由于 216 的立方根是 6，所以输出为 6。

二分查找

二分查找算法 用于在已排序的数组中查找元素，即键。二分查找算法的工作原理如下 -

• 假设数组为 arr。将数组按升序或降序排序。

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

• 否则，如果键值小于 arr[middle] 元素，则将 high 索引设置为 middle index-1；或者如果键值大于 middle 元素，则将 low 索引设置为 middle index+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。

• 因此，给定数组中key = 7 的索引为 3，我们使用二分查找算法找到了它。

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

以下是使用二分查找算法查找数字立方根的步骤 -

• 考虑一个数字 n，并初始化 low=0 和 right=n（给定数字）。
• 使用 mid = low + (high-low)/2 查找 low 和 high 的中间值。
• 查找 mid * mid*mid 的值，如果 mid * mid*mid == n，则返回 mid 值。
• 如果 mid 值小于 n，则 low=mid+1，否则 high =mid-1
• 重复步骤 2 到 4，直到找到值。

查找立方根的 Java 程序

以下是使用二分查找算法查找数字立方根的 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)

代码解释

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

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