題目描述（簡(jiǎn)單難度）
求一個(gè)數(shù)的平方根必盖，不要求近似解拌牲，只需要整數(shù)部分。
解法一 二分法
本科的時(shí)候上計(jì)算方法的時(shí)候歌粥，講過這個(gè)題的幾個(gè)解法塌忽，二分法， 牛頓法失驶，牛頓下山法土居，不同之處是之前是求近似解，類似誤差是 0.0001 這樣的嬉探。而這道題擦耀，只要求整數(shù)部分，所以先忘掉之前的解法涩堤，重新考慮一下眷蜓。
求 n 的平方根的整數(shù)部分，所以平方根一定是 1胎围，2吁系，3 ... n 中的一個(gè)數(shù)。從一個(gè)有序序列中找一個(gè)數(shù)白魂，像極了二分查找汽纤。先取中點(diǎn) mid，然后判斷 mid * mid 是否等于 n碧聪，小于 n 的話取左半部分冒版，大于 n 的話取右半部分，等于 n 的話 mid 就是我們要找的了逞姿。
public int mySqrt(int x) {
int L = 1, R = x;
while (L <= R) {
int mid = （L + R) / 2;
int square = mid * mid;
if (square == x) {
return mid;
} else if (square < x) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return ?;
}
正常的 2 分法辞嗡，如果最后沒有找到就返回 -1。但這里肯定是不行的滞造，那應(yīng)該返回什么呢续室？
對(duì)于平方數(shù) 4 9 16... 肯定會(huì)進(jìn)入 square == x 然后結(jié)束掉。但是非平方數(shù)呢谒养？例如 15挺狰。我們知道 15 的根明郭，一定是 3 點(diǎn)幾。因?yàn)?15 在 9 和 16 之間丰泊，9 的根是 3薯定，16 的根是 4。所以對(duì)于 15瞳购，3 在這里就是我們要找的话侄。 3 * 3 < 15，所以在上邊算法中学赛，最后的解是流向 square < x 的年堆，所以我們用一個(gè)變量保存它，最后返回就可以了盏浇。
public int mySqrt(int x) {
int L = 1, R = x;
int ans = 0; //保存最后的解
while (L <= R) {
int mid = （L + R) / 2;
int square = mid * mid;
if (square == x) {
return mid;
} else if (square < x) {
ans = mid; //存起來以便返回
L = mid + 1;
} else {
R = mid - 1;
}
}
return ans;
}
看起來很完美了变丧，但如果 x = Integer.MAX_VALUE 的話，下邊兩句代碼是會(huì)溢出的绢掰。
int mid = （L + R) / 2;
int square = mid * mid;
當(dāng)然痒蓬，我們把變量用 long 存就解決了，這里有一個(gè)更優(yōu)雅的解法曼月。利用數(shù)學(xué)的變形谊却。
int mid = L + (R - L) / 2;
int div = x / mid;
當(dāng)然相應(yīng)的 if 語句也需要改變。
else if (square < x)
mid * mid < x
mid < x / mid
mid < div
全部加進(jìn)去就可以了哑芹。
public int mySqrt(int x) {
int L = 1, R = x;
int ans = 0;
while (L <= R) {
int mid = L + (R - L) / 2;
int div = x / mid;
if (div == mid) {
return mid;
} else if (mid < div) {
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return ans;
}
時(shí)間復(fù)雜度：O（log ( x））炎辨。
空間復(fù)雜度：O（1）。
解法二 二分法求精確解
把求根轉(zhuǎn)換為求函數(shù)的零點(diǎn)聪姿，求 n 的平方根碴萧，也就是求函數(shù) f ( x ) = x2 - n 的零點(diǎn)。這是一個(gè)二次曲線末购，與 x 軸有兩個(gè)交點(diǎn)破喻，我們要找的是那個(gè)正值。
這里基于零點(diǎn)定理盟榴，去寫算法曹质。
如果函數(shù) y = f ( x ) 在區(qū)間 [ a, b ] 上的圖像是連續(xù)不斷的一條曲線擎场，并且有f ( a ) · f ( b ) < 0， 那么迅办，函數(shù)y = f ( x ) 在區(qū)間 ( a , b ) 內(nèi)有零點(diǎn)，即存在 c ∈ ( a , b ) , 使得 f ( c ) = 0 站欺，這個(gè) c 也就是方程 f ( x ) = 0 的根姨夹。
簡(jiǎn)單的說，如果曲線上兩點(diǎn)的值正負(fù)號(hào)相反磷账，其間必定存在一個(gè)根。
這樣我們就可以用二分法够颠，找出中點(diǎn)熙侍，然后保留與中點(diǎn)的函數(shù)值符號(hào)相反的一段履磨，丟棄另一段庆尘，然后繼續(xù)找中點(diǎn)，直到符合我們的誤差驶忌。
由于題目要求的是整數(shù)部分，所以我們需要想辦法把我們的精確解轉(zhuǎn)成整數(shù)付魔。
四舍五入？由于我們求的是近似解几苍，利用我們的算法我們求出的 8 的立方根會(huì)是 2.8125翻屈，直接四舍五入就是 3 了，很明顯這里 8 的平方根應(yīng)該是 2妻坝。
直接舍棄小數(shù)伸眶？由于我們是近似解，所有 9 的平方根可能會(huì)是 2.999刽宪， 舍棄小數(shù)變成 2 厘贼，很明顯也是不對(duì)的。
這里我想到一個(gè)解法圣拄。
我們先采取四舍五入變成 ans嘴秸，然后判斷 ans * ans 是否大于 n，如果大于 n 了庇谆，ans 減 1岳掐。如果小于等于，那么 ans 不變族铆。這樣的話岩四，求 8 的平方根的例子就被我們解決了。
int ans = (int) Math.round(mid); //先采取四舍五入
if ((long) ans * ans > n) {
ans--;
}
// 可以不用 long
if (ans > n / ans) {
ans--;
}
合起來就可以了哥攘。
//計(jì)算 x2 - n
public double fx(double x, double n) {
return x * x - n;
}
public int mySqrt(int n) {
double low = 0;
double high = n;
double mid = (low + high) / 2;
//函數(shù)值小于 0.1 的時(shí)候結(jié)束
while (Math.abs(fx(mid, n)) > 0.1) {
//左端點(diǎn)的函數(shù)值
double low_f = fx(low, n);
//中間節(jié)點(diǎn)的函數(shù)值
double low_mid = fx(mid, n);
//判斷哪一段的函數(shù)值是異號(hào)的
if (low_f * low_mid < 0) {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
//先進(jìn)行四舍五入
int ans = (int) Math.round(mid);
if (ans != 0 && ans > n / ans) {
ans--;
}
return ans;
}
時(shí)間復(fù)雜度：
空間復(fù)雜度：O（1）剖煌。
解法三 牛頓法
具體解釋可以參考下這篇文章材鹦，或者搜一下， 有很多講解的耕姊，代碼的話根據(jù)下邊的迭代式進(jìn)行寫桶唐。
。
這里的話茉兰，
尤泽。
public int mySqrt(int n) {
double t = n; // 賦一個(gè)初值
while (Math.abs(t * t - n) > 0.1) {
t = (n / t + t) / 2.0;
}
//先進(jìn)行四舍五入
int ans = (int) Math.round(t);
//判斷是否超出
if ((long) ans * ans > n) {
ans--;
}
return ans;
}
時(shí)間復(fù)雜度：
空間復(fù)雜度：O（1）。
總
首先用了正常的二分法规脸，求出整數(shù)解坯约。然后用常規(guī)的二分法、牛頓法求近似根莫鸭，然后利用一個(gè)技巧轉(zhuǎn)換為整數(shù)解闹丐。
更多詳細(xì)通俗題解詳見 leetcode.wang 。
