力扣打卡之X的平方根

题目描述

在不使用sqrt(x)函数的前提下，得到x的平方根

解题思路

方法一：二分法

所谓二分法就是每次找到当前数组的最中间的值，然后将最中间的值的平方根和我们的需求作比较，如果中间的值的平方根大于我们需求的值就往左边找，反之往右边找！！！

方法二：牛顿迭代

什么是牛顿迭代？其实看完之后我还是有点懵

然后我就去研究了一下，所谓牛顿迭代就是利用无限次切线最后求得曲线的解！

其实研究起来挺简单的，可以参考这个文章

牛顿迭代法 - 知乎 (zhihu.com)

然后具体描述一下牛顿迭代法在java中是怎么使用的

在这里，我们也是通过无限次的求解来得到最后的结果

我们举一个例子

因此，我们利用上面的方法就可以最后得到我们想要的所有的结果了！

代码展示

方法一：二分法

public int BinarySearch(int x){   //首先我们要找x的平方根我们就要知道它的范围应该是[0,x-1]
       
    int index=-1;
    int l=0,r=x-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(mid*mid<=x) 
        {   index=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return index;    
}

方法二：牛顿迭代

public int newton(int x){
    if(x<=0) return 0;
    return (int)sqrt(x,x);   //这里需要向下转型，因为我们需要的是int类型的，但是返回的却是double
}
public double sqrt(double i,int x)
{
    double res=(i+x/i)/2;     
    if(res==i)  return i;     //当我们求得的值和我们输入的值一样的时候，我们就得到了最后的结果
    else{
        sqrt(res,x);
    }
}

总结

这个题目主要考察牛顿迭代

我们要知道，需要找某个范围内的某个值的时候我们就可以使用二分法