今天的這篇文章是我在刷算法題的時候遇到的，最簡單的方法是直接調用java里面的Sqrt函數错沃，不過有時候題目中會要求我們不能使用庫函數雀瓢，所以在這里我們自己定義Sqrt方法。
最常見的思路有兩種刃麸，第一種是二分法泊业，第二種是牛頓的微積分思想。沒錯脱吱，想當年大學時候學了很久很痛苦的微積分，被我第一次派上用場了续捂。對于這兩種方法我們一個一個看宦搬。
一、二分法
二分法的思想很簡單矾克，就是從0到N不斷的去縮小范圍來找一個一個滿足精度的最佳值憔足。我們舉一個函數的例子：
這就是二分法的思想酒繁，求平方根也是控妻，我們從0到value取出中間值弓候，然后不斷地比較，假設value=10菇存，查找區(qū)間為（0，10）亥至，這時候燃佟（0,10）的中間值mid=5，mid*mid再和value比較之后，確定下一次查找的區(qū)間變?yōu)椋?杯缺，5），依次類推袍榆。一直到滿足我們需要的精度即可塘揣。下面我們使用java代碼實現一下：
static double MySqrt(int value, double t){
if (value < 0 || t<0)
return 0;
double left = 0;
double right = value;
double mid = (right + left) / 2;
double offset = 2*t ;
while (offset>t){
double temp = mid*mid;
if (temp > value){
right = (left + right) / 2;
offset = temp - value;
}
if (temp <= value){
left = (left + right) / 2;
offset = value - temp;
}
mid = (left + right) / 2;
}
return mid;
}
在這里value就是我們要求的數字亲铡，t表示的是精度。這個方法在這奖蔓，大家可以測試一遍。不過在這里有一個小小的問題需要我們去注意：
如果我們對整數9取平方根厨疙，結果不是3疑务，這里有精度損失梗醇，損失的原因之一是和計算機有關的叙谨，因為計算機的底層其實只有0和1牙肝，所以會無限的接近，而不能精確表示配椭。
以上就是二分法求解的思想，這個思想很簡單衡楞，不過實現的方法卻是有一點點麻煩敦姻。在這里我們開始介紹第二種方法，那就是牛頓的微積分思想
二迷守、牛頓迭代法
牛頓的微積分的思想就是無限接近旺入，在這里提一句，如果你是數學大佬就不要追究思想到底是啥了礼华。對于求平方根來說拗秘，使用切線來無限逼近的方式有時候能起到意想不到的效果。
設r是f(x) = 0的根扮匠，選取x0作為r初始近似值凡涩，過點（x0,f(x0)）做曲線y = f(x)的切線L，
L的方程為y = f(x0)+f'(x0)(x-x0)帮非，求出L與x軸交點的橫坐標 x1 = x0-f(x0)/f'(x0)，稱x1為r的一次近似值末盔。
過點（x1,f(x1)）做曲線y = f(x)的切線陨舱，并求該切線與x軸交點的橫坐標 x2 = x1-f(x1)/f'(x1)，稱x2為r的二次近似值游盲。
重復以上過程，得r的近似值序列谜慌，其中x(n+1)=x(n)－f(x(n))/f'(x(n))莺奔，稱為r的n+1次近似值，上式稱為牛頓迭代公式恼琼。
我們使用一張圖來演示一下：
這種方式也很好理解屏富。所以我們直接來看實現：
static double SqrtIterator(int value,double t){
double temp = value;
while (fabs(temp*temp-value)>t){
temp=(temp+value/temp) / 2.0;
}
return temp;
}
//取絕對值
private static double fabs(double a) {
return (a < 0) ? -a : a;
}
上面的方法同樣可以表示狠半。而且我們可以看到，牛頓的這個方法其實更加的簡單。而且精度也更好乐严。
