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

Cube rootis 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.

Example

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!