💬 Discord
Sign In
NeetCode #265LC-69EasyBinary SearchNC 250
← Back to All Problems

#265 · #69 · Sqrt(x)(x 的平方根)

📌 Problem Statement & Constraints

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You must not use any built-in exponent function or operator. Constraints: 0 <= x <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Binary search for the largest integer k with k * k <= x.
  2. Use the upper-bias midpoint (lo + hi + 1) // 2 together with lo = mid / hi = mid - 1, which finds the last valid value.
  3. The range is [0, x], since x itself bounds the answer.
  4. Newton's method converges faster in practice but binary search is the clearest answer.

💻 Benchmark Python3 Implementation

class Solution:
    def mySqrt(self, x: int) -> int:
        lo, hi = 0, x
        while lo < hi:
            mid = (lo + hi + 1) // 2   # upper-biased to avoid an infinite loop
            if mid * mid <= x:
                lo = mid               # mid is valid -> keep searching right
            else:
                hi = mid - 1
        return lo


# Newton's method: quadratic convergence
class Solution2:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2      # integer Newton step
        return r

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log x) for binary search; O(log log x) iterations for Newton's method.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using the lower-biased midpoint (lo + hi) // 2 with lo = mid: this loops forever when hi == lo + 1. The upper bias is required.
  • Using math.sqrt: explicitly forbidden by the problem.
  • Returning the float result: the answer is an integer (floor of the square root).
  • Overflowing in fixed-width languages: mid * mid can exceed 32 bits for large x; Python is safe.