Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Implementation in Java
3.2.
Complexity Analysis
4.
Approach 2
4.1.
Implementation in Java
4.2.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What optimization did we do on the brute force approach to solve this problem?
5.2.
What is the time complexity for the optimized approach?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Square Root using binary search

Author Nishant Rana
4 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Binary search is one of the most common concepts which is utilized across many different problems in competitive programming as well as in Interviews. Binary search is a method of searching for an element in a sorted dataset. It is much faster than the linear searching methods which involve going through every single element. It can search for an element in a data sent only in O(logN) time where N is the size of the dataset. Here in this problem, we are going to look at one of the ways we can utilize binary search so let's get right to it.

(Also, see Data Structures)

Problem Statement

Given the number ‘X .’ Find the Square root(sqrt) of that given number. If the given number is not a perfect square, return the floor value of the Square Root i.e., the nearest smaller integer.

Let us see a few examples:-

Example 1

Input: 9

Output: 3

Explanation: Square root of 9 is 3. Hence, the output is 3.

Example 2

Input: 8

Output: 2

Explanation: Square root of 8 is 2.82. Since it is a decimal value, the answer will be its floor value i.e., 8.

did you know?

Let's move towards the approach section of this article.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

The square root of the number X can be between 1 and X only. Hence, we can check for each value from 1 to X if it is the given number's square root. 

Implementation in Java


class Main{
    
    public static int mySqrt(int x) {
        
        //It will store the square root of x
        long sqrt = 0;
        
        /* 
          Running a for loop
          and checking every possible
          value for the square root.
        */
        for(long i = 1; i <= x; i++){
            if(i * i <= x){
                sqrt = i;
            }
            else {
                break;
            }
        }
        
        return (int)sqrt;
    }
public static void main (String[] args) {
    int X = 9;
    System.out.println("Square root of "+X+" is "+mySqrt(X));
}
}

Output:

Square root of 9 is 3

Complexity Analysis

Time Complexity: The time complexity for the above approach is O(sqrt(X)) because we run a for loop till the sqrt(x) only.

Space Complexity: The space complexity for the above code is O(1) because we are not using any auxiliary space.

Must Read Recursive Binary Search and  Rabin Karp Algorithm

Approach 2

We can apply Binary Search instead of Linear search to find the square root of a given number.

The reason behind using binary search is that the square of any number ‘N’ increases if we increase the value of ‘N’ and decreases if we decrease the value of ‘N’.

From the above, we can see that it is a monotonically increasing function. Hence, we can apply binary search on it.
We will apply binary search on the Square Root of the given number ‘X’ and check if it is a potential Square Root of a given number ‘X’ or not.

Implementation in Java

class Main {
    
    public static int mySqrt(int x) {
        
        // Base Cases
        if (x == 0 || x == 1){
            return x;
        }
  
        // Do Binary Search for floor(sqrt(x))
        long start = 1, end = x, ans = 0;
        
        while (start <= end)
        {
            long mid = (start + end) / 2;
  
            // If x is a perfect square
            if (mid * mid == x){
                return (int)mid;
            }
  
            /*
              Since we need floor, we update answer when mid*mid is
              smaller than x, and move closer to sqrt(x)
            */
            if (mid * mid < x){
                start = mid + 1;
                ans = mid;
            }

            // If mid * mid is greater than x
            else{
                end = mid - 1;
            }
        }
        return (int)ans;
    }
public static void main (String[] args) {
    int X = 9;
    System.out.println("Square root of "+X+" is "+mySqrt(X));
}
}

 

Output:

Square root of 9 is 3 

(Also, see Square Root in C)

Must read decimal to binary c++ 

Complexity Analysis

Time Complexity: The time complexity for the above approach is O(log(X)) because we are doing a binary search in the range 1 - X.

Space Complexity: The space complexity for the above code is O(1) because we are not using any auxiliary space.

Read More - Time Complexity of Sorting Algorithms

 

Have you noticed how Binary Search reduces the time complexity? Binary Search has always been one of the most asked topics in interviews, to get complete hands-on experience on various other questions which can be asked on Binary Search, you should watch the below video.

Frequently Asked Questions

What optimization did we do on the brute force approach to solve this problem?

We applied binary search instead of linear search because the square of any number ‘N’ increases if we increase the value of ‘N’ and decreases if we decrease the value of ‘N’. From the above, we can see that it is a monotonically increasing function. Hence, we can apply binary search on it.

What is the time complexity for the optimized approach?

The time complexity for the optimized approach 2 is O(log(X)) because we are doing a binary search in the range 1 - X.

Conclusion

In this blog, we have covered the following things:

  1. We first discussed the Brute Force approach to solve this problem.
  2. Then we saw how we optimized the brute force approach by applying a Binary Search instead of a Linear Search.


Recommended Readings:


If you want to learn more about Dynamic Programming and want to practice some questions which require you to take your basic knowledge of Dynamic Programming a notch higher, then you can visit our Guided Path for Binary Search. To practice this problem, you can visit Practice Problem.
 

Until then, All the best for your future endeavors, and Keep Coding.


keep coding

Previous article
Search an Element in an Unsorted Array using Minimum Number of Comparisons
Next article
Count of only Repeated Element in a Sorted Array of Consecutive Elements
Live masterclass