BigBinary Academy

DSA using JavaScript

Lesson

6.7Find Square Root

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

O(1) constant space.

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

O(1) constant space.

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.