問題
Implement int sqrt(int x).
Compute and return the square root of x.
例子
sqrt(8)
2
分析
注意到sqrt的返回值為int枫甲，不是float或者double瑞凑，這樣問題就簡單很多了。而且經(jīng)過測試可以發(fā)現(xiàn)嫩挤，s = sqrt(x)血筑，s應(yīng)該是滿足s*s<=x的最大值绘沉。
使用二分法可以在O(logn)的時(shí)間找到一個整數(shù)的整數(shù)平方根煎楣。
要點(diǎn)
二分法（lower_bound）
時(shí)間復(fù)雜度
O(logn)
空間復(fù)雜度
O(1)
代碼
class Solution {
public:
int mySqrt(int x) {
if (x < 0) return INT_MIN;
int begin = 0, end = x, mid = 0;
while (begin < end) {
mid = (begin + end) / 2 + 1;
long long mid2 = (long long)mid * mid;
if (mid2 > x)
end = mid - 1;
else
begin = mid;
}
return begin;
}
};
牛頓迭代法
class Solution {
public:
int mySqrt(int x) {
long long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return r;
}
};
