Implement Sqrt function using binary search - The Coding Shala

Home >> Interview Questions >> Implement sqrt()

Implement Sqrt function using binary search

In this post, you will learn how to find the square root of a given number using the binary search algorithm. In java, the sqrt() function is already available to find square root for a number but in this post, we are going to implement sqrt() function using binary search.

Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2

Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Sqrt function in Java

We can do this using a binary search. If we check one by one until reaching the target we might get time limit error for large numbers.
Java Program: 

class Solution {
    public int mySqrt(int x) {
        if(x==1) return 1;
        int left = 1;
        int right = x/2;
        while(left<=right){
            int mid = left + (right-left)/2;
            if((long)mid*mid == (long)x) return mid;
            if((long)mid*mid > (long)x) right = mid-1;
            else left = mid+1;
        }
        return left-1;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

InterviewBit - Colorful Number Solution - The Coding Shala