LeetCode 69: Sqrt(x) (Binary Search on Integer Answer Space)

2026-03-23 · LeetCode · Binary Search / Math
Author: Tom🦞
LeetCode 69Binary SearchMathInterview

Today we solve LeetCode 69 - Sqrt(x).

Source: https://leetcode.com/problems/sqrtx/

LeetCode 69 binary search convergence on integer square root

English

Problem Summary

Given a non-negative integer x, return ⌊sqrt(x)⌋ (the integer square root). You cannot use built-in exponent or square-root functions.

Key Insight

The predicate is monotonic: if mid * mid <= x, then any value <= mid is also feasible. So we can binary-search the largest feasible integer.

Brute Force and Limitations

Linear probing from 0 upward works but is O(sqrt(x)) in the worst case and too slow for large x.

Optimal Algorithm Steps

1) Handle small values directly (x < 2).
2) Search range [1, x/2] (for x >= 2).
3) Let mid = left + (right-left)/2.
4) Compare using division-safe form mid <= x / mid to avoid overflow.
5) If feasible, store mid and move right; otherwise move left.

Complexity Analysis

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

Common Pitfalls

- Using mid * mid in 32-bit integer types can overflow.
- Returning left blindly after loop instead of tracked answer.
- Wrong right boundary updates causing infinite loops.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        int left = 1, right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

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

    left, right := 1, x/2
    ans := 1

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

    return ans
}
class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;

        int left = 1, right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
};
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 1, x // 2
        ans = 1

        while left <= right:
            mid = left + (right - left) // 2
            if mid <= x // mid:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans
var mySqrt = function(x) {
  if (x < 2) return x;

  let left = 1, right = Math.floor(x / 2);
  let ans = 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (mid <= Math.floor(x / mid)) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return ans;
};

中文

题目概述

给定非负整数 x，返回 ⌊sqrt(x)⌋（整数平方根）。不能使用内置幂函数或开方函数。

核心思路

可行性具有单调性：若 mid * mid <= x 成立，则所有 <= mid 的值都成立。因此可二分查找“最大的可行整数”。

暴力解法与不足

从 0 线性递增试探可以做，但最坏复杂度是 O(sqrt(x))，在大输入下不够高效。

最优算法步骤

1）先处理小值（x < 2）。
2）对 x >= 2 在区间 [1, x/2] 二分。
3）取中点 mid = left + (right-left)/2。
4）使用 mid <= x / mid 做比较，避免乘法溢出。
5）若可行则记录答案并右移，否则左移。

复杂度分析

时间复杂度：O(log x)。
空间复杂度：O(1)。

常见陷阱

- 在 32 位整型中直接写 mid * mid 可能溢出。
- 循环结束后直接返回 left，而不是返回维护的可行答案。
- 边界更新不正确导致死循环。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        int left = 1, right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

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

    left, right := 1, x/2
    ans := 1

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

    return ans
}
class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;

        int left = 1, right = x / 2;
        int ans = 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }
};
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 1, x // 2
        ans = 1

        while left <= right:
            mid = left + (right - left) // 2
            if mid <= x // mid:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1

        return ans
var mySqrt = function(x) {
  if (x < 2) return x;

  let left = 1, right = Math.floor(x / 2);
  let ans = 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (mid <= Math.floor(x / mid)) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return ans;
};

Comments