What is the optimal approach for solving Sqrt(x)?

The optimal solution is binary search, which allows narrowing the search space for the square root efficiently without using built-in functions.

How do I handle edge cases like x = 0 or x = 1?

For x = 0, the square root is 0, and for x = 1, the square root is 1. These cases are straightforward and can be handled before applying binary search.

Why can't I use built-in exponentiation functions?

The problem explicitly asks not to use any built-in exponentiation functions or operators, which encourages you to implement a more fundamental approach such as binary search.

How do I ensure the output is rounded down to the nearest integer?

During the binary search, when you find a mid-point, you need to check if mid*mid is less than or equal to x. If it exceeds, adjust the bounds accordingly.

What is the time complexity of the binary search approach?

The time complexity of the binary search approach is O(log x), which is much more efficient than a brute force solution.

#69

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。示例 1：输入： x = 4 输出： 2 示例 2：输入： x = …

数学二分查找

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2³¹ - 1

lightbulb

解题思路

方法一：二分查找

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = x$ ，然后在 $[l, r]$ 范围内查找平方根。

在每一步查找中，我们找出中间值 $mid = (l + r + 1) / 2$ ，如果 $mid > x / mid$ ，说明平方根在 $[l, mid - 1]$ 范围内，我们令 $r = mid - 1$ ；否则说明平方根在 $[mid, r]$ 范围内，我们令 $l = mid$ 。

查找结束后，返回 $l$ 即可。

时间复杂度 $O(\log x)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l < r:
            mid = (l + r + 1) >> 1
            if mid > x // mid:
                r = mid - 1
            else:
                l = mid
        return l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands binary search and can apply it in mathematical problems.
question_mark
The candidate efficiently handles edge cases, like x = 0 and x = 1.
question_mark
The candidate explains the reasoning behind the time complexity and avoids unnecessary brute-force solutions.

warning

常见陷阱

外企场景

error
Using built-in square root functions, which contradicts the problem constraints.
error
Not considering edge cases, especially when x is 0 or 1.
error
Misunderstanding the rounding requirement, failing to correctly handle non-perfect squares.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing this with iterative search rather than binary search.
arrow_right_alt
Handling very large values of x near the upper bound of the constraints.
arrow_right_alt
Returning results in floating-point rather than integer form.

help

常见问题

外企场景

继续练习

#268 丢失的数字 #367 有效的完全平方数 #400 第 N 位数字