Java program to find the cube root of a number using binary search algorithm

Cube root is an integer value that, when multiplied by itself three times in succession, results in the original value. In this article, we will write a Java program that uses binary search to find the cube root of a number. Finding the cube root of a number is an application of the binary search algorithm. In this article, we will discuss in detail how to use binary search to calculate cube roots.

Input-output example

Example-1: 
Input: 64 
Output: 4 

For example, the cube root of 64 is 4, and the output is 4.

Example-2: 
Input: 216
Output: 6  

For example, the cube root of 216 is 6, and the output is 6.

Binary search

Binary search is an algorithm used to find elements (i.e. keys in a sorted array). The working principle of binary algorithm is as follows

• Assume the array is "arr". Sort an array in ascending or descending order.

• Initialize low = 0 and high = n-1 (n = number of elements), and calculate mid as middle = low (high-low)/2. If arr[middle] == key then returns middle, the middle index of the array.

• If the key value is less than the arr[middle] element, set the high index to the middle index -1; if the key value is greater than the middle element, set the low index to the middle index 1

• Continue binary search until you find the element you want to find.

• If low is greater than high, return false directly because the key value does not exist in the array 'arr'.

Example of using binary search to find a key

question

Given an ordered integer array arr = [1, 3, 5, 7, 9, 11], use binary search to find the index of the element, that is, key = 7.

solution

• Initialize low = 0 and high = 5 (last index of the array).

• The first iteration of the while loop gives the middle index mid = low (high-low)/2

• Median = 0 (5-0)/2 = 2.

• The value of arr[mid] is 5, which is less than the key value 7. Therefore, we update low= mid 1 = 3.

• The second iteration of the while loop gives us the mid index mid = 4 by using low (high-low)/2.

• The value of arr[mid] is 9, which is greater than the key value 7. Therefore, we update high = 3 (mid - 1).

• The third iteration of the while loop gives us the mid index mid = 3.

• arr[mid] is 7, equal to the key value. Therefore, we return the middle index, which is 3.

• So, in the given array, the index of the keyword is 7, and we found the index 3 using the binary search algorithm.

Algorithm for finding cube roots using binary search

Step 1 - Consider a number 'n' and initialize low=0 and right=n (the given number).

Step 2 - Find the median of low and high values ​​using mid = low (high-low)/2.

Step 3 − Find the value of mid * mid * mid. If mid * mid * mid == n, return the value of mid.

Step 4 - If the middle value is less than n, then low=mid 1, otherwise high=mid-1

Step 5 - Repeat steps 2 through 4 until you find the value.

The Chinese translation of

Example

is:

Example

In this example, we use the binary search algorithm to find the cube root of a value. We created a custom class 'BinarySearchCbrt' and implemented the binary search code for finding the cube root of a number in the 'cuberoot' function. Now, create a custom class object and initialize an integer variable named 'number' and call the 'cuberoot' function using the class object, thereby displaying the desired output.

//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);
   }
}

Output

Cube root of 64 = 4 

Time complexity: O(NlogN) Auxiliary space: O(1)

So, in this article we have discussed how to find the cube root of a number using binary search algorithm in Java.

The above is the detailed content of Java program to find the cube root of a number using binary search algorithm. For more information, please follow other related articles on the PHP Chinese website!