Square Root (Binary Search on Answer)

LeetCode #69 [Easy]

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

💡 Think: Increment i until i² crosses x, then step back by one.

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

💡 Think: Search mid in [0,x]; compare mid² with x to tighten bounds.

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)

💡 Think: Iterate guess = (guess + x/guess)/2 until convergence, then floor.

Solve on LeetCode