Sqrt(x) Using Binary Search

Problem Statement

Given a non-negative integer x, return the integer square root of x (floor(sqrt(x))), without using built-in square-root functions.

Example

Input:  x = 8
Output: 2
Explanation: sqrt(8) = 2.82..., floored to 2.

Approach

Binary search the candidate answer in [1, x/2]. For a midpoint m, compare m*m with x. Narrow toward the largest m with m*m <= x. Use a 64-bit product (or compare with division) to avoid overflow.

Complexity

• Time: O(log x)
• Space: O(1)

Solution Code

Python

def mySqrt(x):
    if x < 2:
        return x
    left, right = 1, x // 2
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

Java

int mySqrt(int x) {
    if (x < 2) return x;
    long left = 1, right = x / 2;
    while (left <= right) {
        long mid = left + (right - left) / 2;
        if (mid * mid == x) return (int) mid;
        else if (mid * mid < x) left = mid + 1;
        else right = mid - 1;
    }
    return (int) right;
}

C++

int mySqrt(int x) {
    if (x < 2) return x;
    long long left = 1, right = x / 2;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (mid * mid == x) return (int) mid;
        else if (mid * mid < x) left = mid + 1;
        else right = mid - 1;
    }
    return (int) right;
}

Key Takeaways

• Returning right after the loop gives the floor automatically.
• Use 64-bit (long/long long) for mid*mid to avoid overflow.
• Reference: LeetCode 69 (Sqrt(x)).