Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Example 2:
1
2
3
4
|
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class {
public int mySqrt(int x) {
if ( x < 0) {
return -1;
}
if (x == 0) {
return 0;
}
int lb = 1;
int ub = x;
long mid = 0;
while (lb + 1 < ub) {
mid = lb + (ub - lb) / 2;
if (mid * mid == x) {
return (int)mid;
} else if (mid * mid < x) {
lb = (int)mid;
} else {
ub = (int)mid;
}
}
return (int)lb;
}
}
|
近期评论