【力扣】69. x 的平方根 学霸���你学废了么？
Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
春招打卡第22天第34篇。
勤学似春起之苗，不见其增，日有所长；辍学如磨刀之石，不见其损，日有所亏。
掘金的活动真多哇，这个月决定每天用go刷题，一方面提升一下算法水平，另一方面沉淀一下go语言的学习。
Let's GO!
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2312^{31}231 - 1
题目分析
为什么越刷题越觉得自己数学学的拉胯呢？
由于x平方根的整数部满足 k2k^{2}k2 ≤ x的最大k值，因此我们可以对k进行二分查找，从而得到答案。
思路讲解
这部分不算原创，是学习了力扣官方的解题思路后，归纳总结的：
- 二分查找的下界为0，上界可以粗略地设定为x。
- 在二分查找的每一步中，我们只需要比较中间元素mid的平方与x的大小关系
- 通过比较的结果调整上下界的范围
- 因为我们所有的运算都是整数运算，不会存在误差
- 因此在得到最终的答案ans后，也就不需要再去尝试ans+1了
AC代码
go
func mySqrt(x int) int { l, r := 0, x ans := -1 for l <= r { mid := l + (r - l) / 2 if mid * mid <= x { ans = mid l = mid + 1 } else { r = mid - 1 } } return ans }运行结果
总结
复杂度分析
时间复杂度：O(logx)，二分查找需要的次数。
空间复杂度：O(1)。
来源说明
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/sq…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最后
感谢阅读，欢迎大家三连：点赞、收藏、投币（关注）！！！