NUHMAN.com

Introduction

LeetCode 69: Sqrt(x) is a classic binary search problem disguised as a math function. The task is to compute the integer part of the square root of a non-negative integer x, discarding any decimal part.

This challenge is a great demonstration of how binary search can be applied outside of just arrays – here we use it to search through a range of integers for the solution.

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 like math.Sqrt.

Examples:

go

Input: x = 4
Output: 2

Input: x = 8
Output: 2
// Explanation: The square root of 8 is 2.82842..., and the integer part is 2.

Constraints

• 0 <= x <= 2³¹ - 1

Approach: Binary Search

We know that:

• The square root of x must lie between 0 and x.
• We can use binary search to narrow down the possible answer by comparing mid * mid to x.

Steps:

1. Set left = 0, right = x.
2. Loop while left <= right:

• Compute mid = (left + right) / 2.
• If mid*mid == x, return mid.
• If mid*mid < x, store mid as possible answer and search right half.
• Else, search the left half.

1. Return the last recorded possible answer.

Go Implementation

go

func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left, right := 1, x/2
    var result int

    for left <= right {
        mid := left + (right-left)/2
        if mid <= x/mid {
            result = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return result
}

Explanation

• We avoid using mid * mid directly to prevent integer overflow.
• Instead, we use mid <= x / mid for safe comparison.
• result stores the last known mid such that mid*mid <= x.

Time and Space Complexity

MetricComplexityTime ComplexityO(log x)Space ComplexityO(1)

• Binary search takes logarithmic time over the range [0, x].
• No extra space used.

Edge Cases

• x = 0 → 0
• x = 1 → 1
• Very large input (e.g., x = 2^31 - 1) → handled without overflow

Conclusion

LeetCode 69 is a textbook example of applying binary search to optimize mathematical computation. It avoids brute force looping and instead uses a powerful, efficient algorithm that scales logarithmically. It’s a great stepping stone into algorithmic thinking in Go and mastering overflow-safe logic.