Find Square Root [Binary Search]

69.Sqrt(x)

Math

Binary Search

Problem Statement:

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator.

Example:

Input:

x = 8

→

Output:

2

The square root of 8 is 2.82842..., and rounding down gives 2.

Algorithm:

1. Handle base cases (x = 0 or 1)
2. Use binary search in range [1, x]
3. For each mid point, compare mid² with x
4. Return largest number whose square is ≤ x

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

public int mySqrt(int x) {
    // Handle base cases
    if (x == 0 || x == 1) return x;

    int start = 1;
    int end = x;
    int mid = -1;

    while (start <= end) {
        // Prevent overflow using safe mid calculation
        mid = start + (end - start) / 2;

        if ((long) mid * mid > (long) x)
            end = mid - 1;
        else if (mid * mid == x)
            return mid;
        else
            start = mid + 1;
    }
    
    return end;
}

Python Solution:

def mySqrt(self, x: int) -> int:
    # Handle base cases
    if x < 2:
        return x
        
    start, end = 1, x
    
    while start <= end:
        mid = start + (end - start) // 2
        square = mid * mid
        
        if square > x:
            end = mid - 1
        elif square == x:
            return mid
        else:
            start = mid + 1
            
    return end

C++ Solution:

int mySqrt(int x) {
    // Handle base cases
    if (x == 0 || x == 1) return x;
    
    int start = 1;
    int end = x;
    
    while (start <= end) {
        int mid = start + (end - start) / 2;
        
        // Use long to prevent overflow
        if ((long) mid * mid > x)
            end = mid - 1;
        else if ((long) mid * mid == x)
            return mid;
        else
            start = mid + 1;
    }
    
    return end;
}