菜鸡每日一题系列打卡69天
每天一道算法题目
小伙伴们一起留言打卡
坚持就是胜利，我们一起努力！
题目描述(引自LeetCode)
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:输入: 4输出: 2
示例 2:输入: 8输出: 2说明: 8 的平方根是 2.82842...,由于返回类型是整数，小数部分将被舍去。
题目分析
这道题目可以看作是一道纯数学的题目，我们可以采用诸如换底公式或者牛顿-拉夫逊迭代进行求解。
在本文中，菜鸡将会用一种在算法题中更常见的方法——二分法进行求解。思路通过二分求平方的方式每次淘汰一半的数字，最终得到答案。在这个过程中需要注意求平方过程中可能出现溢出。
话不多说，上代码！
代码实现
class Solution {public int mySqrt(int x) {int result = 0, start = 0, end = x, mid = 0;long multi = 0L;while (start <= end) {mid = start + ((end - start) >> 1);multi = (long) mid * mid;if (multi <= x) start = mid + 1;else end = mid - 1;}return multi > x ? mid - 1 : mid;}}
代码分析
对代码进行分析，程序采用二分搜索的方式，时间复杂度为O(logn)，而就空间而言，仅仅使用了常数级别的额外空间，因此，空间复杂度为O(1)。
执行结果
学习 | 工作 | 分享
👆长按关注“有理想的菜鸡”
文章转载自有理想的菜鸡，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
