二分与排序简单2 种解法

#69x 的平方根

返回非负整数 x 的算术平方根向下取整结果。

#数学#二分查找

解题主线

答案是满足 mid² <= x 的最大整数，可用二分查找最后一个真值。

解法 1：线性试探

从 0 递增，记录平方仍不超过 x 的最后一个整数。

时间复杂度

O(√x)

空间复杂度

O(1)

69. x 的平方根 · 线性试探

java

final class Solution {
    public int mySqrt(int x) {
        int answer = 0;
        while ((long) (answer + 1) * (answer + 1) <= x) answer++;
        return answer;
    }
}

从 0 递增，记录平方仍不超过 x 的最后一个整数。

解法 2：二分答案

在 [0, x] 中寻找平方不超过 x 的最右位置。

时间复杂度

O(log x)

空间复杂度

O(1)

69. x 的平方根 · 二分答案

java

final class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x, answer = 0;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if ((long) middle * middle <= x) {
                answer = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return answer;
    }
}

在 [0, x] 中寻找平方不超过 x 的最右位置。

边界与易错点

mid * mid 可能溢出 int，乘法前必须提升为 long。
x = 0 时答案也是 0。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q069_sqrtx.java