Problem Statement
Given a non-negative integer, write a function to compute the square root using binary search. If the square root is not an integer, return the floor value.
Sample Test Case
Approaches
Brute Force Approach
Idea
- Try all numbers from 1 up to the square root of
x by multiplying each number by itself and checking if the result is equal to or less than x.
Steps
- Start from 1 and incrementally check if
i * i <= x.
- If the condition holds, update the result to
i.
- If the condition fails, return the last valid result.
Time Complexity
- O(sqrt(n)), since we are iterating through all numbers up to the square root of
x.
Space Complexity
Example Code
Dry Run
- Input: x = 8
- Start loop: i = 1, 1 * 1 = 1, continue.
- i = 2, 2 * 2 = 4, continue.
- i = 3, 3 * 3 = 9, stop.
- Output: result = 2.
Efficient Approach (Binary Search)
Idea
- Binary search between 1 and
x to find the largest number whose square is less than or equal to x.
Steps
- Initialize
low = 1 and high = x.
- Use binary search to find the square root:
- Calculate
mid = Math.floor((low + high) / 2).
- If
mid * mid == x, return mid.
- If
mid * mid < x, move the low pointer to mid + 1.
- If
mid * mid > x, move the high pointer to mid - 1.
- Return the
high pointer, which will be the floor value of the square root.
Time Complexity
- O(log n) due to binary search.
Space Complexity
Example Code
Dry Run
- Input: x = 8
low = 1, high = 8- Calculate mid:
mid = 4 (4 * 4 = 16, too large), set high = 3.
low = 1, high = 3- Calculate mid:
mid = 2 (2 * 2 = 4, valid), set low = 3, save mid = 2 as result.
- Calculate mid:
mid = 3 (3 * 3 = 9, too large), set high = 2.
- Return 2.
Example Test Case
Complexity Analysis
Brute Force Approach
- Time Complexity: O(sqrt(n))
- Space Complexity: O(1)
Efficient Approach
- Time Complexity: O(log n)
- Space Complexity: O(1)
Conclusion
- The brute force approach is simpler but has a higher time complexity as it iterates through all possible numbers up to the square root.
- The binary search approach reduces the time complexity significantly, making it suitable for large inputs.