剑指 Offer II 072. 求平方根
题目:
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去
示例.png
思路提醒.png
利用库函数 :袖珍计算器算法
逻辑分析.png
class Solution1 {
public int mySqrt(int x) {
if(x==0) return 0;
int ans = (int)Math.exp(0.5*Math.log(x));
return (long)(ans+1)*(ans+1) <= x ?(ans+1):ans;
}
}
袖珍计算器提交结果.png
二分查找
很牛的思路.png
class Solution {
int mySqrt(int x) {
/* 查找区间为 [1, x / 2 + 1] */
int left = 1, right = x / 2 + 1;
/* 循环不变量，查找区间始终保持左闭右闭 */
while (left <= right) {
/* 防止整型溢出 */
int mid = left + ((right - left) >> 1);
if (mid > x / mid) {
right = mid - 1;
} else if (mid < x / mid) {
left = mid + 1;
} else {
return mid;
}
}
return right;
}
}
二分查找提交结果.png
方法三：牛顿迭代
牛顿迭代法是一种可以用来快速求解函数零点的方法
