int sqrt(int x)
.Compute and return the square root of x.
Naive Way: Return the square root of an integer as an integer. I use binary search. First I need to find maximum possible square root, which is (int)Math.sqrt(Integer.MAX_VALUE). And when it happens sqrt(x) is this value, can't use i^2 <= x <(i+1)^2 to end the loop since (i+1)^2 will overflow. List this case separately.
public class Solution {
static final int MAX_SQRT = (int)Math.sqrt(Integer.MAX_VALUE);
public int sqrt(int x) {
int high = MAX_SQRT, low = 0;
while(low <= high){
int middle = (high+low)/2;
if(middle*middle <= x && middle == MAX_SQRT) return middle;
if(middle*middle <= x && (middle+1)*(middle+1) > x) return middle;
if(middle*middle > x)
high = middle-1;
else
low = middle+1;
}
return low;
}
}
Improved Way: There is a mathematical method Newton's Method. I can't understand what is stated in the link. There are too mathematical. I understand from other one's algorithm newtons-iterative-method-in-c . In the answer of that question. Newton's method was explained.
No comments:
Post a Comment