Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
Example:
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
Solution:
Applying binary search for a range from 1 _to x and looking for a number which has a square _x.
Code:
public int sqrt(int x) {
long start = 1;
long end = x;
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (mid * mid <= x) {
start = mid;
} else if (mid * mid > x) {
end = mid;
}
}
if (end * end <= x) {
return (int)end;
}
return (int)start;
}