使用二分查詢法查詢數字立方根的 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 中使用二分查詢演算法查詢數字的立方根。