使用二分查找演算法找出一個數的立方根的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 = 元素數量），並將 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);
   }
}

輸出

Cube root of 64 = 4 

時間複雜度：O(NlogN) 輔助空間：O(1)

因此，在本文中我們討論瞭如何使用 Java 中的二分查找演算法來尋找數字的立方根。

以上是使用二分查找演算法找出一個數的立方根的Java程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！