LeetCode LCR 072. x 的平方根

Categories:

题目描述
思路分析
1. 解法一：二分查找上界（推荐）
相似题目

题目描述

✅ LCR 072. x 的平方根

思路分析

解法一：二分查找上界（推荐）

核心思路：

目标是找到满足 mid * mid <= x 的最大整数。

使用二分查找，在闭区间内收缩范围。

为避免溢出，比较时用 mid <= x / mid。

复杂度分析：

时间复杂度：O(log x)，其中 x 表示输入数值。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }

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

        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 <= 1 {
		return x
	}

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

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

	return ans
}

相似题目

题目	难度	考察点
367. 有效的完全平方数	简单	二分查找
50. Pow(x, n)	中等	快速幂
69. x 的平方根	简单	二分查找
441. 排列硬币	简单	二分查找
278. 第一个错误的版本	简单	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/60776124