Question
from lintcode
Find the square root of a number(integer).
Idea
Start from 0 to the given number. Perform a binary search to find a number whose square is closest but no larger than the given number.
public class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
if (x == 0) return x;
long start = 1;
long end = x;
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (mid * mid > x) {
end = mid;
} else {
start = mid;
}
}
if (start * start <= x)
return (int)start;
return (int)end;
}
}
