Implement int sqrt(int x).
Compute and return the square root of x.
public class Solution {
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0) return 0;
//binary search method
long high = x / 2 + 1;
long low = 0;
while(low <= high) {
long mid = low + (high - low) / 2;
long approximateSquare = mid * mid;
if(approximateSquare == x)
return (int) mid;
if(approximateSquare < x) //too small
low = mid + 1;
else //too large
high = mid - 1;
}
return (int) high;
}
}
newton iteration method (x_{i+1} = x_i - f(x_i) / f^‘(x_i)). where f^‘(x_i) = 2x_i in this problem.
Therefore, x_{i+1} = x_i -(x_i^2 - x) /2x_i = ( x_i + x / x_i) / 2. The algorithm converges to the root, so the termination condition of the loop is x_{i} == x{i+1}
public class Solution {
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0) return 0;
double last = 0;
double iter = 1;
while(last != iter){ //termination condition. the algorithm converges to the root
last = iter;
iter = (iter + x / iter) / 2;
}
return (int) iter;
}
}
leetcode--Sqrt(x),布布扣,bubuko.com
原文：http://www.cnblogs.com/averillzheng/p/3825205.html