Java Program to find Square Root of a number using Binary Search

Square Root of a number is an integer value when multiplied by itself, gives the original number. In this article, we are going to write a java program to find the square root of a number using binary search. Finding square root of a number is one of the application of the binary search algorithm. We will discuss in detail how we calculate the square root using binary search in this article.

Examples

Input: 64 Output: 8 

As, the square root of 64 is 8, the output is 8.

Input: 16 Output: 4 

As, the square root of 16 is 4, the output is 4.

Binary Search

Binary search is an algorithm used to find an element i.e., key in a sorted array. Binary algorithm works as below ?

• Let us say that array is ?arr'. Sort the array in ascending or descending order.

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

• Else if the key value is less than the arr[middle] element set the high index as middle index-1 or if the key value is more than middle element set the low index as middle index+1

• Continue the binary search until the element that needs to be find is found.

• If low is greater than high than return false directly as key is not present in the array ?arr'.

Example to find Key using Binary Search

Problem ? Given a sorted array of integers arr = [1, 3, 5, 7, 9, 11], find the index of the element i.e., key = 7 using binary search.

Solution

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

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

• mid = 0+(5-0)/2 = 2

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

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

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

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

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

Thus, the index of the key = 7 in the given array is 3, which we found using the binary search algorithm.

Algorithm to find the Square Root using Binary Search

• Consider a number ?n' and initialise low=0 and right= n (given number).

• Find mid value of low and high using mid = low + (high-low)/2.

• find the value of mid * mid, if mid * mid == n then return mid value.

• If mid value is less than n then low=mid+1 else high =mid-1

• Repeat from steps 2 to 4 until we find the value.

Example 1: Using Binary Search

In this example, we create a custom class ?BinarySearchSqrt' and implement the binary search code for finding the square root of a number code in ?sqrt' function. Now, create the custom Class object and initialise a variable called ?number' with an integer number and using the class object class the ?sqrt' function is called and thus the desired output is displayed.

//Java Program to find Square root of a number using Binary Search import java.util.*; class BinarySearchSqrt { public int sqrt(int number) { int low = 0; int high = number; while (low <= high) { int mid = (low + high) / 2; int square = mid * mid; if (square == number) { return mid; } else if (square < number) { low = mid + 1; } else { high = mid - 1; } } return 0; } } public class Main { public static void main(String[] args) { int n = 64; BinarySearchSqrt Obj = new BinarySearchSqrt(); int result= Obj.sqrt(n); System.out.println("Square root of " + n + " = " + result); } } 

Output

Square root of 64 = 8 

Time Complexity: O(NlogN) Auxiliary Space: O(1)

Example 2: Using Binary Search and Math.pow()

In the below example, we created a custom class ?BinarySearchSqrt' and implemented the binary search code for finding the square root of a number code in ?sqrt' function. The ?sqrt' function uses the in-built function ?Math.pow()' to calculate the square of a number .Now, create the custom Class object and initialise a variable called ?number' with an integer number and using the class object class the ?sqrt'function is called and thus the desired output is displayed.

//Java Program to find Square root of a number using Binary Search and Math.pow() import java.util.*; class BinarySearchSqrt { public int sqrt(int number) { int low = 0; int high = number; while (low <= high) { int mid = (low + high) / 2; if (Math.pow(mid,2) == number) { return mid; } else if (Math.pow(mid,2) < number) { low = mid + 1; } else { high = mid - 1; } } return 0; } } public class Main { public static void main(String[] args) { int n = 64; BinarySearchSqrt Obj = new BinarySearchSqrt(); int result= Obj.sqrt(n); System.out.println("Square root of " + n + " = " + result); } } 

Output

Square root of 64 = 8 

Time Complexity: O(NlogN) Auxiliary Space: O(1)

Thus, in this article we have discussed how to find the square root of a number using Binary Search Algorithm in Java.