Square Root using Binary Search – GeeksforGeeks Solution Explained

The “Square Root using Binary Search” problem is a classic question that helps you understand both brute force and binary search techniques. In this blog, we’ll explain the problem, walk you through both brute force and binary search solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

You are given a non-negative integer n. Your task is to compute the floor value of the square root of n (i.e., the greatest integer x such that x*x <= n).

Example 1

Input:
n = 5

Output:
2

Explanation:
The square root of 5 is approximately 2.236. The floor value is 2.

Example 2

Input:
n = 16

Output:
4

Explanation:
The square root of 16 is exactly 4.

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Number:
   Start from 0 and go up to n. For each number, check if its square is less than or equal to n.
2. Keep Track of the Answer:
   If the square is less than or equal to n, update the answer.
3. Stop When Square Exceeds n:
   As soon as the square of the number is greater than n, break the loop.
4. Why does this work?
   We check every possible integer, so we’re sure to find the largest integer whose square is less than or equal to n.

This approach is easy to understand but not very efficient for large values of n.

Code Implementation

class Solution:
    def floorSqrt(self, n):
        ans = 0
        for i in range(0, n + 1):
            if i * i <= n:      # Check if square is less than or equal to n
                ans = i         # Update answer
            else:
                break           # Stop if square exceeds n
        return ans              # Return the floor value of sqrt(n)

Code Explanation

• Start from 0 and check every number up to n.
• If i * i is less than or equal to n, update ans.
• As soon as i * i exceeds n, break the loop.
• Return the last valid value of ans.

Dry Run

Input:
n = 10

• i = 0: 0*0 = 0 ≤ 10 → ans = 0
• i = 1: 1*1 = 1 ≤ 10 → ans = 1
• i = 2: 2*2 = 4 ≤ 10 → ans = 2
• i = 3: 3*3 = 9 ≤ 10 → ans = 3
• i = 4: 4*4 = 16 > 10 → break

Final Output:
3

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every number up to n.
• Space Complexity: O(1)
  Only a variable for the answer.

Conclusion

The brute force approach is simple and works for small values of n, but it’s too slow for large inputs.

Solution using Binary Search

Intuition and Approach

We can do much better using binary search:

1. Binary Search Range:
   The answer lies between 0 and n. Use binary search to find the largest integer whose square is less than or equal to n.
2. Check the Middle Value:
   • If mid*mid is less than or equal to n, move the search to the right (higher values).
   • If mid*mid is greater than n, move the search to the left (lower values).
3. Why does this work?
   Binary search efficiently narrows down the possible values, making it much faster for large n.

Code Implementation

class Solution:
    def floorSqrt(self, n):
        low = 0
        high = n
        while low <= high:
            mid = (low + high) // 2
            if mid * mid <= n:
                low = mid + 1        # Try for a bigger answer
            else:
                high = mid - 1       # Try for a smaller answer
        return high                  # high will be the floor value of sqrt(n)

Code Explanation

• Use binary search between 0 and n.
• If mid*mid is less than or equal to n, move low up to search for a bigger answer.
• If mid*mid is greater than n, move high down to search for a smaller answer.
• When the loop ends, high will be the largest integer whose square is less than or equal to n.

Dry Run

Input:
n = 10

• low = 0, high = 10
• mid = 5, 5*5 = 25 > 10 → high = 4
• mid = 2, 2*2 = 4 ≤ 10 → low = 3
• mid = 3, 3*3 = 9 ≤ 10 → low = 4
• mid = 4, 4*4 = 16 > 10 → high = 3

Loop ends.
Final Output:
3 (since 33 = 9 ≤ 10 and 44 = 16 > 10)

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search divides the range each time.
• Space Complexity: O(1)
  Only a few pointers.

Conclusion

The binary search solution is efficient and works well for large values of n. It’s the best approach for interviews and practical use.

Final Thoughts

The “Square Root using Binary Search” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.