LeetCode 第69题 x的平方根

题目

点击查看原题

给你一个非负整数x，计算并返回x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被舍去。
注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5)或者x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：
0 <= x <= 2^31 - 1

方法1 二分查找

思路

代码

class Solution {
public:
    int mySqrt(int x) {
        int l=0,r=x,ans=-1;//声明变量  left=0;right=x最大值，ans答案设置为-1
        while(l<=r)//循环判断left永远小于等于right
        {
            int mid=(r-l)/2 + l;//获取中点的值
            if((long long)mid*mid <=x) //判断每一个中点的平方是否小于等于x，若小于x则中点变为left然后继续取中点判断，直到中点的平方等于x时跳出while。  此处mid*mid只能小于等于x，不能大于等于x，因为mid是取整之后的值，是丢掉小数部分的值，所以计算结果一定比x小，如果这里写成大于等于x，则会出现错误结果比正确结果大1的情况。
            {
                ans = mid;//中点赋值给答案
                l=mid+1;//进入if说明mid平方小于或等于x，所以抛弃mid当前值，从他的下一个值继续计算，所以+1
            }
            else
            {
                r=mid-1;//进入else说明mid平方大于x，所以抛弃mid当前值，从他的前一个值继续计算，所以-1
            }
        }
         return ans;//返回循环后的结果
    }
};

方法2 牛顿迭代法

思路

思路作者：LOAFER
源链接：https://leetcode.cn/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/

代码

class Solution {
public:
    int s; //定义一个保存原始数据的变量

    int mySqrt(int x) {
        s=x;//将输入的值复制一份存到s中
        if(x==0) return 0;//如果输入0，则直接输出结果
        return ((int)sqrt(x));//使用递归，直到找到答案才返回结果
    }

    double sqrt(double x) 
    {
        double res = (x+s/x)/2;//根据函数公式进行计算res的值
        if(res==x) return res;//若res等于x，则返回结果
        else return sqrt(res);//否则继续递归
    }
};