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

WBOY 转载: 2023-08-28 13:33:10 350浏览

立方根是一个整数值，当它自己连续乘以自己三次时，得到原始数值。在本文中，我们将编写一个使用二分搜索来找到一个数的立方根的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 = 元素数量），并将 mid 计算为 middle = low + (high-low)/2。如果 arr[middle] == key 则返回 middle，即数组的中间索引。
如果键值小于arr[middle]元素，则将高索引设置为中间索引-1；如果键值大于中间元素，则将低索引设置为中间索引+1
继续二分查找，直到找到需要查找的元素。
如果low大于high，则直接返回false，因为键值在数组'arr'中不存在。

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

问题

给定一个有序整数数组 arr = [1, 3, 5, 7, 9, 11]，使用二分查找找到元素的索引，即 key = 7。

解决方案

初始化 low = 0 和 high= 5（数组的最后一个索引）。
while 循环的第一次迭代给出了中间索引 mid = low+ (high-low)/2
中值 = 0+(5-0)/2 = 2。
arr[mid]的值为5，小于键值7。因此，我们更新low= mid+1 = 3。
while 循环的第二次迭代通过使用 low+ (high-low)/2 为我们提供中间索引 mid = 4。
arr[mid]的值为9，大于键值7。因此，我们更新high= 3（mid - 1）。
while 循环的第三次迭代为我们提供了中间索引 mid = 3。
arr[mid] 是 7，等于关键值。因此，我们返回中间索引，即 3。
因此，在给定的数组中，关键字的索引为7，我们使用二分查找算法找到了索引为3。

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

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

第 2 步 - 使用 mid = low + (high-low)/2 查找低值和高值的中值。

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

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

第 5 步 - 重复第 2 步到第 4 步，直到找到该值。

Example

的中文翻译为：

示例

在这个例子中，我们使用二分查找算法找到一个值的立方根。我们创建了一个自定义类'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);
   }
}