成绩

编写一个函数 sqrt(x)，输入一个整数，返回其平方根的整数部分。

示例

• 输入：6
• 输入：2
• 输入：20
• 输入：4

说明：结果只保留整数部分，所有小数部分将被舍弃。

这是一道在 LeetCode 上的经典题目，也是面试中常见的测试题之一。该题目主要考察的是二分查找算法的应用。很多人在面试时可能并不清楚这个问题的核心在于二分查找。因此，掌握这类题目是非常重要的。接下来，我们将详细探讨该题的解决方法。

二分查找

二分查找的基本思路是在不断缩小搜索范围的过程中找到最接近 sqrt(x) 的整数值。通常情况下，一个整数的平方根不会超过其一半的值，可以通过不等式验证这一点。

例如，对于任意整数 a，当 a >= 4 或 a <= 0 时，a 的边界值（如 1、2、3）需要特别注意，避免遗漏。

关于为什么选择左侧的中位数，我们需要理解为什么会出现死循环的情况。虽然代码可以有多种实现方式，但这些细节并不是核心部分。

复杂度分析

• 时间复杂度：O(logN)，因为二分查找的时间复杂度是对数级别的。
• 空间复杂度：O(1)，只使用了常数级的额外空间。

牛顿法

对于熟悉机器学习的同学来说，牛顿法应该并不陌生。下面展示一个动态图来帮助理解牛顿法：

(动态图来源：https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/)

牛顿法原理

牛顿法的基本思想是，在每次迭代过程中，用一条直线（即一阶泰勒展开）来近似当前曲线，然后求出这条直线与 x 轴的交点，重复此过程直到收敛。

具体公式如下： [ f(x) = x^2 - a ] 目标是找到一个 x，使得 f(x) ≈ 0，即 x 接近 a 的平方根。

总结

这道题目展示了二分查找算法的典型应用。尽管问题本身简单，但理解背后的逻辑非常重要。对于如此基础的问题，您认为自己需要多长时间才能得出答案？欢迎大家在评论区分享您的看法。后续章节将继续介绍更多经典题目。