Square Root (Binary Search on Answer)

Problem Statement

Given a non-negative integer x, compute and return the integer part of its square root. You must not use built-in exponent functions.

Example: x = 8 → Output: 2 (because 2² ≤ 8 < 3²)

Approach 1: Linear Scan

Explanation: Try every integer from 0 to x to find the square root.

Time Complexity: O(√x)

Space Complexity: O(1)

for i in 0..x:
    if i*i > x:
        return i-1
return x

Approach 2: Binary Search on Answer

Explanation: Treat square root as an answer in range [0, x] and use binary search.

Time Complexity: O(log x)

Space Complexity: O(1)

low = 0
high = x
while low <= high:
    mid = (low + high) // 2
    if mid*mid == x:
        return mid
    else if mid*mid < x:
        low = mid + 1
        ans = mid
    else:
        high = mid - 1
return ans

Approach 3: Newton's Method (Optional)

Explanation: Iteratively improve guess using x / guess formula.

Time Complexity: O(log x)

Space Complexity: O(1)

guess = x
while guess*guess - x > epsilon:
    guess = (guess + x/guess) / 2
return int(guess)