求平方根

剑指 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

方法三：牛顿迭代
牛顿迭代法是一种可以用来快速求解函数零点的方法