Java 使用二分查找法找到一个数的立方根

立方根 当一个数与自身相乘三次时，得到原始数的整数值。在本文章中，我们将编写一个使用二分查找法找到一个数的立方根的Java程序。找到一个数的立方根是二分查找算法的一个应用之一。在本文中，我们将详细讨论如何使用二分查找法计算立方根。

输入输出示例

Example-1: 
Input: 64 
Output: 4

由于64的立方根是4，输出结果为4。

Example-2: 
Input: 216
Output: 6

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

二分查找

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

假设数组为’arr’。将数组按升序或降序排序。
初始化low = 0和high = n-1（n为元素个数），计算middle = low + (high-low)/2。如果arr[middle] key，则返回中间索引即middle。
否则，如果key值小于arr[middle]元素，则将high索引设置为middle索引-1；如果key值大于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，小于key值7。因此，我们更新low = mid + 1 = 3。
while循环的第二次迭代通过使用low + (high-low)/2来得到中间索引mid = 4。
arr[mid]的值为9，大于key值7。因此，我们更新high = 3（mid – 1）。
while循环的第三次迭代给出中间索引mid = 3。
arr[mid]是7，等于key值。因此，我们返回中间索引3。
因此，给定数组中键7的索引为3，这是使用二分查找算法找到的。

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

步骤1： 考虑一个数字’n’，并初始化low = 0和 high = n（给定的数字）。

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

步骤3 − 找到 mid * mid * mid 的值，如果 mid * mid * mid n，则返回 mid 的值。

步骤4 − 如果 mid 的值小于 n，则将 low=mid+1，否则将 high=mid-1

步骤5 − 重复步骤2到4直到找到所需的值。

示例

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

//Java Program to find Cube root of a number using Binary Search
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);
   }
}